Partizioni bilanciate producono log n livelli, ciascuno con Θ(n) lavoro complessivo: Θ(n log n).
Algoritmi di ordinamento · 3/7
Quicksort
Porta ogni pivot nella sua posizione finale e ricorre sulle due partizioni.
Tempo medioΘ(n log n)
MemoriaΘ(log n) medio
StabileNo
In placeSì
Come funziona
Questa simulazione usa la partizione di Lomuto e l’ultimo elemento come pivot: gli elementi ≤ pivot vengono raccolti a sinistra, quelli maggiori restano a destra.
Invariante: Durante la partizione, A[low…i−1] ≤ pivot e A[i…j−1] > pivot; A[j] è il prossimo elemento da classificare.
Simulazione passo passo
Ogni barra rappresenta un elemento. I colori distinguono gli elementi confrontati, il pivot o la chiave, la parte già definitiva e l’area attiva.
Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.
- Confronti
- 0
- Scritture
- 0
- Scambi
- 0
- Passaggio / livello
- 0
attivo
confronto
pivot / chiave
definitivo
Pseudocodice collegato alla simulazione
quickSort(A, low, high)if low ≥ high: returnpivot ← A[high]i ← lowfor j ← low to high − 1if A[j] ≤ pivot: swap A[i], A[j]; i++swap A[i], A[high]quickSort(A, low, i − 1); quickSort(A, i + 1, high)
La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.
Studio della complessità
Con pivot casuale, o input casuale, la profondità attesa è Θ(log n) e il tempo atteso Θ(n log n).
Con pivot sempre minimo o massimo, le dimensioni sono 0 e n−1: T(n)=T(n−1)+Θ(n)=Θ(n²).
Le partizioni avvengono nell’array. Lo stack è Θ(log n) in media e Θ(n) nel caso peggiore; l’algoritmo non è stabile.
Proprietà in breve
La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.
La classificazione considera la versione dell’algoritmo mostrata in questa pagina.
Quando usarlo e che cosa evitare
Buona scelta quando…
Molto rapido su array in memoria grazie a buona località e costanti contenute. Pivot casuale o mediana di tre riducono gli sbilanciamenti.
Errore comune
Scegliere sempre primo o ultimo elemento come pivot senza contromisure è rischioso su input ordinati o avversari.