0Pricing
C++ Academy · Lektion

Sortieren und Partitionieren: sort, stable_partition

Sortieren und partitionieren Sie Container mit std::sort und std::stable_partition.

Sortieren und Partitionieren: sort, stable_partition ist eine kostenlose C++ Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C++ Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.

std::sort

Der Standardalgorithmus für das Sortieren. Durchschnittlich O(N log N). In-place. Nicht garantiert stabil.

#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

Benutzerdefinierter Komparator

Übergeben Sie einen Komparator (Lambda oder Funktor), um nach anderen Kriterien zu sortieren.

std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });   // descending

Benutzerdefinierte Typen sortieren

Stellen Sie einen Komparator bereit, der bestimmte Member vergleicht, oder definieren Sie operator< für den Typ.

struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });

std::stable_sort

Wie sort, behält aber die relative Reihenfolge gleicher Elemente bei. Etwas langsamer (typischerweise O(N log^2 N) zusätzlicher Speicher).

std::partial_sort

Platziert die kleinsten k Elemente an erster Stelle und sortiert sie. Die übrigen Elemente befinden sich in einer nicht näher bestimmten Reihenfolge. Schneller als eine vollständige Sortierung, wenn Sie nur die Top-k-Elemente benötigen.

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sorted

std::nth_element

Teilt den Bereich so auf, dass das Element an der Position nth dem Element an dieser Position in einem vollständig sortierten Bereich entspricht. Alles davor ist ≤ dem n-ten Element, alles danach ist ≥ ihm. Durchschnittlich O(N).

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

Prüft, ob ein Bereich bereits sortiert ist.

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

Ordnet einen Bereich so um, dass Elemente, die ein Prädikat erfüllen, zuerst kommen. Gibt den Iterator auf das erste Element zurück, das das Prädikat nicht erfüllt. Nicht stabil.

std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });
// even numbers come first, then odd

std::stable_partition

Wie partition, behält aber die relative Reihenfolge innerhalb jeder Gruppe bei.

Nach mehreren Schlüsseln sortieren

Verwenden Sie einen Komparator, der zuerst den primären Schlüssel und bei Gleichheit den sekundären Schlüssel vergleicht.

std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.age != b.age) return a.age < b.age;
        return a.name < b.name;
    });

Binäre Suche in sortierten Bereichen

Verwenden Sie nach dem Sortieren std::lower_bound, std::upper_bound und std::binary_search für Suchen in O(log N).

Schnelltest

Welcher Algorithmus behält nach dem Sortieren die relative Reihenfolge gleicher Elemente bei?

Zusammenfassung

Verwenden Sie std::sort für allgemeine Sortierungen, std::stable_sort, wenn die Reihenfolge gleicher Elemente wichtig ist, std::partial_sort für Top-k-Elemente, std::nth_element zum Auswählen und std::partition/std::stable_partition zum Gruppieren.

Häufig gestellte Fragen

Ist die Lektion „Sortieren und Partitionieren: sort, stable_partition“ kostenlos?

Ja — der vollständige Text von „Sortieren und Partitionieren: sort, stable_partition“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C++ Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Sortieren und Partitionieren: sort, stable_partition“?

Sortieren und partitionieren Sie Container mit std::sort und std::stable_partition. Du übst C++ Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C++ Academy zu starten?

Keine Vorkenntnisse erforderlich. C++ Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Sortieren und Partitionieren: sort, stable_partition“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C++ Academy-Lektion Code schreiben und ausführen?

Ja. Jede C++ Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Nicht verändernde Algorithmen: find, count, all_of
  2. Verändernde Algorithmen: transform, copy_if, replace
  3. Sortieren und Partitionieren: sort, stable_partition
  4. Numerische Algorithmen: accumulate, reduce, transform_reduce
← Zurück zu C++ Academy