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.