We hebben besproken qsort() in C. C++ STL biedt een vergelijkbare functiesortering die een vector of array sorteert (items met willekeurige toegang)
Er zijn over het algemeen twee parameters nodig, de eerste is het punt van de array/vector vanwaar het sorteren moet beginnen en de tweede parameter is de lengte tot waar we willen dat de array/vector wordt gesorteerd. De derde parameter is optioneel en kan bijvoorbeeld worden gebruikt als we de elementen lexicografisch willen sorteren.
Standaard sorteert de functie sort() de elementen in oplopende volgorde.
Hieronder staat een eenvoudig programma om de werking van sort() te laten zien.
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; }> |
>
>Uitvoer
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Tijdcomplexiteit: O(N logboek N)
Hulpruimte: O(1)
Hoe aflopend sorteren?
sort() heeft een derde parameter nodig die wordt gebruikt om de volgorde op te geven waarin elementen moeten worden gesorteerd. We kunnen de functie groter() doorgeven om in aflopende volgorde te sorteren. Deze functie voert een vergelijking uit op een manier die grotere elementen ervoor plaatst.
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; }> |
>
>Uitvoer
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Tijdcomplexiteit: O(N logboek N)
Hulpruimte: O(1)
Sorteer de array alleen binnen het opgegeven bereik: Om met dit soort problemen om te gaan, hoeven we alleen maar het bereik binnen de sorteerfunctie te vermelden.
Hieronder vindt u de implementatie van bovenstaande casus:
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> |
>
>Uitvoer
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Tijdcomplexiteit: O(N log N)
Hulpruimte: O(1)
Hoe sorteer je in een bepaalde volgorde?
We kunnen ook onze eigen comparatorfunctie schrijven en deze als derde parameter doorgeven. Deze vergelijkingsfunctie retourneert een waarde; converteerbaar naar bool, wat ons in feite vertelt of het doorgegeven eerste argument vóór het doorgegeven tweede argument moet worden geplaatst of niet.
Bijvoorbeeld: Stel dat in de onderstaande code de intervallen {6,8} en {1,9} worden doorgegeven als argumenten in de functie CompareInterval (vergelijkingsfunctie). Nu 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; }> |
>
>Uitvoer
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
De tijdscomplexiteit van std::sort() is:
Java-webservices
- Beste geval – O(N log N)
- Gemiddeld geval – O(N log N)
- In het slechtste geval – O(N log N)
Ruimtecomplexiteit: Het kan O(log N) hulpruimte gebruiken.
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 |
>
>Uitvoer
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>
Tijdcomplexiteit: O(N logboek N)
Hulpruimte: O(1)