En aquest article, parlarem de l'algoritme d'ordenació de Radix. L'ordenació per radi és l'algorisme d'ordenació lineal que s'utilitza per als nombres enters. En l'ordenació Radix, es realitza una ordenació dígit per dígit que s'inicia des del dígit menys significatiu fins al dígit més significatiu.
El procés d'ordenació radix funciona de manera similar a l'ordenació dels noms dels estudiants, segons l'ordre alfabètic. En aquest cas, hi ha 26 radix formades a causa dels 26 alfabets en anglès. En la primera passada, els noms dels alumnes s'agrupen segons l'ordre ascendent de la primera lletra dels seus noms. Després d'això, en la segona passada, els seus noms s'agrupen segons l'ordre ascendent de la segona lletra del seu nom. I el procés continua fins que trobem la llista ordenada.
barra d'eines d'accés ràpid de ms word
Ara, vegem l'algoritme de l'ordenació Radix.
Algorisme
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
Funcionament de l'algoritme d'ordenació Radix
Ara, vegem el funcionament de l'algoritme d'ordenació de Radix.
Els passos utilitzats en l'ordenació de l'ordenació radix s'enumeren de la següent manera:
- Primer, hem de trobar l'element més gran (suposem màx ) de la matriu donada. Suposem 'x' sigui el nombre de dígits màx . El 'x' es calcula perquè hem de recórrer els llocs significatius de tots els elements.
- Després d'això, recorreu un per un cada lloc significatiu. Aquí, hem d'utilitzar qualsevol algorisme d'ordenació estable per ordenar els dígits de cada lloc significatiu.
Ara vegem el funcionament de l'ordenació radix en detall utilitzant un exemple. Per entendre-ho més clarament, agafem una matriu no ordenada i provem d'ordenar-la utilitzant l'ordenació radix. Farà l'explicació més clara i fàcil.
A la matriu donada, l'element més gran és 736 això té 3 dígits en ella. Per tant, el bucle s'executarà fins a tres vegades (és a dir, fins al centenars de llocs ). Això vol dir que calen tres passades per ordenar la matriu.
Ara, primer ordeneu els elements en funció dels dígits del lloc de la unitat (és a dir, x = 0 ). Aquí, estem utilitzant l'algorisme d'ordenació de recompte per ordenar els elements.
Passat 1:
A la primera passada, la llista s'ordena en funció dels dígits al lloc del 0.
Després de la primera passada, els elements de la matriu són -
Passat 2:
En aquesta passada, la llista s'ordena en funció dels següents dígits significatius (és a dir, dígits a 10thlloc).
Després de la segona passada, els elements de la matriu són -
10 de 100
Passat 3:
En aquesta passada, la llista s'ordena en funció dels següents dígits significatius (és a dir, dígits a 100thlloc).
Després de la tercera passada, els elements de la matriu són -
Ara, la matriu s'ordena en ordre ascendent.
Complexitat d'ordenació de radix
Ara, vegem la complexitat temporal de l'ordenació de Radix en el millor dels casos, el cas mitjà i el pitjor dels casos. També veurem la complexitat espacial del tipus Radix.
1. Complexitat temporal
| Caixa | Complexitat temporal |
|---|---|
| Millor cas | Ω(n+k) |
| Cas mitjà | θ(nk) |
| Pitjor dels casos | O(nk) |
Radix sort és un algorisme d'ordenació no comparatiu que és millor que els algorismes d'ordenació comparativa. Té una complexitat temporal lineal que és millor que els algorismes comparatius amb complexitat O(n logn).
2. Complexitat espacial
| Complexitat espacial | O(n + k) |
| Estable | SÍ |
- La complexitat espacial de l'ordenació Radix és O(n + k).
Implementació de l'ordenació Radix
Ara, anem a veure els programes d'ordenació de Radix en diferents llenguatges de programació.
Programa: Escriu un programa per implementar l'ordenació Radix en llenguatge 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'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;>