- In conteggio
- Appena spostata
- Al loro posto
Counting sort
Il counting sort funziona quando i valori sono numeri interi in un intervallo piccolo. Tiene un contatore per ogni valore possibile, conta quante volte compare ciascuno e da quei conteggi sa esattamente dove va ogni valore. Guarda i contatori riempirsi mentre la lista viene letta, poi svuotarsi di nuovo mentre ogni valore entra nel suo blocco, uno spostamento alla volta. 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. La striscia tra la lista e la riga del buffer contiene un contatore per ogni valore. I riquadri mostrano i valori contati, gli spostamenti e i contatori. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri. 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. Prova una lista con pochi valori distinti.
- 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.
- Guarda i contatori: si riempiono mentre la lista viene letta, poi scendono man mano che ogni valore viene posizionato.
Come funziona il counting sort
Crea un contatore per ogni valore dal più piccolo al più grande. Leggi la lista una volta e aggiungi uno al contatore di ogni valore che incontri. Poi somma i conteggi a partire dal valore più piccolo: il blocco di un valore inizia subito dopo tutti i valori più piccoli. Infine scorri di nuovo la lista, sposta ogni valore nel prossimo posto libero del suo blocco e ricopia il risultato.
Veloce su un intervallo piccolo
Il counting sort legge la lista due volte e scorre i contatori una volta, quindi il suo lavoro cresce con n + k: il numero di valori più il numero di contatori. Per molti valori in un intervallo piccolo, come voti d'esame da 0 a 100 o età, batte qualsiasi ordinamento per confronto. Per un intervallo ampio spreca tempo e memoria in contatori che nessuno usa: tre valori sparsi da 1 a 1.000.000 richiederebbero un milione di contatori. È anche il passaggio che il radix sort ripete per ogni cifra.
Domande frequenti
Come funziona il counting sort?
Conta quante volte compare ciascun valore, somma i conteggi per trovare dove inizia il blocco di ogni valore, poi sposta ogni valore direttamente nel prossimo posto libero del suo blocco. Non confronta mai due valori.
Quando conviene usare il counting sort?
Quando i valori sono numeri interi, o si possono trasformare in interi, e l'intervallo dal più piccolo al più grande non è molto più ampio del numero di valori: voti, età, piccoli codici. Allora richiede un tempo proporzionale a n + k.
Il counting sort è stabile?
Sì, quando i valori vengono spostati in ordine di lista nel prossimo posto libero del loro blocco, come qui. È questo che permette al radix sort di usarlo per ogni cifra.
Perché non scrivere semplicemente ogni valore tante volte quante è stato contato?
Per semplici numeri funziona, ed è persino più semplice. Ma i dati reali di solito contengono più della sola chiave, come un nome accanto a ogni voto, e scrivendo le chiavi contate andrebbe perso. Spostare gli elementi stessi tiene tutto insieme.
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