In dit artikel bespreken we het Radix-sorteeralgoritme. Radix sort is het lineaire sorteeralgoritme dat wordt gebruikt voor gehele getallen. Bij Radix-sortering wordt cijfer voor cijfer gesorteerd, waarbij wordt gestart van het minst significante cijfer naar het meest significante cijfer.
Het proces van het sorteren van de radix werkt vergelijkbaar met het sorteren van de namen van leerlingen, volgens alfabetische volgorde. In dit geval worden er 26 radix gevormd vanwege de 26 alfabetten in het Engels. Bij de eerste doorgang worden de namen van de leerlingen gegroepeerd volgens de oplopende volgorde van de eerste letter van hun naam. Daarna worden hun namen bij de tweede doorgang gegroepeerd volgens de oplopende volgorde van de tweede letter van hun naam. En het proces gaat door totdat we de gesorteerde lijst vinden.
Kali Linux-terminal
Laten we nu het algoritme van Radix-sortering bekijken.
Algoritme
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
Werking van het Radix-soortalgoritme
Laten we nu eens kijken naar de werking van het Radix-sorteeralgoritme.
De stappen die worden gebruikt bij het sorteren van de radix-sortering worden als volgt weergegeven:
- Eerst moeten we het grootste element vinden (stel maximaal ) uit de gegeven array. Veronderstellen 'X' het aantal cijfers zijn maximaal . De 'X' wordt berekend omdat we de belangrijke plaatsen van alle elementen moeten doorlopen.
- Ga daarna één voor één door elke belangrijke plaats. Hier moeten we een stabiel sorteeralgoritme gebruiken om de cijfers van elke belangrijke plaats te sorteren.
Laten we nu de werking van radix-sortering in detail bekijken aan de hand van een voorbeeld. Om het duidelijker te begrijpen, nemen we een ongesorteerde array en proberen deze te sorteren met behulp van radix sort. Het zal de uitleg duidelijker en gemakkelijker maken.
In de gegeven array is het grootste element 736 Dat heeft 3 cijfers erin. De lus zal dus maximaal drie keer doorlopen (d.w.z. tot de honderden plaats ). Dat betekent dat er drie passages nodig zijn om de array te sorteren.
Sorteer nu eerst de elementen op basis van eenheidscijfers (d.w.z. x = 0 ). Hier gebruiken we het tellende sorteeralgoritme om de elementen te sorteren.
Pas 1:
Bij de eerste doorgang wordt de lijst gesorteerd op basis van de cijfers op de plaats van de 0.
Na de eerste doorgang zijn de array-elementen -
Pas 2:
Bij deze doorgang wordt de lijst gesorteerd op basis van de volgende significante cijfers (d.w.z. cijfers op 10eplaats).
livecricket.is
Na de tweede doorgang zijn de array-elementen -
Pas 3:
Bij deze doorgang wordt de lijst gesorteerd op basis van de volgende significante cijfers (d.w.z. cijfers op 100eplaats).
Na de derde doorgang zijn de array-elementen -
Nu wordt de array in oplopende volgorde gesorteerd.
Radix sorteercomplexiteit
Laten we nu eens kijken naar de tijdscomplexiteit van Radix, gesorteerd in het beste geval, het gemiddelde geval en het slechtste geval. We zullen ook de ruimtecomplexiteit van Radix-soort zien.
1. Tijdcomplexiteit
| Geval | Tijdcomplexiteit |
|---|---|
| Beste geval | Ω(n+k) |
| Gemiddeld geval | θ(nk) |
| Het slechtste geval | O(nk) |
Radix-sortering is een niet-vergelijkend sorteeralgoritme dat beter is dan de vergelijkende sorteeralgoritmen. Het heeft een lineaire tijdscomplexiteit die beter is dan de vergelijkende algoritmen met complexiteit O(n logn).
2. Ruimtecomplexiteit
| Ruimtecomplexiteit | O(n + k) |
| Stal | JA |
- De ruimtecomplexiteit van Radix-soort is O(n + k).
Implementatie van Radix sort
Laten we nu eens kijken naar de programma's van Radix die in verschillende programmeertalen worden gesorteerd.
Programma: Schrijf een programma om Radix sort in C-taal te implementeren.
#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;>