- Secchio in uso
- Appena spostata
- Ricopiate
- Al loro posto
Radix sort
Il radix sort ordina numeri interi senza mai confrontarne due. Ordina la lista per la cifra delle unità, poi per quella delle decine, poi per quella delle centinaia, spostando ogni volta i valori in dieci secchi e ricopiandoli in ordine. Guarda i secchi riempirsi nella riga sotto la lista, uno spostamento alla volta, e la lista diventare ordinata per sempre più cifre. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere uno spostamento alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. I secchi da 0 a 9 stanno uno accanto all'altro nella riga sotto la lista. I riquadri contano cifre lette, spostamenti e passate. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri fino a 999. 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, oppure inserisci i tuoi numeri interi fino a 999 per vedere la passata delle centinaia.
- Premi Avvia, oppure usa Passo e Indietro per procedere un valore alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
- Segui ogni passata: conta le cifre, sposta ogni valore nel suo secchio, poi ricopia i secchi.
Come funziona il radix sort
Guarda solo l'ultima cifra di ogni numero e ordina la lista in base a quella: metti ogni numero in uno di dieci secchi, da 0 a 9, nell'ordine in cui arrivano, poi ricopia i secchi uno dopo l'altro. Fai lo stesso con la cifra delle decine, poi con quella delle centinaia. Poiché ogni passata mantiene l'ordine dei numeri che hanno una cifra in comune, le passate precedenti decidono ancora il loro ordine, e dopo l'ultima passata tutta la lista è ordinata.
Nessun confronto
Gli ordinamenti per confronto richiedono almeno circa n log₂ n confronti nel caso peggiore, qualunque trucco usino. Il radix sort aggira questo limite leggendo cifre: ogni passata legge una cifra di ogni valore e sposta ogni valore due volte, quindi d cifre richiedono d passate e il lavoro cresce con n · d. Per lunghe liste di chiavi corte conviene: un milione di numeri fino a 999 richiede tre passate, dove un ordinamento per confronto ha bisogno di circa 20 milioni di confronti. Il prezzo è che funziona solo con chiavi fatte di cifre o caratteri, e serve spazio per i secchi.
Domande frequenti
Come funziona il radix sort?
Ordina i numeri per l'ultima cifra, poi per la cifra precedente, e così via fino alla prima. Ogni passata mette i numeri in dieci secchi in base a quella cifra, mantenendo il loro ordine, e ricopia i secchi. Dopo la passata sulla cifra più significativa la lista è ordinata.
Perché partire dall'ultima cifra?
Perché ogni passata è stabile: i numeri con la stessa cifra mantengono l'ordine dato dalle passate precedenti. Così l'ultima passata, sulla prima cifra, decide l'ordine, e i pareggi sono risolti dalle cifre già ordinate. Si chiama radix sort LSD (least significant digit, cifra meno significativa).
Il radix sort è più veloce del quicksort?
Può esserlo, con molte chiavi corte: il suo lavoro cresce con il numero di valori per il numero di cifre, senza n log n. Con pochi valori, chiavi molto lunghe o dati non fatti di cifre, quicksort e merge sort di solito sono più veloci e più semplici.
Che legame ha con il counting sort?
Ogni passata del radix sort è un counting sort su una cifra: conta quanti valori hanno ciascuna cifra, calcola dove inizia ogni secchio e sposta lì i valori in 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