Radix Ord

Un radix o una base è una rappresentazione di un numero che mostra quante cifre sono necessarie per rappresentare un numero posizionale. Ad esempio, per rappresentare il numero binario, il valore Radix è 2 (rappresentiamo il binario con 0 o 1). Per rappresentare il numero decimale, il valore Radix è 10 (rappresentiamo il numero decimale con i numeri da 0 a 9).

Come funziona l'algoritmo di ordinamento Redix

Supponiamo che abbiamo il seguente elenco di array e vogliamo ordinare questo array usando l'ordinamento Radix:

Usiamo altri due concetti in questo algoritmo, che sono:

1. 1. Cifra meno significativa
   2. Cifre più significativa

1. Cifera meno significativa (LSD): Il valore esponente di un numero decimale che è estremamente vicino alla posizione più a destra è indicato come LSD.

Ad esempio, il numero decimale "2563" ha il valore di cifre meno significativo di "3".

2. Cifera più significativa (MSD): MSD è l'esatto inverso dell'LSD. Un valore MSD è la cifra più a sinistra diversa da qualsiasi numero decimale.

Ad esempio, il numero decimale "2563" ha il valore delle cifre più significativo di "2".

Passaggio 1: cerca l'elemento più importante (valore massimo)

Come già sappiamo, questo algoritmo funziona sulle cifre per ordinare i numeri. Quindi, per questo, questo algoritmo richiede il numero massimo di cifre per l'iterazione. Il nostro primo passo è scoprire il numero massimo di elementi in questo array. Dopo aver trovato il valore massimo di un array, dobbiamo contare il numero di cifre in quel numero per le iterazioni.

Passaggio 2: conta il numero di cifre dell'elemento massimo

Dobbiamo contare il numero di cifre dell'elemento massimo di un array perché allora possiamo scoprire quante iterazioni abbiamo bisogno di ordinare l'array.

Quindi, come abbiamo già scoperto, l'elemento massimo è 167 e il numero di cifre è 3. Abbiamo bisogno di tre iterazioni per ordinare l'array.

Passaggio 3: ordinare gli elementi per una cifra meno significativa

La prima disposizione delle cifre viene eseguita dalla cifra meno significativa. Dalla seguente immagine, possiamo vedere che tutte le cifre più piccole e meno significative sono disposte sul lato sinistro. In questo caso, ci concentriamo solo sulla cifra meno significativa.

Un'altra cosa che possiamo notare qui è che alcune cifre vengono ordinate automaticamente, anche se le loro cifre unitarie sono diverse, ma le altre sono le stesse.

Per esempio, I numeri 36 nella posizione dell'indice 7 e il numero 32 nella posizione dell'indice 3 hanno entrambe cifre unitarie diverse ma hanno lo stesso altro numero, che è 3. Ovviamente, il numero 32 viene prima del numero 36. Dopo gli accordi del primo elemento, possiamo vedere che ora, 32 viene prima di 36 che viene automaticamente ordinato.

Passaggio 4: ordinamento degli elementi in base alla cifra successiva (TENS DIFIT)

Ora, organizziamo gli elementi dell'array attraverso la cifra del decimo posto. Come già sappiamo, questo smistamento deve essere finito in 3 iterazioni perché il numero massimo di elementi ha 3 cifre. Questa è la nostra seconda iterazione e possiamo supporre che la maggior parte degli elementi dell'array siano ordinati dopo questa iterazione.

I risultati indicati mostrano che la maggior parte degli elementi dell'array sono già ordinati (sotto i 100). Se avessimo solo due cifre come il nostro numero massimo, sono sufficienti solo due iterazioni per ottenere l'array ordinato.

Passaggio 5: ordinare gli elementi in base alla cifra più significativa

Ora inseriamo la terza iterazione in base alla cifra più significativa (centinaia di posti). Questa iterazione ordina gli elementi a tre cifre dell'array. Dopo questa iterazione, tutti gli elementi dell'array sono in ordine ordinato.

Dopo aver organizzato gli elementi in base all'MSD, il nostro array è ora completamente ordinato.

Abbiamo capito i concetti dell'algoritmo di ordinamento Radix. Ma abbiamo bisogno di un altro algoritmo per implementare l'ordinamento di Radix, e questo è il Contare l'algoritmo di ordinamento. Capiamo questo Contare l'algoritmo di ordinamento.

Contare l'algoritmo di ordinamento

Ora spieghiamo ogni fase dell'algoritmo di conteggio.

L'array fornito è il nostro array di input e i numeri che sono mostrati sopra l'array sono i numeri dell'indice degli elementi corrispondenti.

Passaggio 1: cerca l'elemento massimo

Il primo passo nell'algoritmo di ordinamento di conteggio è cercare l'elemento massimo in tutto l'array. Il modo migliore per cercare l'elemento massimo è attraversare l'intero array e confrontare gli elementi in ciascuna iterazione: l'elemento di valore maggiore viene aggiornato fino alla fine dell'array.

Durante il primo passaggio, abbiamo scoperto che l'elemento massimo è 9 nella posizione dell'indice 8.

Passaggio 2: crea una nuova serie di dimensioni comparabili

Creiamo una nuova serie di dimensioni simili. Come già sappiamo, il valore massimo dell'array è 9, quindi ci saranno un totale di 10 elementi. Di conseguenza, abbiamo bisogno di una dimensione massima dell'array di + 1.

Come possiamo vedere nell'immagine precedente, abbiamo una dimensione totale dell'array di 10 con valori di 0. Nel passaggio successivo, riempiamo questo array di conteggi con elementi ordinati.

Passaggio 3: riempire il nuovo array in base alla frequenza di ciascun elemento

In questo passaggio, contiamo ogni elemento e, in base alla loro frequenza, riempire i valori corrispondenti nell'array.

Per esempio, Come possiamo vedere, l'elemento 6 è presente due volte nell'array di input. Quindi, inseriamo il valore di frequenza di 2 all'indice 6.

Passaggio 4: determinare la frequenza cumulativa

Ora, contiamo la frequenza cumulativa dell'array riempito. Questa frequenza cumulativa viene utilizzata in seguito per ordinare l'array di input.

Possiamo calcolare la frequenza cumulativa aggiungendo il valore corrente al valore dell'indice precedente, come mostrato nella seguente schermata:

L'ultimo valore dell'array nell'array cumulativo deve essere il numero totale di elementi.

Passaggio 5: ordinamento dell'array per frequenza commutativa

Ora, utilizziamo l'array di frequenza cumulativa per mappare ogni elemento dell'array per produrre un array ordinato.

Per esempio, il primo elemento nell'array 5 che scegliamo. Quindi, il corrispondente valore di frequenza cumulativa all'indice 5 che ha un valore di 7. Diminuiamo il valore di 1 e ne abbiamo 6. Posizioniamo il valore 5 nell'indice nella posizione 6 e riduciamo anche la frequenza cumulativa all'indice 5 di 1.

La frequenza cumulativa è all'indice 5 dopo essere stata decrementata da uno.

Comprendiamo questo concetto con un altro esempio.

L'elemento successivo nell'array è 2. Scegliamo il valore dell'indice di 2 nell'array di frequenza commutativa. Diminuiamo il valore all'indice 2 e otteniamo 1. Posizioniamo l'elemento array 2 nella posizione dell'indice 1. Alla fine, diminuiamo il valore di frequenza all'indice 2 per 1, come mostrato nella seguente schermata:

Dall'array ordinato precedente, possiamo vedere che viene lasciato solo un posto prima di 2 (posizione indice 1) e un valore inferiore a 2 nell'array originale, che è 1. Quindi, va nel modo giusto di ordinare l'array.

Non dobbiamo ricordare di ridurre il valore cumulativo ad ogni iterazione. Dopo due delle precedenti iterazioni, l'array cumulativo sembra le seguenti:

Passaggio 6: Array finale

Eseguiamo il passaggio 5 fino a quando ogni elemento di array non viene riempito nell'array ordinato. Dopo che è riempito, il nostro array sembra così:

Programma C ++ per l'algoritmo di ordinamento Radix

Questo esempio si basa sulla spiegazione in questo tutorial sui suggerimenti Linux

#includere
Utilizzo dello spazio dei nomi std;
void radixsortalgo (int a [], int size_of_a)
// Nel primo passaggio (passaggio 1), finiamo il valore massimo nell'array.
int
per (int i = 1; iMaximumnumber = max (Maximumnumber, a [i]);

// Nel secondo passaggio (passaggio 2), stiamo calcolando il numero di cifre di
// L'elemento massimo dell'array
int digitsCount = 0;
while (Maximumnumber> 0)
DigitsCount ++;
massimo /= 10;

// Ora stiamo aggiornando un nuovo array (passaggi 3,4 e 5)
per (int i = 0; iint pwr = pow (10, i);
int new_a [size_of_a];
// Questo è un Count_array che viene utilizzato per l'array di conteggio
// per ordinare le cifre da 0 a 9.
int count_array [10];
memset (count_array, 0, sizeof (count_array));
// Calcolo della frequenza di ciascun elemento dell'array
per (int j = 0; jint num = (a [j]/pwr) % 10;
count_array [num] ++;

// questa è una frequenza comulativa
per (int j = 1; j<10;j++)
count_array [j] += count_array [j-1];

// stiamo mappando l'array di frequenza con ogni elemento
// dell'array per scoprire la posizione desiderata nell'array aggiornato
for (int j = size_of_a-1; j> = 0; j-)
int num = (a [j]/pwr) % 10;
new_a [count_array [num] -1] = a [j];
count_array [num]-;

// Ora stiamo aggiornando l'array con il nuovo array
per (int j = 0; ja [j] = new_a [j];

// Infine, stampiamo il risultato dell'array ordinato
per (int j = 0; jcout<cout<
int main ()
// Questo array di valori verrà ordinato usando l'algoritmo di ordinamento Radix.
int a [] = 155, 10, 51, 38, 16, 811, 755, 3, 91, 6;
// stiamo calcolando le dimensioni dell'array
int size_of_a = sizeof (a)/sizeof (size_of_a);
// chiamando al metodo dell'algoritmo di ordinamento radix
radixsortalgo (a, size_of_a);
Ritorno 1;

Output dall'esecuzione di C+ RADIX

Linuxhint@desktop: ~ $ ./radix
3 6 10 16 38 51 91 155 755 811
Linuxhint@desktop: ~ $

Complessità temporale dell'algoritmo di ordinamento radix

Calcoliamo la complessità del tempo dell'algoritmo di ordinamento Radix.

Passaggio 1: per calcolare il numero massimo di elementi nell'intero array, attraversiamo l'intero array. Quindi, il tempo totale richiesto è O (n).

Passaggio 2: supponiamo che le cifre totali nel numero massimo siano k. Quindi, il tempo totale impiegato per calcolare il numero di cifre in un numero massimo è O (k).

Passaggi da 3 a 5: questi passaggi funzionano sulle cifre stesse, quindi impiegano volte a (k) insieme al conteggio dell'algoritmo di ordinamento ad ogni iterazione - o (k * n).

Di conseguenza, la complessità del tempo totale è O (k * n).

Conclusione

Abbiamo studiato l'algoritmo di ordinamento e di conteggio di Radix. Esistono diversi tipi di algoritmi di smistamento disponibili sul mercato. Il miglior algoritmo dipende anche dai requisiti. Non è facile dire quale algoritmo sia il migliore. Ma sulla base della complessità del tempo, stiamo cercando di capire il miglior algoritmo. E sulla base di questo, Radix Ord è anche uno dei migliori algoritmi per l'ordinamento.