Counting sort
Il counting sort non ordina affatto confrontando i valori. Se sai che ogni valore è un numero intero tra, diciamo, 1 e 40, puoi semplicemente contare quanti ce ne sono di ciascuno e dai conteggi ricavare dove va ognuno. Per un intervallo piccolo, ordinare più in fretta è quasi impossibile.
Contare
Trova il valore più piccolo e quello più grande e crea un contatore per ogni valore compreso, tutti a zero. Leggi la lista una volta dall'inizio alla fine e aggiungi uno al contatore di ogni valore che incontri. Ora i contatori formano un istogramma: quanti 1, quanti 2 e così via. Con n valori e k contatori servono n passi.
Sommare
I valori uguali al più piccolo vengono per primi, quindi il loro blocco inizia al posto 1. Il blocco del valore successivo inizia subito dopo, e così via: ogni blocco inizia dopo la somma di tutti i conteggi precedenti. Questi totali progressivi, detti somme prefisse, trasformano l'istogramma in una mappa della lista ordinata. Servono k passi.
Posizionare
Leggi la lista una seconda volta e sposta ogni valore nel prossimo posto libero del suo blocco. Poiché i valori vengono spostati nell'ordine in cui compaiono, i valori uguali mantengono il loro ordine originale: il counting sort è stabile. Ricopia il buffer e la lista è ordinata. L'app mostra ogni contatore che scende di nuovo man mano che i suoi valori vengono posizionati.
Un esempio
Prendi 4, 1, 3, 4, 2, 1, 4. I contatori da 1 a 4 finiscono a 2, 1, 1 e 3. Sommando si ottengono i blocchi: gli 1 ai posti 1 e 2, il 2 al posto 3, il 3 al posto 4 e i 4 ai posti da 5 a 7. Posizionando i valori in ordine di lista si ottiene 1, 1, 2, 3, 4, 4, 4: 7 valori contati, 14 spostamenti, 4 contatori e nessun confronto.
Quando usarlo
Il lavoro totale cresce con n + k. Quando k è piccolo rispetto a n, come mille voti d'esame da 0 a 100, il counting sort è più veloce di qualsiasi ordinamento per confronto, che richiede circa n log₂ n confronti. Quando l'intervallo è ampio è dispendioso: pochi valori sparsi fino a un milione richiedono un milione di contatori. Il radix sort risolve il problema eseguendo il counting sort una volta per cifra, così ogni passata richiede solo dieci contatori. Harold Seward descrisse il counting sort, insieme al radix sort, nel 1954.
Esploralo
Apri l'app e premi Passo. La striscia tra la lista e la riga del buffer mostra un contatore per valore. Guarda i contatori riempirsi mentre la lista viene letta, i blocchi comparire nel buffer quando i conteggi vengono sommati e i contatori scendere di nuovo man mano che i valori vengono posizionati. Scegli pochi valori distinti per vedere blocchi grandi, oppure inserisci numeri molto distanti per vedere quanti contatori servono per un intervallo ampio.
Domande frequenti
Qual è la complessità temporale del counting sort?
O(n + k) per n valori e k valori possibili, e O(n + k) di memoria aggiuntiva per i contatori e il buffer.
Perché il counting sort non è sempre il più veloce?
Perché il suo costo dipende dall'intervallo dei valori, non solo da quanti sono. Se l'intervallo è molto più ampio della lista, la maggior parte dei contatori resta a zero e tempo e memoria vanno sprecati.
Il counting sort gestisce i numeri negativi?
Sì. I contatori vanno dal valore più piccolo al più grande, quindi sottrai il valore più piccolo per ottenere l'indice di un contatore. L'app fa lo stesso.
Il counting sort è stabile?
Sì, purché i valori vengano spostati in ordine di lista nel prossimo posto libero del loro blocco. Il radix sort si basa su questo.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il counting sort