Confronti
Scambi
Partizioni

  • Parte in corso di partizione
  • Pivot
  • Confrontate
  • Scambiate
  • Al loro posto

Scopri di più sul quicksort

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

  1. Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
  2. 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.
  3. 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