- Parte in corso di partizione
- Pivot
- Confrontate
- Scambiate
- Al loro posto
Quicksort
Il quicksort sceglie un pivot, sposta prima di esso ogni valore più piccolo e dopo di esso tutti gli altri, poi ordina i due lati allo stesso modo. Dopo ogni partizione il pivot è al suo posto definitivo. Scegli la regola del pivot, avvia l'ordinamento a qualsiasi velocità o procedi un confronto alla volta, e scopri perché un pivot sbagliato su una lista ordinata rende lento il quicksort. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. I riquadri contano confronti, scambi e partizioni. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri, e come viene scelto il pivot. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
- Premi Avvia, oppure usa Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
- Scegli la regola del pivot: l'ultimo valore, il valore centrale, un valore casuale o la mediana di tre. Provale tutte su una lista ordinata.
Come funziona il quicksort
Scegli un valore della parte da ordinare come pivot e spostalo in fondo. Scorri gli altri valori da sinistra a destra; ognuno più piccolo del pivot viene scambiato in una parte sinistra che cresce dall'inizio. Poi scambia il pivot subito dopo la parte sinistra. Tutto ciò che sta prima è ora più piccolo e niente di ciò che sta dopo lo è, quindi il pivot è al suo posto definitivo. Ordina allo stesso modo la parte prima e la parte dopo, finché ogni parte contiene un solo valore.
Perché il pivot conta
Quando il pivot cade vicino al centro, ogni partizione dimezza il problema e i confronti crescono come n log n: per 40 valori casuali, circa 190. Quando il pivot è il valore più piccolo o più grande, un lato è vuoto e l'altro contiene tutto il resto. Con l'ultimo valore come pivot questo succede a ogni passo su una lista ordinata o inversa, e l'ordinamento richiede n(n − 1)/2 confronti, 780 per 40 valori. Un pivot casuale o la mediana tra il primo, il centrale e l'ultimo valore lo evita nella pratica.
Domande frequenti
Come funziona il quicksort?
Sceglie un pivot, partiziona la lista in modo che i valori più piccoli vengano prima del pivot e gli altri dopo, poi ordina entrambi i lati con il quicksort. Dopo ogni partizione il pivot è al suo posto definitivo.
Perché il quicksort è lento su una lista ordinata?
Con il primo o l'ultimo valore come pivot, una lista ordinata dà sempre come pivot il valore più piccolo o più grande. Un lato della partizione resta quindi vuoto, ogni partizione toglie un solo valore e l'ordinamento richiede n(n − 1)/2 confronti. Un pivot casuale o la mediana di tre risolve il problema nella pratica.
Il quicksort è più veloce del merge sort?
Spesso, nella pratica: ordina sul posto, non ha bisogno di un buffer e il suo ciclo interno è molto semplice. In media fa un po' più confronti del merge sort, e il suo caso peggiore è n², mentre il merge sort è sempre n log n. Gli ordinamenti delle librerie, come l'introsort, partono con il quicksort e passano all'heap sort se le divisioni diventano troppo sbilanciate.
Il quicksort è stabile?
No. Una partizione scambia valori su lunghe distanze, quindi valori uguali possono cambiare ordine.
I miei numeri vengono inviati da qualche parte?
No. L'ordinamento avviene nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor