TechCodeview

In questo articolo discuteremo dell'algoritmo Radix Sort. L'ordinamento radicale è l'algoritmo di ordinamento lineare utilizzato per gli interi. Nell'ordinamento radicale viene eseguito un ordinamento cifra per cifra che inizia dalla cifra meno significativa fino a quella più significativa.

Il processo di ordinamento digitale funziona in modo simile all'ordinamento dei nomi degli studenti, secondo l'ordine alfabetico. In questo caso, ci sono 26 radici formate grazie ai 26 alfabeti in inglese. Nel primo passaggio i nomi degli studenti vengono raggruppati secondo l'ordine crescente della prima lettera del loro nome. Successivamente, nel secondo passaggio, i loro nomi vengono raggruppati secondo l'ordine crescente della seconda lettera del loro nome. E il processo continua finché non troviamo l'elenco ordinato.

formica contro esperto

Ora vediamo l'algoritmo del Radix Sort.

Algoritmo

 radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -> 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place 

Funzionamento dell'algoritmo Radix Sort

Ora vediamo il funzionamento dell'algoritmo Radix Sort.

I passaggi utilizzati nell'ordinamento del radix sort sono elencati come segue:

• Per prima cosa dobbiamo trovare l'elemento più grande (supponiamo massimo ) dall'array specificato. Supponiamo 'X' essere il numero di cifre in massimo . IL 'X' si calcola perché bisogna ripercorrere i luoghi significativi di tutti gli elementi.
• Successivamente, esamina uno per uno ciascun luogo significativo. Qui dobbiamo utilizzare qualsiasi algoritmo di ordinamento stabile per ordinare le cifre di ciascuna posizione significativa.

Vediamo ora il funzionamento del radix sort in dettaglio utilizzando un esempio. Per capirlo più chiaramente, prendiamo un array non ordinato e proviamo a ordinarlo utilizzando l'ordinamento digitale. Renderà la spiegazione più chiara e semplice.

Nell'array indicato, l'elemento più grande è 736 che ha 3 cifre in esso. Quindi, il ciclo verrà eseguito fino a tre volte (cioè fino al centinaia di posti ). Ciò significa che sono necessari tre passaggi per ordinare l'array.

Ora, per prima cosa ordina gli elementi sulla base delle cifre delle posizioni unitarie (ad esempio, x = 0 ). Qui stiamo utilizzando l'algoritmo di ordinamento del conteggio per ordinare gli elementi.

Passaggio 1:

Nel primo passaggio l'elenco viene ordinato in base alle cifre al posto dello 0.

Dopo il primo passaggio, gli elementi dell'array sono:

contatti bloccati

Passaggio 2:

In questo passaggio l'elenco viene ordinato in base alle cifre significative successive (cioè le cifre a 10^thposto).

Dopo il secondo passaggio, gli elementi dell'array sono:

Passaggio 3:

In questo passaggio l'elenco viene ordinato in base alle cifre significative successive (ovvero, le cifre a 100^thposto).

Dopo il terzo passaggio, gli elementi dell'array sono:

Ora l'array è ordinato in ordine crescente.

Complessità dell'ordinamento radicale

Ora, vediamo la complessità temporale dell'ordinamento Radix nel caso migliore, medio e peggiore. Vedremo anche la complessità spaziale del Radix sort.

1. Complessità temporale

Migliore complessità del caso -Si verifica quando non è richiesto alcun ordinamento, ovvero l'array è già ordinato. La complessità temporale nel migliore dei casi dell'ordinamento Radix è Ω(n+k) .Complessità media del caso -Si verifica quando gli elementi dell'array sono in ordine confuso, ovvero non correttamente ascendente e non correttamente discendente. La complessità media del tempo di caso dell'ordinamento Radix è θ(nk) .Complessità del caso peggiore -Si verifica quando gli elementi dell'array devono essere ordinati in ordine inverso. Ciò significa che supponiamo di dover ordinare gli elementi dell'array in ordine crescente, ma i suoi elementi sono in ordine decrescente. La complessità temporale nel caso peggiore dell'ordinamento Radix è OK(nk) .

L'ordinamento radicale è un algoritmo di ordinamento non comparativo migliore degli algoritmi di ordinamento comparativo. Ha una complessità temporale lineare che è migliore degli algoritmi comparativi con complessità O(n logn).

2. Complessità spaziale

• La complessità spaziale del Radix sort è O(n + k).

Implementazione del Radix Sort

Vediamo ora i programmi di Radix Sort nei diversi linguaggi di programmazione.

Programma: Scrivere un programma per implementare l'ordinamento Radix in linguaggio C.

 #include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarray(a,n); radixsort(a, n); cout<<'

after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); console.write('

after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are - 
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('

after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>