logo

std::sort() i C++ STL

Vi har diskuterat qsort() i C. C++ STL tillhandahåller en liknande funktionssortering som sorterar en vektor eller array (objekt med direktåtkomst)

Det krävs vanligtvis två parametrar, den första är punkten för arrayen/vektorn där sorteringen behöver börja och den andra parametern är längden upp till vilken vi vill att arrayen/vektorn ska sorteras. Den tredje parametern är valfri och kan användas i fall som om vi vill sortera elementen lexikografiskt.



Som standard sorterar funktionen sort() elementen i stigande ordning.

Nedan finns ett enkelt program för att visa hur 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; }>

>

>

Produktion

Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>

Tidskomplexitet: O(N log N)
Hjälputrymme: O(1)

Hur sorterar man i fallande ordning?
sort() tar en tredje parameter som används för att specificera i vilken ordning element ska sorteras. Vi kan skicka funktionen greater() för att sortera i fallande ordning. Denna funktion gör en jämförelse på ett sätt som sätter större element före.

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; }>

>

>

Produktion

Array after sorting : 9 8 7 6 5 4 3 2 1 0>

Tidskomplexitet: O(N log N)
Hjälputrymme: O(1)

Sortera arrayen endast inom det givna intervallet: För att hantera sådana typer av problem måste vi bara nämna intervallet i sorteringsfunktionen.
Nedan är implementeringen av ovanstående fall:

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>

>

>

Produktion

Array after sorting : 0 1 2 3 4 5 6 7 8 9>

Tidskomplexitet: O(N log N)

Hjälputrymme: O(1)

Hur man sorterar i en särskild ordning?
Vi kan också skriva vår egen komparatorfunktion och skicka den som en tredje parameter. Denna komparatorfunktion returnerar ett värde; konvertibel till bool, vilket i princip talar om för oss om det godkända första argumentet ska placeras före det godkända andra argumentet eller inte.
Till exempel: I koden nedan, anta att intervall {6,8} och {1,9} skickas som argument i compareInterval-funktionen (jämförarfunktion). Nu som 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; }>

>

>

Produktion

Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>

Tidskomplexiteten för std::sort() är:

linux-filer
  1. Bästa fall – O(N log N)
  2. Genomsnittligt fall – O(N log N)
  3. Värsta fall – O(N log N)

Utrymmes komplexitet: Den kan använda O( log N) hjälputrymme.

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 bool funComparator(T x1, T x2) { // returtyp är bool retur x1<= x2; } void show(int a[], int array_size) { for (int i = 0; i cout << a[i] << ' '; } } int main() { int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int asize = sizeof(a) / sizeof(int); cout << 'The array before sorting is : '; show(a, asize); cout << endl << 'The array after sorting is(asc) :'; sort(a, a + asize); show(a, asize); cout << endl << 'The array after sorting is(desc) :'; sort(a, a + asize, greater ()); visa(a, asize); cout<< endl << 'The array after sorting is(asc but our ' 'comparator class) :'; sort(a, a + asize, Comparator ()); visa(a, asize); cout<< endl << 'The array after sorting is(asc but our ' 'comparator function) :'; sort(a, a + asize, funComparator ); visa(a, asize); returnera 0; }>

>

>

Produktion

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>

Tidskomplexitet: O(N log N)
Hjälputrymme: O(1)