diskutovali jsme qsort() v C. C++ STL poskytuje podobné třídění funkcí, které třídí vektor nebo pole (položky s náhodným přístupem)
Obecně to vyžaduje dva parametry, první je bod pole/vektoru, odkud má třídění začít, a druhý parametr je délka, do které chceme pole/vektor seřadit. Třetí parametr je volitelný a lze jej použít v případech, kdy chceme prvky třídit lexikograficky.
Ve výchozím nastavení třídí funkce sort() prvky ve vzestupném pořadí.
Níže je jednoduchý program, který ukazuje fungování 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; }> |
>
>Výstup
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9>
Časová náročnost: O(N log N)
Pomocný prostor: O(1)
Jak seřadit sestupně?
sort() přebírá třetí parametr, který se používá k určení pořadí, ve kterém mají být prvky seřazeny. Můžeme předat funkci větší () k řazení v sestupném pořadí. Tato funkce provádí porovnání způsobem, který předkládá větší prvky.
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; }> |
>
>Výstup
Array after sorting : 9 8 7 6 5 4 3 2 1 0>
Časová náročnost: O(N log N)
Pomocný prostor: O(1)
Seřaďte pole pouze v daném rozsahu: Abychom se vypořádali s takovými typy problémů, musíme zmínit rozsah uvnitř funkce řazení.
Níže je implementace výše uvedeného případu:
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> |
>
>Výstup
Array after sorting : 0 1 2 3 4 5 6 7 8 9>
Časová složitost: O(N log N)
Pomocný prostor: O(1)
Jak třídit v a konkrétní objednávka?
Můžeme si také napsat vlastní funkci komparátoru a předat ji jako třetí parametr. Tato funkce komparátoru vrací hodnotu; convertible to bool, což nám v podstatě říká, zda má být předaný první argument umístěn před předaný druhý argument nebo ne.
Například: V níže uvedeném kódu předpokládejme, že intervaly {6,8} a {1,9} jsou předány jako argumenty ve funkci CompareInterval (funkce komparátoru). Nyní jako 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; }> |
>
>Výstup
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]>
Časová složitost std::sort() je:
javascript pro rozevírací seznam
- Nejlepší případ – O(N log N)
- Průměrný případ – O(N log N)
- Nejhorší případ – O(N log N)
Prostorová složitost: Může používat pomocný prostor 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 |
>
>Výstup
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>
Časová náročnost: O(N log N)
Pomocný prostor: O(1)