DAA - Radix Sort

Radix sortè un piccolo metodo che molte persone usano intuitivamente quando alfabetizzano un lungo elenco di nomi. In particolare, l'elenco dei nomi viene prima ordinato in base alla prima lettera di ciascun nome, ovvero i nomi sono organizzati in 26 classi.

Intuitivamente, si potrebbe voler ordinare i numeri sulla cifra più significativa. Tuttavia, l'ordinamento Radix funziona in modo controintuitivo ordinando prima le cifre meno significative. Al primo passaggio, tutti i numeri vengono ordinati sulla cifra meno significativa e combinati in una matrice. Quindi, al secondo passaggio, i numeri interi vengono nuovamente ordinati sulle seconde cifre meno significative e combinati in una matrice e così via.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Analisi

Ogni chiave viene esaminata contemporaneamente per ogni cifra (o lettera se le chiavi sono alfabetiche) della chiave più lunga. Quindi, se la chiave più lunga ham cifre e ci sono n chiavi, radix sort ha ordine O(m.n).

Tuttavia, se guardiamo a questi due valori, la dimensione delle chiavi sarà relativamente piccola rispetto al numero di chiavi. Ad esempio, se abbiamo chiavi a sei cifre, potremmo avere un milione di record diversi.

Qui, vediamo che la dimensione delle chiavi non è significativa e questo algoritmo è di complessità lineare O(n).

Esempio

L'esempio seguente mostra come l'ordinamento Radix opera su un numero di sette cifre.

Ingresso	1 ° Passo	2 ° passaggio	3 ° passaggio
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

Nell'esempio sopra, la prima colonna è l'input. Le colonne rimanenti mostrano l'elenco dopo ordinamenti successivi in ​​posizione di cifre sempre più significative. Il codice per l'ordinamento Radix presuppone che ogni elemento in un arrayA di n elementi ha d cifre, dove cifra 1 è la cifra di ordine più basso e d è la cifra di ordine più alto.