logo

TechCodeview

std::sort() C++ STL

Mēs esam apsprieduši qsort() valodā C. C++ STL nodrošina līdzīgu funkciju šķirošanu, kas kārto vektoru vai masīvu (vienumus ar nejaušu piekļuvi)

Parasti ir nepieciešami divi parametri, no kuriem pirmais ir masīva/vektora punkts, no kura jāsāk kārtošana, un otrais parametrs ir garums, līdz kuram mēs vēlamies, lai masīvs/vektors tiktu sakārtots. Trešais parametrs nav obligāts, un to var izmantot, piemēram, ja mēs vēlamies kārtot elementus leksikogrāfiski.



Pēc noklusējuma funkcija sort() sakārto elementus augošā secībā.

Zemāk ir vienkārša programma, kas parāda sort () darbību.

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

>

>

Izvade 

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

Laika sarežģītība: O(N log N)
Palīgtelpa: O(1)

Kā kārtot dilstošā secībā?
sort() aizņem trešo parametru, kas tiek izmantots, lai norādītu secību, kādā elementi ir jākārto. Mēs varam nodot lielāku () funkciju, lai kārtotu dilstošā secībā. Šī funkcija veic salīdzināšanu tādā veidā, kas liek priekšā lielākus elementus.

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

>

>

Izvade 

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

Laika sarežģītība: O(N log N)
Palīgtelpa: O(1)

Kārtot masīvu tikai norādītajā diapazonā: Lai risinātu šāda veida problēmas, mums vienkārši jāpiemin diapazons kārtošanas funkcijā.
Zemāk ir aprakstīta iepriekš minētā gadījuma īstenošana:

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> 

>

>

Izvade 

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

Laika sarežģītība: O(N log N)

Palīgtelpa: O(1)

Kā kārtot a īpašs pasūtījums?
Mēs varam arī uzrakstīt savu salīdzinājuma funkciju un nodot to kā trešo parametru. Šī salīdzinājuma funkcija atgriež vērtību; konvertējams uz bool, kas būtībā norāda, vai nodotais pirmais arguments ir jāievieto pirms nodotā ​​otrā argumenta vai nē.
Piemēram: Pieņemsim, ka zemāk esošajā kodā intervāli {6,8} un {1,9} tiek nodoti kā argumenti funkcijā salīdzinātInterval (salīdzinājuma funkcija). Tagad kā 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; }> 

>

>

Izvade 

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

std::sort() laika sarežģītība ir:

mysql mainīt kolonnas veidu
  1. Labākais gadījums — O (N log N)
  2. Vidējais gadījums — O (N log N)
  3. Sliktākais gadījums — O (N log N)

Kosmosa sarežģītība: Tas var izmantot O(log N) palīgtelpu.

C++




#include> #include> using> namespace> std;> template> <>class> T>>> 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) { // atgriešanas veids ir bool return 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 ()); parādīt(a, lielums); cout<< endl << 'The array after sorting is(asc but our ' 'comparator class) :'; sort(a, a + asize, Comparator ()); parādīt(a, lielums); cout<< endl << 'The array after sorting is(asc but our ' 'comparator function) :'; sort(a, a + asize, funComparator ); parādīt(a, lielums); atgriezties 0; }> 

>

>

Izvade 

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>

Laika sarežģītība: O(N log N)
Palīgtelpa: O(1)