Ausführbare C++-Docs: Sortieren

Q: Wie sortiert man einen Vektor in C++?

Binde ein und rufe sort(v.begin(), v.end()) auf. Das sortiert die Elemente an Ort und Stelle in aufsteigender Reihenfolge mithilfe von operator<. Um ein Array zu sortieren, übergib arr und arr + n (oder begin(arr) / end(arr)).

Q: Wie sortiert man in C++ in absteigender Reihenfolge?

Übergib eine Vergleichsfunktion, die a > b zurückgibt: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Du kannst auch das eingebaute sort(v.begin(), v.end(), greater ()); aus verwenden.

Q: Warum bringt meine Vergleichsfunktion std::sort in C++ zum Absturz?

Deine Vergleichsfunktion muss eine strikte schwache Ordnung (strict weak ordering) sein: Sie muss false zurückgeben, wenn beide Argumente gleich sind. = zu verwenden (was bei gleichen Elementen true zurückgibt) verletzt diese Regel und ist undefiniertes Verhalten - std::sort kann außerhalb der Grenzen lesen und abstürzen. Vergleiche immer mit .

Sortieren ist nur ein weiterer Algorithmus

Auf der vorherigen Seite hast du gesehen, dass die Standardbibliothek fertige Algorithmen mitbringt, die über Iteratoren auf jedem Bereich funktionieren. Sortieren ist der Algorithmus, zu dem du am häufigsten greifst, und er bekommt seine eigene Seite, weil er ein paar scharfe Kanten hat: eigene Ordnungen, Stabilität und eine Regel, die dir, wenn du sie brichst, undefiniertes Verhalten statt einer falschen Antwort beschert.

Das Arbeitstier ist std::sort aus <algorithm>. Du gibst ihm den Anfang und das Ende eines Bereichs, und es ordnet die Elemente an Ort und Stelle in aufsteigender Reihenfolge um:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // aufsteigend, an Ort und Stelle

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Es wird keine Kopie erstellt - der Vektor selbst wird umgeordnet. Unter der Haube ist std::sort typischerweise ein Introsort (Quicksort, der auf Heapsort zurückfällt) und liefert dir im Durchschnitt O(n log n). Das ist fast immer schneller und weit weniger fehleranfällig, als deine eigene Sortierung zu schreiben.

Es funktioniert auch mit einfachen C-Arrays - du beschreibst den Bereich einfach mit Zeigern:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // oder sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Eigene Reihenfolge mit einer Vergleichsfunktion

Standardmäßig ordnet std::sort die Elemente mit operator<. Um anders zu sortieren, übergib ein drittes Argument: eine Vergleichsfunktion, die zwei Elemente nimmt und true zurückgibt, wenn das erste vor dem zweiten kommen soll.

Ein Lambda passt hier natürlich. Absteigende Reihenfolge ist einfach a > b:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a vor b", wenn a größer ist -> absteigend
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Für den häufigen Fall einer einfachen absteigenden Reihenfolge bei eingebauten Typen liefert die Bibliothek sogar eine fertige Vergleichsfunktion mit, greater<T>() aus <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // dasselbe wie a > b

Die Vergleichsfunktion ist auch der Weg, nach etwas anderem als dem Wert selbst zu sortieren - zum Beispiel Strings nach Länge statt alphabetisch zu sortieren:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // kürzere Wörter zuerst
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Nimm die Parameter der Vergleichsfunktion per const& für alles, was größer als ein paar Bytes ist (wie string) - jedes Element bei jedem Vergleich zu kopieren ist reine Verschwendung.

Structs nach einem Feld sortieren

In echten Programmen sortierst du normalerweise Sammlungen von Structs nach einem ihrer Felder. Die Vergleichsfunktion greift einfach auf das Feld zu, das dich interessiert. Hier sortieren wir Personen nach Alter, die jüngsten zuerst:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Beachte, dass Linus und Dennis beide 25 Jahre alt sind. Sie kamen hier in ihrer ursprünglichen relativen Reihenfolge heraus, aber std::sort garantiert das nicht. Wenn die relative Reihenfolge gleicher Elemente wichtig ist, verwende std::stable_sort, das sie erhält (zu geringen Performance-Kosten):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus bleibt vor Dennis - ihre Eingabereihenfolge bleibt erhalten
    return 0;
}

Um Gleichstände gezielt aufzulösen - etwa nach Alter und dann alphabetisch nach Name sortieren - vergleiche den sekundären Schlüssel nur dann, wenn die primären Schlüssel gleich sind. std::tie macht das übersichtlich:

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // Alter, dann Name
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis & Linus 25, alphabetisch
    return 0;
}

Die Strict-Weak-Ordering-Falle

Das ist der mit Abstand gefährlichste Fehler beim Sortieren in C++, denn er gibt dir keine falsche Antwort - er gibt dir undefiniertes Verhalten, was oft einen Absturz oder einen Lesezugriff außerhalb der Grenzen bedeutet.

std::sort verlangt, dass deine Vergleichsfunktion eine strikte schwache Ordnung definiert. Die praktische Regel: comp(x, x) muss false sein für jedes Element x. Mit anderen Worten: Ein Element ist nie „vor" sich selbst. Genau das geben dir < und >, und genau das brechen <= und >=:

// BUG: gibt true zurück, wenn a == b, und verletzt damit die strikte schwache Ordnung.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // undefiniertes Verhalten - kann bei manchen Eingaben abstürzen
});

Mit <= behauptet die Vergleichsfunktion, dass 5 vor einer anderen 5 kommt, was widersprüchlich ist. std::sort kann dann einen Zeiger über das Ende des Bereichs hinaus laufen lassen. Kleine Eingaben scheinen manchmal zu funktionieren, was diesen Bug furchteinflößend macht - er kann deine Tests bestehen und in der Produktion abstürzen. Die Lösung ist schlicht <:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // korrekt: false, wenn gleich
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Ein zweiter Klassiker: Sortieren macht alles ungültig, das in den Bereich hineinzeigt. Iteratoren, Zeiger und Indizes, die du vor dem Sortieren gespeichert hast, verweisen danach nicht mehr auf dasselbe logische Element, weil sich die Elemente bewegt haben. Leite jede Position, die du brauchst, nach dem Sortieren neu ab, niemals vorher.

Einen Teil eines Bereichs sortieren

Manchmal musst du nicht alles sortieren - du willst nur die obersten paar. Den ganzen Vektor zu sortieren, um die ersten drei zu lesen, ist Verschwendung. std::partial_sort ordnet nur die Elemente, die du verlangst, und lässt den Rest in unspezifizierter Reihenfolge, was günstiger ist:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Setzt die 3 kleinsten, in Reihenfolge, nach vorne. Der Rest ist unspezifiziert.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

Und wenn du nur das eine Element brauchst, das an einer bestimmten Position stehen würde - wie der Median - macht std::nth_element noch weniger Arbeit: Es platziert das richtige Element an diesem Index, mit allem Kleineren davor und allem Größeren dahinter, alles im Durchschnitt in O(n).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Greife zu diesen, wenn „vollständig sortiert" mehr ist, als das Problem tatsächlich braucht - sie sparen bei großen Datenmengen echte Zeit.

Als Nächstes: Templates

Ist dir aufgefallen, dass dasselbe std::sort mit int, string und deinem eigenen Person-Struct umgehen konnte, und dass greater<int>() genauso gut greater<string>() sein könnte? Diese Allgemeingültigkeit ist keine Magie - es sind Templates, der Mechanismus, der ein einziges Stück Code für jeden Typ funktionieren lässt, den der Aufrufer einsteckt. Auf der nächsten Seite sehen wir, wie du deine eigenen templatisierten Funktionen und Klassen schreibst, damit dein Code so typunabhängig sein kann wie die Algorithmen, die du verwendet hast.

Häufig gestellte Fragen

Wie sortiert man einen Vektor in C++?

Binde <algorithm> ein und rufe sort(v.begin(), v.end()) auf. Das sortiert die Elemente an Ort und Stelle in aufsteigender Reihenfolge mithilfe von operator<. Um ein Array zu sortieren, übergib arr und arr + n (oder begin(arr) / end(arr)).

Wie sortiert man in C++ in absteigender Reihenfolge?

Übergib eine Vergleichsfunktion, die a > b zurückgibt: sort(v.begin(), v.end(), [](int a, int b){ return a > b; });. Du kannst auch das eingebaute sort(v.begin(), v.end(), greater<int>()); aus <functional> verwenden.

Warum bringt meine Vergleichsfunktion std::sort in C++ zum Absturz?

Deine Vergleichsfunktion muss eine strikte schwache Ordnung (strict weak ordering) sein: Sie muss false zurückgeben, wenn beide Argumente gleich sind. <= oder >= zu verwenden (was bei gleichen Elementen true zurückgibt) verletzt diese Regel und ist undefiniertes Verhalten - std::sort kann außerhalb der Grenzen lesen und abstürzen. Vergleiche immer mit < oder >.

Verwandte Konzepte