Hemos discutido qsort() en C. C++ STL proporciona una función de clasificación similar que ordena un vector o una matriz (elementos con acceso aleatorio)
Generalmente se necesitan dos parámetros, el primero es el punto de la matriz/vector desde donde debe comenzar la clasificación y el segundo parámetro es la longitud hasta la cual queremos que se ordene la matriz/vector. El tercer parámetro es opcional y se puede utilizar en casos como si queremos ordenar los elementos lexicográficamente.
De forma predeterminada, la función sort() ordena los elementos en orden ascendente.
A continuación se muestra un programa sencillo para mostrar el funcionamiento 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; }> |
>
>Producción
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Complejidad del tiempo: O(N iniciar sesión N)
Espacio Auxiliar: O(1)
¿Cómo ordenar en orden descendente?
sort() toma un tercer parámetro que se utiliza para especificar el orden en el que se ordenarán los elementos. Podemos pasar la función mayor() para ordenar en orden descendente. Esta función hace una comparación de una manera que antepone elementos mayores.
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; }> |
>
>Producción
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Complejidad del tiempo: O(N iniciar sesión N)
Espacio Auxiliar: O(1)
Ordene la matriz solo en el rango dado: Para solucionar este tipo de problemas sólo tenemos que mencionar el rango dentro de la función de clasificación.
A continuación se muestra la implementación del caso 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> |
>
>Producción
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Complejidad del tiempo: O (N log N)
Espacio auxiliar: O(1)
¿Cómo ordenar en un ¿orden particular?
También podemos escribir nuestra propia función de comparación y pasarla como tercer parámetro. Esta función de comparación devuelve un valor; convertible a bool, que básicamente nos dice si el primer argumento pasado debe colocarse antes del segundo argumento pasado o no.
Por ejemplo: en el código siguiente, supongamos que los intervalos {6,8} y {1,9} se pasan como argumentos en la función compareInterval (función de comparación). Ahora como 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; }> |
>
>Producción
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
La complejidad temporal de std::sort() es:
bin en bcd
- Mejor caso: O (N log N)
- Caso promedio – O(N log N)
- Peor de los casos: O (N log N)
Complejidad espacial: Puede utilizar espacio 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 |
>
>Producción
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>
Complejidad del tiempo: O(N iniciar sesión N)
Espacio Auxiliar: O(1)