V tem članku bomo razpravljali o algoritmu razvrščanja Radix. Radix sort je algoritem linearnega razvrščanja, ki se uporablja za cela števila. Pri razvrščanju Radix se izvaja razvrščanje po števki, ki se začne od najmanj pomembne števke do najpomembnejše števke.
Postopek razvrščanja po osnovi deluje podobno kot razvrščanje imen študentov po abecednem vrstnem redu. V tem primeru je 26 radiksov, ki nastanejo zaradi 26 abeced v angleščini. Pri prvem prehodu so imena učencev razvrščena po naraščajočem vrstnem redu prve črke njihovih imen. Nato so v drugem prehodu njihova imena razvrščena po naraščajočem vrstnem redu druge črke njihovega imena. In postopek se nadaljuje, dokler ne najdemo razvrščenega seznama.
intellij ideja proti mrku
Zdaj pa si oglejmo algoritem razvrščanja Radix.
Algoritem
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
Delovanje algoritma za razvrščanje Radix
Zdaj pa si oglejmo delovanje algoritma za razvrščanje Radix.
Koraki, uporabljeni pri razvrščanju razvrščanja po korenu, so navedeni na naslednji način -
- Najprej moramo najti največji element (predpostavimo maks ) iz podane matrike. Recimo 'x' biti število števk v maks . The 'x' se izračuna, ker moramo iti skozi pomembna mesta vseh elementov.
- Nato pojdite enega za drugim skozi vsako pomembno mesto. Tukaj moramo uporabiti kateri koli stabilen algoritem za razvrščanje števk vsakega pomembnega mesta.
Zdaj pa si na primeru podrobno oglejmo delovanje razvrščanja po radixu. Da bi to bolj jasno razumeli, vzemimo nerazvrščeno matriko in jo poskusimo razvrstiti z razvrščanjem po osnovi. Tako bo razlaga jasnejša in lažja.
V dani matriki je največji element 736 ki imajo 3 števk v njem. Torej se bo zanka zagnala do trikrat (tj. do na stotine mesto ). To pomeni, da so za razvrščanje matrike potrebni trije prehodi.
Sedaj najprej razvrstite elemente na podlagi mestnih števk enote (tj. x = 0 ). Tukaj uporabljamo algoritem razvrščanja s štetjem za razvrščanje elementov.
Prehod 1:
Pri prvem prehodu je seznam razvrščen na podlagi števk na mestu 0.
Po prvem prehodu so elementi niza -
kakec
Prehod 2:
V tem prehodu je seznam razvrščen na podlagi naslednjih pomembnih števk (tj. števk pri 10thmesto).
Po drugem prehodu so elementi niza -
Prehod 3:
V tem prehodu je seznam razvrščen na podlagi naslednjih pomembnih števk (tj. števk pri 100thmesto).
Po tretjem prehodu so elementi niza -
Zdaj je niz razvrščen v naraščajočem vrstnem redu.
Kompleksnost sortiranja Radix
Zdaj pa poglejmo časovno kompleksnost razvrščanja Radix v najboljšem, povprečnem in najslabšem primeru. Videli bomo tudi prostorsko kompleksnost sorte Radix.
1. Časovna zapletenost
| Ovitek | Časovna zapletenost |
|---|---|
| Najboljši primer | Ω(n+k) |
| Povprečen primer | θ(nk) |
| V najslabšem primeru | O(nk) |
Radix sort je neprimerjalni algoritem za razvrščanje, ki je boljši od primerjalnih algoritmov za razvrščanje. Ima linearno časovno kompleksnost, ki je boljša od primerjalnih algoritmov s kompleksnostjo O(n logn).
2. Kompleksnost prostora
| Kompleksnost prostora | O(n + k) |
| Stabilen | DA |
- Prostorska kompleksnost razvrščanja Radix je O(n + k).
Izvedba sortiranja Radix
Zdaj pa si oglejmo programe sortiranja Radix v različnih programskih jezikih.
Program: Napišite program za izvajanje razvrščanja Radix v jeziku 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;>