Algoritmii de sortare sunt un set de instrucțiuni care iau o matrice sau o listă ca intrare și aranjează articolele într-o anumită ordine.

Sortările sunt cel mai frecvent în ordine numerică sau sub formă de ordine alfabetică (numită lexicografică) și pot fi în ordine crescătoare (AZ, 0-9) sau descendentă (ZA, 9-0).

De ce sunt importante algoritmii de sortare

Deoarece sortarea poate reduce adesea complexitatea unei probleme, este un algoritm important în informatică. Acești algoritmi au aplicații directe în algoritmi de căutare, algoritmi de baze de date, metode de divizare și cucerire, algoritmi de structură a datelor și multe altele.

Unele algoritmi de sortare obișnuiți

Unii dintre cei mai comuni algoritmi de sortare sunt:

  • Selecție Sortare
  • Sortare cu bule
  • Sortare prin inserție
  • Merge Sort
  • Sortare rapida
  • Sortare în grămadă
  • Numărare Sortare
  • Radix Sort
  • Sortare cupă

Clasificarea algoritmului de sortare

Algoritmii de sortare pot fi clasificați pe baza următorilor parametri:

  1. Bazat pe numărul de swapuri sau inversiuni Acesta este de câte ori algoritmul schimbă elemente pentru a sorta intrarea. Selection Sort necesită numărul minim de swap-uri.
  2. Bazat pe numărul de comparații Acesta este de câte ori algoritmul compară elemente pentru a sorta intrarea. Folosind Notare Big-O, exemplele de algoritm de sortare enumerate mai sus necesită cel puțin O(nlogn) comparații în cel mai bun caz și O(n^2) comparații în cel mai rău caz pentru majoritatea rezultatelor.
  3. Bazat pe recursivitate sau nerecursiune Unii algoritmi de sortare, cum ar fi Quick Sort, utilizați tehnici recursive pentru a sorta intrarea. Alți algoritmi de sortare, cum ar fi Selection Sort sau Insertion Sort, utilizați tehnici non-recursive. În cele din urmă, un algoritm de sortare, cum ar fi Merge Sort, utilizați atât tehnici recursive, cât și tehnici non-recursive pentru a sorta intrarea.
  4. Pe baza stabilității, se spune că sunt algoritmi de sortare stable dacă algoritmul menține ordinea relativă a elementelor cu chei egale. Cu alte cuvinte, două elemente echivalente rămân în aceeași ordine în ieșirea sortată așa cum erau în intrare.
  5. Insertion sort, Merge Sort, și Bubble Sort sunt stabile
  6. Heap Sort și Quick Sort nu sunt stabile
  7. Pe baza cerinței de spațiu suplimentar se spune că algoritmii de sortare sunt in place dacă necesită o constantă O(1) spațiu suplimentar pentru sortare.
  8. Insertion sort și Quick-sort sunteți in place sortează pe măsură ce mutăm elementele din pivot și nu folosim de fapt o matrice separată, ceea ce NU este cazul în sortare combinată în care dimensiunea intrării trebuie alocată în prealabil pentru a stoca ieșirea în timpul sortării.
  9. Merge Sort este un exemplu de out place sortați, deoarece necesită spațiu de memorie suplimentar pentru operațiunile sale.

Cea mai bună complexitate de timp posibilă pentru orice sortare bazată pe comparație

Orice algoritm de sortare bazat pe comparație trebuie să facă cel puțin nLog2n comparații pentru a sorta matricea de intrare, iar sortarea Heapsort și merge sunt sortimente de comparație asimptotice optime. Acest lucru poate fi ușor dovedit prin trasarea diagramei arborelui decizional.