De ce sortare?
Sortarea e una dintre cele mai studiate probleme din informatică. E atât de fundamentală încât majoritatea limbajelor o au în biblioteca standard — dar înțelegerea mecanismelor din spate face diferența între un programator care "scrie cod" și unul care "proiectează sisteme".
QuickSort
QuickSort, inventat de Tony Hoare în 1959, e cel mai utilizat algoritm de sortare în practică.
Cum funcționează
QuickSort e un algoritm divide et impera care funcționează astfel:
- Alege un pivot din array
- Partiționează array-ul astfel încât elementele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta
- Aplică recursiv QuickSort pe cele două sub-array-uri
Complexitate
| Caz | Complexitate | Explicație | |---|---|---| | Cel mai bun | O(n log n) | Pivotul împarte array-ul în jumătăți egale | | Mediu | O(n log n) | Majoritatea cazurilor practice | | Cel mai rău | O(n²) | Pivotul e mereu minimul sau maximul (ex: array deja sortat) |
Optimizări
- Alegerea pivotului: mediana a trei (primul, mijlociu, ultimul)
- Introsort: QuickSort + HeapSort (coboară la O(n log n) în cazul cel mai rău)
- Sortare prin inserție pentru sub-array-uri mici (< 16 elemente)
- Tail recursion: optimizează memoria stivei
Memorie
O(log n) pentru stiva de recursie. Nu e in-place adevărat din cauza recursiei.
MergeSort
MergeSort, inventat de John von Neumann în 1945, e un algoritm stabil și predictibil.
Cum funcționează
- Împarte array-ul în două jumătăți egale
- Sortează recursiv fiecare jumătate
- Interclasează (merge) cele două jumătăți sortate
Complexitate
| Caz | Complexitate | |---|---| | Cel mai bun | O(n log n) | | Mediu | O(n log n) | | Cel mai rău | O(n log n) |
Avantaj: Performanță garantată, indiferent de datele de intrare. Dezavantaj: Necesită O(n) memorie suplimentară pentru interclasare.
Stabilitate
MergeSort este stabil — elementele cu valori egale își păstrează ordinea relativă. QuickSort (în implementarea tipică) nu e stabil.
Variante
- In-place MergeSort: posibil dar complex și lent în practică
- TimSort: hibrid MergeSort + InsertionSort (folosit de Python, Java, Android)
- MergeSort paralel: ușor de paralelizat datorită structurii divide-et-impera
HeapSort
HeapSort, propus de J.W.J. Williams în 1964, folosește un heap binar.
Cum funcționează
- Construiește un max-heap din array-ul nesortat: O(n)
- Extrage maximul (rădăcina heap-ului) și îl plasează la sfârșit: O(log n)
- Reface heap-ul și repetă de n ori: O(n log n)
Complexitate
| Caz | Complexitate | Memorie | |---|---|---| | Toate cazurile | O(n log n) | O(1) in-place |
Avantaj: Memorie constantă și performanță garantată. Dezavantaj: Nu e stabil, și în practică e mai lent decât QuickSort din cauza cache-ului (accesează memoria necontiguu).
Comparație directă
| Caracteristică | QuickSort | MergeSort | HeapSort | |---|---|---|---| | Caz mediu | O(n log n) | O(n log n) | O(n log n) | | Caz rău | O(n²) | O(n log n) | O(n log n) | | Memorie | O(log n) | O(n) | O(1) | | Stabil | Nu | Da | Nu | | Cache-friendly | Da | Da (parțial) | Nu | | Paralelizabil | Mediu | Ușor | Greu | | Folosit în | C++ sort(), C qsort() | Python, Java, Go | Haskell, în embedded |
Recomandări practice
- Trebuie viteză și nu ai limită de memorie? QuickSort (optimizat)
- Trebuie stabilitate și predictibilitate? MergeSort (sau TimSort)
- Memorie limitată? HeapSort (sau Introsort)
- Date mici (< 50 elemente)? InsertionSort — e O(n²) dar constantele sunt atât de mici încât depășește QuickSort
Vezi și
- Big O
- P vs NP
- Algoritmul Minimax
- Metoda Monte Carlo