Quicksort
Il quicksort è uno degli algoritmi di ordinamento più usati. Sceglie un pivot, divide la lista tra i valori più piccoli del pivot e gli altri, e ordina i due lati allo stesso modo. Nella pratica è veloce e non richiede una lista aggiuntiva, ma quanto sia veloce dipende dal pivot.
L'idea
Scegli un valore come pivot. Riordina la lista in modo che ogni valore più piccolo del pivot venga prima di esso e ogni altro valore dopo. Questo riordinamento si chiama partizione, e lascia il pivot esattamente dove deve stare nella lista ordinata. I due lati sono ora problemi indipendenti: ordina ciascuno con il quicksort. Un lato con un solo valore o nessuno è già ordinato.
La partizione, passo dopo passo
L'app usa la partizione di Lomuto. Il pivot viene spostato in fondo alla parte. Un indicatore parte dall'inizio: tutto ciò che sta prima è più piccolo del pivot. Ogni altro valore viene confrontato con il pivot; se è più piccolo, viene scambiato nella posizione dell'indicatore e l'indicatore avanza di un posto. Alla fine il pivot viene scambiato nella posizione dell'indicatore. Prendi 5, 1, 4, 2, 8 con l'ultimo valore come pivot: tutti e quattro i valori sono più piccoli di 8, quindi 8 resta in fondo. La parte 5, 1, 4, 2 viene partizionata attorno a 2, il che dà 1, 2, 4, 5, e 4, 5 attorno a 5. In tutto 8 confronti, 2 scambi e 3 partizioni.
Pivot buoni e cattivi
Se ogni pivot cadesse al centro, ogni partizione dimezzerebbe il problema, e l'ordinamento richiederebbe circa n log₂ n confronti. Su una lista casuale i pivot sono raramente perfetti ma di solito abbastanza buoni: per 40 valori casuali l'app conta circa 190 confronti. Il caso peggiore si ha quando il pivot è sempre il valore più piccolo o più grande. Con l'ultimo valore come pivot, una lista già ordinata, o inversa, fa proprio questo: ogni partizione toglie solo il pivot, e l'ordinamento richiede n(n − 1)/2 confronti, 780 per 40 valori.
Scegliere il pivot
Un pivot casuale rende il caso peggiore estremamente improbabile per qualsiasi input, perché nessun ordine particolare può ingannarlo. La mediana di tre, il valore di mezzo tra il primo, il centrale e l'ultimo elemento, costa poco e gestisce bene le liste ordinate e inverse. Prova entrambi su una lista ordinata nell'app: i confronti scendono da 780 a circa 150. Molti valori uguali sono un problema diverso: finiscono tutti dallo stesso lato del pivot. Una partizione a tre vie, che tiene i valori uguali al pivot in una parte centrale, risolve il problema.
Storia e uso
Tony Hoare inventò il quicksort nel 1959 e lo pubblicò nel 1961. La sua partizione scorre da entrambe le estremità e fa meno scambi; la versione più semplice di Lomuto, mostrata qui, si è diffusa grazie ai libri di testo. Il quicksort ordina sul posto e il suo ciclo interno è molto breve, quindi nella pratica è di solito più veloce del merge sort, anche se non è stabile. L'introsort, l'ordinamento della libreria standard del C++, esegue il quicksort e passa all'heap sort se le partizioni diventano troppo sbilanciate, così il suo caso peggiore resta n log n.
Esploralo
Apri l'app e premi Passo. La parte in corso di partizione è ombreggiata, il pivot ha un suo colore, e la linea tratteggiata segna la fine della parte sinistra, quella dei valori più piccoli del pivot. Ogni pivot diventa verde quando raggiunge il suo posto definitivo. Scegli una lista ordinata e l'ultimo valore come pivot, poi passa alla mediana di tre e confronta i contatori.
Domande frequenti
Qual è la complessità temporale del quicksort?
O(n log n) in media e con buoni pivot, O(n²) nel caso peggiore. Ordina sul posto; la ricorsione richiede O(log n) di memoria aggiuntiva se il lato più piccolo viene ordinato per primo.
Qual è la differenza tra la partizione di Lomuto e quella di Hoare?
Lomuto usa un solo indicatore e scorre da sinistra a destra, il che è facile da seguire ed è ciò che mostra questa app. Hoare scorre dalle due estremità l'una verso l'altra e scambia le coppie che stanno dal lato sbagliato, il che in media richiede circa tre volte meno scambi.
Perché il quicksort è lento quando molti valori sono uguali?
I valori uguali al pivot finiscono tutti dallo stesso lato, quindi una lista con pochi valori distinti si divide in modo sbilanciato, e una lista di valori uguali è pessima quanto il caso peggiore. Una partizione a tre vie che raccoglie al centro i valori uguali al pivot lo evita.
Il quicksort è stabile?
No. Gli scambi durante una partizione spostano i valori su lunghe distanze, quindi valori uguali possono cambiare ordine.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il quicksort