Quicksort è un ordinamento divide-and-conquer che sceglie un pivot, partiziona gli elementi in quelli più piccoli e più grandi di esso, quindi ordina ricorsivamente ogni lato. Media O(n log n), caso peggiore O(n²).
Il partizionamento posiziona il pivot nella sua posizione finale ordinata; tutto a sinistra è più piccolo, tutto a destra è più grande. Ricorri su entrambi i lati.
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]
(Il partizionamento in-place viene utilizzato in pratica per risparmiare memoria.)
| Caso | Tempo | Causa |
|---|---|---|
| Migliore/Media | O(n log n) | partizioni equilibrate |
| Peggiore | O(n²) | già ordinato con pivot non ottimale |
Il quicksort in-place utilizza O(log n) spazio stack.
Solitamente il più veloce in pratica grazie alla cache friendliness e al basso overhead, ed è in-place. Il caso peggiore O(n²) si evita con un pivot randomizzato o mediana-di-tre. Non è stabile.
Il quicksort è quello predefinito in molte librerie standard grazie alla sua eccellente velocità nel caso medio e al basso uso di memoria.
Capire perché la scelta del pivot causa il caso peggiore O(n²) insegna una lezione fondamentale: il caso medio e il caso peggiore possono divergere drasticamente.
È un argomento preferito nei colloqui proprio per quella sfumatura.