Triere este una dintre cele mai de bază și utile funcții aplicate datelor. Acesta are ca scop aranjarea datelor într-un mod particular, care poate fi în creștere sau în scădere conform cerințelor. Există o funcție încorporată în C ++ STL sub numele de ‘sort ()’ care ne permite să efectuăm cu ușurință algoritmul de sortare. În acest articol vom explora funcția de sortare în C ++,
Următorii indicatori vor fi acoperiți în acest articol:
- Funcția Sort ()
- Exemplu - Pentru a sorta datele în ordine crescătoare
- Exemplu - Pentru a sorta datele în ordine descrescătoare
- Parțial_sort
Continuăm cu acest articol despre funcția Sortare în C ++
Fel ( ) funcție
Este o funcție încorporată a fișierului antet algoritm, este folosit pentru a sorta containerele ca o matrice, vectori într-o ordine specificată. Pe plan intern această funcție este implementată ca sortare rapidă
Quicksort este un algoritm de divizare și cucerire. Quicksort împarte mai întâi o listă mare de elemente în două sub-liste mai mici: elementele inferioare și elementele superioare. Quicksort apoi sortează recursiv sub-listele.
Pașii sunt următorii:
1. Alegeți un element aleatoriu (de obicei ultimul element), numit pivot, din listă.
2. Reordonați lista astfel încât toate elementele cu valori mai mici decât pivotul să vină înaintea pivotului, în timp ce toate elementele cu valori mai mari decât pivotul să vină după ea și valorile egale să poată merge în orice sens, acest proces este numit operație de partiție.
3. Sortați recursiv sub-lista de elemente mai mici și sub-lista de elemente mai mari, selectați din nou un pivot în sub-listă și împărțiți-le.
Cazul de bază al recursiunii este listele cu dimensiunea zero sau una, care nu trebuie niciodată sortate și astfel prin combinarea acestora ne sortăm lista.
treceți prin referință în java
Quicksort este mai rapid în practică decât alți algoritmi O (n log n), cum ar fi Insertion Sort sau Bubble sort. Quicksort poate fi implementat cu un algoritm de partiționare în loc, ceea ce înseamnă că întreaga sortare se poate face doar cu O (jurnal n) spațiu suplimentar. Quicksort nu este un tip stabil.
Complexitatea sa este următoarea:
Cel mai bun caz - O (n log n)
Cel mai rău caz - O (n ^ 2)
Caz mediu - O (n log n)
Sintaxă:
sortare (primul, ultimul)
Aici,
primul - este indexul (indicatorul) primului element din intervalul care urmează să fie sortat.
last - este indexul (indicatorul) ultimului element din intervalul care urmează să fie sortat.
De exemplu, vrem să sortăm elementele unei matrice ‘arr’ de la 1 la 10 poziții, vom folosi sortare (arr, arr + 10) și va sorta 10 elemente în ordine crescătoare.
Valoare returnată
Nici unul
Complexitate
Media unei complexități de sortare este N * log2 (N), unde N = ultima - prima.
Interval de date
Obiectul din intervalul [primul, ultimul) sunt modificate.
Excepții
Supraîncărcările cu un parametru șablon denumit ExecutionPolicy raportează erorile după cum urmează:
Dacă algoritmul nu reușește să aloce memorie, std :: bad_alloc este aruncat ca o excepție.
Dacă executarea unei funcții invocate ca parte a algoritmului aruncă o excepție std :: terminate.
Continuăm cu acest articol despre funcția Sortare în C ++
Exemplu - Pentru a sorta datele în ordine crescătoare:
#include folosirea spațiului de nume std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' oferă dimensiunea matricei totale, adică mărimea fiecărui caracter * nu. de caractere // deci pentru a obține nr. de caractere // împărțim dimensiunea (matrice) cu dimensiunea oricărui caracter al matricei // aici este matrice [0] sort (matrice, matrice + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 }
Ieșire:
Explicaţie
Din exemplul de mai sus, vedem că funcția sort () implicit sortează o matrice în ordine crescătoare.
Continuăm cu acest articol despre funcția Sortare în C ++
Exemplu - Pentru a sorta datele în ordine descrescătoare:
Pentru a sorta datele matricei în ordine descrescătoare, trebuie să introducem un al treilea parametru care este utilizat pentru a specifica ordinea în care elementele vor fi sortate. Putem folosi funcția „mai mare ()” pentru a sorta datele în ordine descrescătoare.
#includeți utilizarea spațiului de nume std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) sort (matrice, matrice + n, mai mare ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 }
Ieșire:
Exp l o natiune
Aici funcția sort () face o comparație într-un mod care pune elementul mai mare înainte.
Continuăm cu acest articol despre funcția Sortare în C ++
Parțial_sort
C ++ STL ne oferă o funcție de sortare parțială, funcția este similară cu funcția sort (), dar spre deosebire de funcția sort () nu este utilizată pentru sortarea întregului interval, ci este folosită pentru a sorta doar o sub-parte a acestuia. Sortează elementele din intervalul [primul, ultimul), în așa fel încât elementele dinaintea elementului mijlociu sunt sortate în ordine crescătoare, în timp ce elementele după mijloc sunt lăsate așa cum este.
Poate fi folosit pentru a găsi cel mai mare element dacă folosim un obiect funcțional pentru a sorta pentru prima poziție
Exemplu
#include #include #include folosind namespace std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr partial_sort (vec.begin (), vec.begin () + 1, vec.end (), greater ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 }
Ieșire:
planul de monitorizare și control al proiectului
Explicaţie:
Codul de mai sus poate fi folosit pentru a găsi cel mai mare număr dintr-o serie, pentru a găsi cel mai mic număr din serie trebuie doar să eliminăm comanda mai mare.
Astfel am ajuns la sfârșitul acestui articol despre „Funcția de sortare în C ++”. Dacă doriți să aflați mai multe, consultați Java Training de la Edureka, o companie de învățare online de încredere. Edureka’s cursul este conceput pentru a vă instrui atât pentru conceptele Java de bază, cât și pentru cele avansate, împreună cu diverse cadre Java, cum ar fi Hibernate & Spring.
Ai o întrebare pentru noi? Vă rugăm să o menționați în secțiunea de comentarii a acestui blog și vă vom răspunde cât mai curând posibil.