Sortieren in der C++ Standard Template Library(STL)

1. Verwendung der Funktion sort() zum Sortieren von Array oder STL-Containern in C++
2. Sortieren des Arrays in absteigender Reihenfolge in C++
3. Verwendung der Funktion partial_sort() zum Sortieren eines Teils eines Arrays oder Vektors
4. Benutzerdefinierte oder benutzerdefinierte Sortierung mit der Funktion sort() in C++
5. Verwendung der Methode is_sorted() in C++
6. Zeitkomplexität von Sortieralgorithmen

In diesem Tutorial lernen wir eine weit verbreitete C++-Funktion namens sort() kennen. Wir werden uns auch andere Funktionen ansehen, die mit dem Sortieren zusammenhängen.

Um Daten in C++ zu sortieren, schreiben wir unseren Algorithmus und wenden ihn auf Daten an, oder wir können die eingebaute Funktion sort() verwenden, die in C++ STL vorhanden ist. Die Funktion sort() ist in der Header-Datei algorithm definiert.

Diese Funktion verwendet den IntroSort-Algorithmus, einen hybriden Sortieralgorithmus, der die drei Sortieralgorithmen Quicksort, Heapsort und Insertionsort verwendet, um die Laufzeit zu minimieren.

Diese Funktion sortiert die Elemente des angegebenen Bereichs.

Syntax:

sort(start iterator, end iterator, compare_function)

Dies sortiert die Elemente in dem Bereich, der durch Start-Iterator und End-Iterator definiert ist, standardmäßig in aufsteigender Reihenfolge (dies ist die Standard-compare_function).

Verwendung der Funktion sort() zum Sortieren von Array oder STL-Containern in C++

Das Sortieren ist eine der grundlegenden Operationen, die an Daten durchgeführt wird. Wir ordnen Daten aufsteigend, absteigend oder benutzerdefiniert (benutzerdefinierte Sortierung) an.

Wir können ein Array oder STL-Container wie Vektor, Set, Map usw. in C++ mit der Funktion sort() sortieren.

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

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n);
  sort(v.begin(), v.end());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Ausgabe:

The array  after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67

Die Elemente sind standardmäßig in aufsteigender Reihenfolge angeordnet.

Sortieren des Arrays in absteigender Reihenfolge in C++

Um in C++ STL vorhandene Arrays oder Container in absteigender Reihenfolge zu sortieren, müssen wir einen dritten Parameter namens greater<type>() in der Funktion sort() übergeben. Diese Funktion führt einen Vergleich durch, sodass die Elemente am Ende in absteigender Reihenfolge sortiert werden.

Der Typ bezieht sich auf den Typ des Arrays oder Containers, den wir verwenden, Int, Float oder String-Typ.

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

int main() {
  int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

  // array size
  int n = sizeof(arr) / sizeof(arr[0]);

  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << "The array  after sorting is : \n";

  sort(arr, arr + n, greater<int>());
  sort(v.begin(), v.end(), greater<int>());  // sorting vector

  for (int i = 0; i < n; ++i) cout << arr[i] << " ";

  cout << endl;

  cout << "The vector after sorting is : \n";
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}

Ausgabe:

The array  after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22

Verwendung der Funktion partial_sort() zum Sortieren eines Teils eines Arrays oder Vektors

Wir können partial_sort() verwenden, um nur einen Teil eines Arrays zu sortieren. Diese Methode ist nichts anderes als eine Variante der ursprünglichen sort-Methode.

Syntax:

partial_sort(first, middle, last)

Es ordnet die Elemente im Bereich (first, last) neu an, so dass die Elemente vor der Mitte in aufsteigender Reihenfolge sortiert werden und die Elemente nach der Mitte ohne bestimmte Reihenfolge belassen werden.

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

int main() {
  vector<int> vr{35, 67, 11, -9, 7, -22};  // vector

  cout << "The vector after partial sorting is : \n";

  partial_sort(vr.begin(), vr.begin() + 2, vr.end());

  for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}

Ausgabe:

The vector after partial sorting is :
-22 -9 67 35 11 7

Wir können beobachten, dass nur die ersten beiden Elemente sortiert werden, die verbleibenden sind nur in einer zufälligen Reihenfolge vorhanden.

Benutzerdefinierte oder benutzerdefinierte Sortierung mit der Funktion sort() in C++

Solange wir die Daten in aufsteigender oder absteigender Reihenfolge sortieren möchten, können wir diese Funktion verwenden, aber manchmal möchten wir, dass die Daten auf benutzerdefinierte Weise sortiert werden.

Hier müssen wir unsere benutzerdefinierte Sortierfunktion schreiben, die wir als dritten Parameter in der Funktion sort() übergeben.

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

bool myfunction(string x, string y) { return x.size() < y.size(); }

int main() {
  string str[] = {"a", "abc", "ba", "abcd"};
  int n = 4;

  sort(str, str + n);  // normal sort function
  cout << "Array after sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";

  cout << endl;

  sort(str, str + n, myfunction);
  cout << "Array after user defined sorting : \n";
  for (int i = 0; i < n; ++i) cout << str[i] << " ";
}

Ausgabe:

Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd

Die erste Sortiermethode sortiert das Array von Zeichenfolgen standardmäßig in lexikografisch aufsteigender Reihenfolge. Die zweite Sortiermethode sortiert die Strings nach ihrer Länge, d.h. der Bedingung, die wir in unserer benutzerdefinierten Vergleichsfunktion namens myfunction erwähnt haben.

Verwendung der Methode is_sorted() in C++

Wenn wir überprüfen möchten, ob der angegebene Datenbereich sortiert ist oder nicht, können wir diese Methode verwenden.

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

int main() {
  vector<int> v{35, 67, 11, -9, 7, -22};  // vector

  cout << is_sorted(v.begin(), v.end());
}

Ausgabe:

0

Da der Vektor nicht sortiert ist, erhalten wir als Ausgabe 0, was false bedeutet.

Zeitkomplexität von Sortieralgorithmen

sort() hat eine Zeitkomplexität von O(NlogN), wobei N die Anzahl der Elemente ist, auf die die Funktion sort() angewendet wird.