In diesem Artikel besprechen wir den Radix-Sortieralgorithmus. Radix-Sortierung ist der lineare Sortieralgorithmus, der für ganze Zahlen verwendet wird. Bei der Radix-Sortierung wird eine Ziffern-für-Ziffern-Sortierung durchgeführt, die von der niedrigstwertigen Ziffer zur höchstwertigen Ziffer beginnt.
Der Prozess der Basissortierung funktioniert ähnlich wie die Sortierung der Schülernamen in alphabetischer Reihenfolge. In diesem Fall werden aufgrund der 26 Alphabete im Englischen 26 Radix gebildet. Im ersten Durchgang werden die Namen der Studierenden nach aufsteigender Reihenfolge des Anfangsbuchstabens ihres Namens gruppiert. Danach werden ihre Namen im zweiten Durchgang entsprechend der aufsteigenden Reihenfolge des zweiten Buchstabens ihres Namens gruppiert. Und der Prozess wird fortgesetzt, bis wir die sortierte Liste finden.
Zimt vs. Mate
Sehen wir uns nun den Algorithmus der Radix-Sortierung an.
Algorithmus
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
Funktionsweise des Radix-Sortieralgorithmus
Sehen wir uns nun die Funktionsweise des Radix-Sortieralgorithmus an.
Die beim Sortieren der Basissortierung verwendeten Schritte sind wie folgt aufgeführt:
- Zuerst müssen wir das größte Element finden (angenommen max ) aus dem angegebenen Array. Vermuten 'X' sei die Anzahl der Ziffern in max . Der 'X' wird berechnet, weil wir die signifikanten Stellen aller Elemente durchgehen müssen.
- Gehen Sie danach jeden wichtigen Ort nacheinander durch. Hier müssen wir einen beliebigen stabilen Sortieralgorithmus verwenden, um die Ziffern jeder signifikanten Stelle zu sortieren.
Sehen wir uns nun anhand eines Beispiels die Funktionsweise der Radix-Sortierung im Detail an. Um es besser zu verstehen, nehmen wir ein unsortiertes Array und versuchen, es mithilfe der Basissortierung zu sortieren. Dadurch wird die Erklärung klarer und einfacher.
Im angegebenen Array ist das größte Element 736 die haben 3 Ziffern darin. Die Schleife wird also bis zu dreimal durchlaufen (d. h. bis zum Hunderterplatz ). Das bedeutet, dass zum Sortieren des Arrays drei Durchgänge erforderlich sind.
Sortieren Sie nun zunächst die Elemente auf der Grundlage der Einheitsstellenziffern (d. h. x = 0 ). Hier verwenden wir den Zählsortieralgorithmus, um die Elemente zu sortieren.
Durchgang 1:
Im ersten Durchgang wird die Liste anhand der Ziffern an der Nullstelle sortiert.
Nach dem ersten Durchgang sind die Array-Elemente -
Durchgang 2:
In diesem Durchgang wird die Liste auf der Grundlage der nächsten signifikanten Ziffern (d. h. Ziffern bei 10) sortiertThOrt).
Nach dem zweiten Durchgang sind die Array-Elemente -
Durchgang 3:
In diesem Durchgang wird die Liste auf der Grundlage der nächsten signifikanten Ziffern (d. h. Ziffern bei 100) sortiertThOrt).
Nach dem dritten Durchgang sind die Array-Elemente -
Jetzt wird das Array in aufsteigender Reihenfolge sortiert.
Komplexität der Radix-Sortierung
Sehen wir uns nun die zeitliche Komplexität der Radix-Sortierung im besten, durchschnittlichen und schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Radix-Sortierung sehen.
1. Zeitkomplexität
| Fall | Zeitkomplexität |
|---|---|
| I'm besten fall | Ω(n+k) |
| Durchschnittlicher Fall | θ(nk) |
| Schlimmsten Fall | O(nk) |
Die Radix-Sortierung ist ein nicht vergleichender Sortieralgorithmus, der besser ist als die vergleichenden Sortieralgorithmen. Die lineare Zeitkomplexität ist besser als die Vergleichsalgorithmen mit der Komplexität O(n logn).
Listenknoten Java
2. Raumkomplexität
| Weltraumkomplexität | O(n + k) |
| Stabil | JA |
- Die räumliche Komplexität der Radix-Sortierung beträgt O(n + k).
Implementierung der Radix-Sortierung
Sehen wir uns nun die Programme von Radix in verschiedenen Programmiersprachen an.
Programm: Schreiben Sie ein Programm zur Implementierung der Radix-Sortierung in der Sprache 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;>