Verwendung von sort() in der C++ std Library

Einführung

Sortieren ist eine grundlegende Operation in der Programmierung, bei der Elemente in einer bestimmten Reihenfolge angeordnet werden. Diese Elemente können Teil einer Sequenz, eines Arrays oder einer anderen Datenstruktur sein. In C++ bietet die Standardbibliothek die eingebaute Funktion std::sort(), die Sortiervorgänge mit beeindruckender Effizienz vereinfacht.

In diesem aktualisierten Tutorial lernen Sie die Verwendung, Varianten und Besonderheiten der Funktion std::sort() in C++ kennen. Los geht's!

Was ist std::sort()?

Die Funktion std::sort() ist ein leistungsstarkes Werkzeug der C++-Standardbibliothek, definiert im Header <algorithm>. Sie ermöglicht das Sortieren von Datenstrukturen wie Arrays und Vektoren in aufsteigender oder absteigender Reihenfolge und bietet die Möglichkeit, benutzerdefinierte Sortierkriterien festzulegen.

Syntax

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• first: Iterator, der auf das erste Element des zu sortierenden Bereichs zeigt.
• last: Iterator, der auf das Ende des zu sortierenden Bereichs zeigt (einen Platz nach dem letzten Element).
• comp (optional): Eine Vergleichsfunktion oder ein Funktionsobjekt, das die Sortierreihenfolge definiert. Wird dieser Parameter weggelassen, werden die Elemente standardmäßig in aufsteigender Reihenfolge mit std::less<>() sortiert.

Sortieren mit std::sort()

1. Sortieren in aufsteigender Reihenfolge (Standardverhalten)

Standardmäßig ordnet std::sort() Elemente in aufsteigender Reihenfolge an, wenn der Parameter comp nicht angegeben ist.

Beispiel:

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int demo[5] = {5, 4, 3, 2, 1};

int len = sizeof(demo) / sizeof(demo[0]);

cout << "Before sorting: ";

for (int i = 0; i < len; i++) cout << demo[i] << " ";

std::sort(demo, demo + len); // Default ascending sort

cout << "\nAfter sorting: ";

for (int i = 0; i < len; i++) cout << demo[i] << " ";

return 0;

}

Output:

Before sorting: 5 4 3 2 1

After sorting: 1 2 3 4 5

2. Sortieren in absteigender Reihenfolge

Um in absteigender Reihenfolge zu sortieren, geben Sie einen Comparator wie std::greater<int>() als dritten Parameter an.

Beispiel:

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int demo[5] = {44, 22, 55, 33, 66};

int len = sizeof(demo) / sizeof(demo[0]);

cout << "Before sorting: ";

for (int i = 0; i < len; i++) cout << demo[i] << " ";

std::sort(demo, demo + len, greater<int>()); // Descending sort

cout << "\nAfter sorting: ";

for (int i = 0; i < len; i++) cout << demo[i] << " ";

return 0;

}

Output:

Before sorting: 44 22 55 33 66 
After sorting: 66 55 44 33 22

Alternativ können Sie eine Lambda-Funktion für eine benutzerdefinierte absteigende Sortierung verwenden:

std::sort(demo, demo + len, [](int a, int b) { return a > b; });

3. Sortieren mit benutzerdefinierter Reihenfolge

Der Parameter comp erlaubt es, eigene Sortierlogiken zu definieren. Zum Beispiel können Sie Elemente basierend auf ihren Resten bei der Division durch 10 sortieren.

Beispiel:

#include <iostream>

#include <algorithm>

using namespace std;

bool customSort(int a, int b) {

return (a % 10) < (b % 10);

}

int main() {

int demo[5] = {18, 45, 34, 92, 21};

int len = sizeof(demo) / sizeof(demo[0]);

cout << "Vor dem Sortieren: ";

for (int i = 0; i < len; i++) cout << demo[i] << " ";

std::sort(demo, demo + len, customSort); // Sortieren nach Resten bei Division durch 10

cout << "\nNach dem Sortieren: ";

for (int i = 0; i < len; i++) cout << demo[i] << " ";

return 0;

}

Output:

Before sorting: 18 45 34 92 21 
After sorting: 21 92 34 45 18

Komplexität von std::sort()

Die Zeitkomplexität von std::sort() beträgt O(Nlog(N)) im Durchschnitts- und Worst-Case, was es zu einer sehr effizienten Methode für große Datensätze macht.

Tipps und Best Practices

1. 1. Verwenden Sie geeignete Iteratoren: Übergeben Sie std::sort() immer Random-Access-Iteratoren (z. B. für Arrays oder Vektoren).
   2. Nutzen Sie Lambda-Funktionen für benutzerdefinierte Sortierungen: Lambda-Funktionen sind oft klarer und prägnanter als separate Vergleichsfunktionen.
   3. Optimieren Sie die Lesbarkeit: Verwenden Sie aussagekräftige Namen für benutzerdefinierte Comparator-Funktionen oder Lambdas, um die Sortierlogik zu verdeutlichen.
   4. Sortieren Sie andere Container: std::sort() funktioniert auch mit anderen Containern wie std::vector oder std::deque.

   Beispiel: Sortieren eines std::vector:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

vector<int> vec = {3, 1, 4, 1, 5};

std::sort(vec.begin(), vec.end()); // Ascending sort

cout << "Sorted vector: ";

for (int v : vec) cout << v << " ";

return 0;

}

Zusammenfassung