Noi abbiamo discusso qsort() in C. C++ STL fornisce una funzione simile per ordinare un vettore o un array (elementi con accesso casuale)
Generalmente richiede due parametri, il primo è il punto dell'array/vettore da cui deve iniziare l'ordinamento e il secondo parametro è la lunghezza fino alla quale vogliamo che l'array/vettore venga ordinato. Il terzo parametro è facoltativo e può essere utilizzato in casi come se si volessero ordinare gli elementi lessicograficamente.
Per impostazione predefinita, la funzione sort() ordina gli elementi in ordine crescente.
Di seguito è riportato un semplice programma per mostrare il funzionamento di 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; }> |
>
>Produzione
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Complessità temporale: O(N logN)
Spazio ausiliario: O(1)
Come ordinare in ordine decrescente?
sort() accetta un terzo parametro utilizzato per specificare l'ordine in cui devono essere ordinati gli elementi. Possiamo passare la funzione major() per ordinare in ordine decrescente. Questa funzione esegue un confronto in modo da anteporre elementi maggiori.
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; }> |
>
>Produzione
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Complessità temporale: O(N logN)
Spazio ausiliario: O(1)
Ordina l'array solo nell'intervallo specificato: Per affrontare questo tipo di problemi dobbiamo solo menzionare l'intervallo all'interno della funzione di ordinamento.
Di seguito è riportata l'implementazione del caso precedente:
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> |
>
>Produzione
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Complessità temporale: O(N log N)
Spazio ausiliario: O(1)
Come ordinare in a ordine particolare?
Possiamo anche scrivere la nostra funzione comparatrice e passarla come terzo parametro. Questa funzione comparatrice restituisce un valore; convertibile in bool, che sostanzialmente ci dice se il primo argomento passato deve essere posizionato prima del secondo argomento passato oppure no.
Ad esempio: nel codice seguente, supponiamo che gli intervalli {6,8} e {1,9} vengano passati come argomenti nella funzione compareInterval (funzione comparatrice). Ora come 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; }> |
>
>Produzione
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
La complessità temporale di std::sort() È:
Java analizza la stringa in int
- Caso migliore – O(N log N)
- Caso medio – O(N log N)
- Caso peggiore – O(N log N)
Complessità spaziale: Può utilizzare lo spazio ausiliario 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 |
>
>Produzione
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>
Complessità temporale: O(N logN)
Spazio ausiliario: O(1)