Quicksort este un algoritm de sortare "divide and conquer" care alege o pivot, partiționează elementele în cele mai mici și mai mari decât ea, și apoi sortează recursiv fiecare parte. Medie O(n log n), cel mai rău caz O(n²).
Partiționarea plasează pivotul în poziția finală sortată; totul la stânga este mai mic, totul la dreapta este mai mare. Repetă recursiv pe ambele părți.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(Partiționarea in-place se folosește în practică pentru a economisi memorie.)
| Caz | Timp | Cauză |
|---|---|---|
| Cel mai bun/Mediu | O(n log n) | partiții echilibrate |
| Cel mai rău | O(n²) | deja sortat cu pivot slab |
Quicksort in-place folosește O(log n) spațiu de stivă.
De obicei cel mai rapid în practică datorită prieteniei cu cache-ul și overhead scăzut, și este in-place. Cel mai rău caz O(n²) se evită cu o pivotă randomizată sau median-of-three. Nu este stabil.
Quicksort este implicit în multe biblioteci standard datorită vitezei excelente în cazul mediu și utilizării scăzute a memoriei.
Înțelegerea de ce alegerea pivotei determină cel mai rău caz O(n²) predă o lecție esențială: cazul mediu și cel mai rău pot diverge brusc.
Este un subiect favorit la interviuri tocmai datorită acestei nuanțe.