Hem comentat qsort() en C. C++ STL proporciona una funció similar que ordena un vector o una matriu (elements amb accés aleatori)
En general, pren dos paràmetres, el primer és el punt de la matriu/vector des d'on ha de començar l'ordenació i el segon paràmetre és la longitud fins a la qual volem que s'ordena la matriu/vector. El tercer paràmetre és opcional i es pot utilitzar en casos com si volem ordenar els elements lexicogràficament.
Per defecte, la funció sort() ordena els elements en ordre ascendent.
A continuació es mostra un programa senzill per mostrar el funcionament de 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; }> |
>
>Sortida
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Complexitat temporal: O(N log N)
Espai auxiliar: O(1)
Com ordenar en ordre descendent?
sort() pren un tercer paràmetre que s'utilitza per especificar l'ordre en què s'han d'ordenar els elements. Podem passar la funció major() per ordenar en ordre descendent. Aquesta funció fa una comparació d'una manera que posa els elements més grans abans.
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; }> |
>
>Sortida
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Complexitat temporal: O(N log N)
Espai auxiliar: O(1)
Ordena la matriu només en l'interval donat: Per fer front a aquest tipus de problemes només hem d'esmentar l'interval dins de la funció d'ordenació.
A continuació es mostra la implementació del cas anterior:
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> |
>
>Sortida
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Complexitat temporal: O(N log N)
Espai auxiliar: O(1)
Com ordenar en a ordre particular?
També podem escriure la nostra pròpia funció comparadora i passar-la com a tercer paràmetre. Aquesta funció comparadora retorna un valor; convertible a bool, que bàsicament ens indica si el primer argument passat s'ha de col·locar abans del segon argument passat o no.
Per exemple: En el codi següent, suposem que els intervals {6,8} i {1,9} es passen com a arguments a la funció compareInterval (funció comparadora). Ara com 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; }> |
>
>Sortida
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
La complexitat temporal de std::sort() és:
selecciona com
- Millor cas: O(N log N)
- Cas mitjà: O(N log N)
- El pitjor dels casos: O(N log N)
Complexitat espacial: Pot utilitzar espai auxiliar O(log N).
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 |
>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>
Complexitat temporal: O(N log N)
Espai auxiliar: O(1)