Am discutat qsort() în C. C++ STL oferă o funcție similară sortare care sortează un vector sau o matrice (articole cu acces aleatoriu)
În general, este nevoie de doi parametri, primul fiind punctul matricei/vectorului de unde trebuie să înceapă sortarea, iar al doilea parametru fiind lungimea până la care dorim ca matricea/vectorul să fie sortat. Al treilea parametru este opțional și poate fi folosit în cazuri precum dacă dorim să sortăm elementele lexicografic.
În mod implicit, funcția sort() sortează elementele în ordine crescătoare.
Mai jos este un program simplu pentru a arăta funcționarea sort().
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; }> |
>
>Ieșire
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Complexitatea timpului: O(N log N)
Spațiu auxiliar: O(1)
Cum se sortează în ordine descrescătoare?
sort() preia un al treilea parametru care este folosit pentru a specifica ordinea în care elementele vor fi sortate. Putem trece funcția great() pentru a sorta în ordine descrescătoare. Această funcție face o comparație într-un mod care pune elemente mai mari înainte.
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; }> |
>
>Ieșire
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Complexitatea timpului: O(N log N)
Spațiu auxiliar: O(1)
Sortați matricea numai în intervalul dat: Pentru a face față unor astfel de probleme, trebuie doar să menționăm intervalul din interiorul funcției de sortare.
Mai jos este implementarea cazului de mai sus:
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> |
>
>Ieșire
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Complexitatea timpului: O(N log N)
Spațiu auxiliar: O(1)
Cum se sortează într-un ordine anume?
De asemenea, putem scrie propria noastră funcție de comparare și o transmitem ca al treilea parametru. Această funcție de comparare returnează o valoare; convertibil în bool, care practic ne spune dacă primul argument trecut trebuie plasat înaintea celui de-al doilea argument sau nu.
De exemplu: În codul de mai jos, să presupunem că intervalele {6,8} și {1,9} sunt transmise ca argumente în funcția compareInterval (funcția comparator). Acum ca 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; }> |
>
>Ieșire
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
Complexitatea de timp a std::sort() este:
ipconfig gratuit pentru Linux
- Cel mai bun caz – O(N log N)
- Caz mediu – O(N log N)
- Cel mai rău caz – O(N log N)
Complexitatea spațiului: Poate folosi spațiu auxiliar O(log N).
C++
#include> #include> using> namespace> std;> template> <>class> T>>>> // we pass an object of this class as> >// third arg to sort function...> public>:> >bool> operator()(T x1, T x2)> >{> >return> x1 } }; template |
>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>
Complexitatea timpului: O(N log N)
Spațiu auxiliar: O(1)