Wir haben diskutiert qsort() in C. C++ STL bietet eine ähnliche Funktion sort, die einen Vektor oder ein Array (Elemente mit wahlfreiem Zugriff) sortiert.
Im Allgemeinen werden zwei Parameter benötigt: Der erste ist der Punkt des Arrays/Vektors, von dem aus die Sortierung beginnen muss, und der zweite Parameter ist die Länge, bis zu der das Array/der Vektor sortiert werden soll. Der dritte Parameter ist optional und kann beispielsweise dann verwendet werden, wenn wir die Elemente lexikografisch sortieren möchten.
Standardmäßig sortiert die Funktion sort() die Elemente in aufsteigender Reihenfolge.
Unten finden Sie ein einfaches Programm, das die Funktionsweise von sort() zeigt.
CPP
// C++ program to demonstrate default behaviour of> // sort() in STL.> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >/*Here we take two parameters, the beginning of the> >array and the length n upto which we want the array to> >be sorted*/> >sort(arr, arr + n);> >cout <<>'
Array after sorting using '> >'default sort is :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; }> |
>
>Ausgabe
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Zeitkomplexität: O(N log N)
Hilfsraum: O(1)
Wie sortiere ich in absteigender Reihenfolge?
sort() benötigt einen dritten Parameter, der verwendet wird, um die Reihenfolge anzugeben, in der Elemente sortiert werden sollen. Wir können die Funktion „größer()“ übergeben, um in absteigender Reihenfolge zu sortieren. Diese Funktion führt einen Vergleich so durch, dass größere Elemente vorangestellt werden.
CPP
// C++ program to demonstrate descending order sort using> // greater().> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >sort(arr, arr + n, greater<>int>>());> >cout <<>'Array after sorting :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; }> |
>
>Ausgabe
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Zeitkomplexität: O(N log N)
Hilfsraum: O(1)
Sortieren Sie das Array nur im angegebenen Bereich: Um solche Probleme zu lösen, müssen wir lediglich den Bereich innerhalb der Sortierfunktion erwähnen.
Unten ist die Implementierung des obigen Falls:
C++
// C++ program to demonstrate sort()> #include> using> namespace> std;> int> main()> {> >int> arr[] = { 0, 1, 5, 8, 9, 6, 7, 3, 4, 2 };> >int> n =>sizeof>(arr) />sizeof>(arr[0]);> >// Sort the elements which lies in the range of 2 to> >// (n-1)> >sort(arr + 2, arr + n);> >cout <<>'Array after sorting :
'>;> >for> (>int> i = 0; i cout << arr[i] << ' '; return 0; } // This code is contributed by Suruchi Kumari> |
>
>Ausgabe
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Zeitkomplexität: O(N log N)
Hilfsraum: O(1)
So sortieren Sie ein bestimmte Reihenfolge?
Wir können auch unsere eigene Komparatorfunktion schreiben und sie als dritten Parameter übergeben. Diese Komparatorfunktion gibt einen Wert zurück; konvertierbar in bool, was uns im Grunde sagt, ob das übergebene erste Argument vor dem übergebenen zweiten Argument platziert werden soll oder nicht.
Zum Beispiel: Nehmen wir im folgenden Code an, dass die Intervalle {6,8} und {1,9} als Argumente in der Funktion „compareInterval“ (Komparatorfunktion) übergeben werden. Jetzt als i1.first (=6)
CPP
// A C++ program to demonstrate> // STL sort() using> // our own comparator> #include> using> namespace> std;> // An interval has a start> // time and end time> struct> Interval {> >int> start, end;> };> // Compares two intervals> // according to starting times.> bool> compareInterval(Interval i1, Interval i2)> {> >return> (i1.start } int main() { Interval arr[] = { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } }; int n = sizeof(arr) / sizeof(arr[0]); // sort the intervals in increasing order of // start time sort(arr, arr + n, compareInterval); cout << 'Intervals sorted by start time :
'; for (int i = 0; i cout << '[' << arr[i].start << ',' << arr[i].end << '] '; return 0; }> |
>
>Ausgabe
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
Die zeitliche Komplexität von std::sort() Ist:
Namensverzeichnis Linux ändern
- Bester Fall – O(N log N)
- Durchschnittlicher Fall – O(N log N)
- Worst-Case – O(N log N)
Raumkomplexität: Es kann O(log N) Hilfsraum verwenden.
C++
#include> #include> using> namespace> std;> template> <>class> T>> class> Comparator {>// we pass an object of this class as> >// third arg to sort function...> public>:> >bool> operator()(T x1, T x2)> >{> >return> x1 } }; template |
>
>Ausgabe
The array before sorting is : 1 5 8 9 6 7 3 4 2 0 The array after sorting is(asc) :0 1 2 3 4 5 6 7 8 9 The array after sorting is(desc) :9 8 7 6 5 4 3 2 1 0 The array after sorting is(asc but our comparator class) :0 1 2 3 4 5 6 7 8 9 The array after sorting is(asc but our comparator function) :0 1 2 3 4 5 6 7 8 9>
Zeitkomplexität: O(N log N)
Hilfsraum: O(1)