Šajā rakstā mēs apspriedīsim Radix kārtošanas algoritmu. Radix šķirošana ir lineārās šķirošanas algoritms, ko izmanto veseliem skaitļiem. Radix kārtošanā tiek veikta šķirošana pa cipariem, kas tiek sākta no vismazāk nozīmīgākā cipara līdz visnozīmīgākajam ciparam.
Radix kārtošanas process darbojas līdzīgi kā skolēnu vārdu šķirošana alfabētiskā secībā. Šajā gadījumā angļu valodā ir izveidoti 26 radiksi, pateicoties 26 alfabētiem. Pirmajā piegājienā skolēnu vārdi tiek grupēti atbilstoši viņu vārda pirmā burta augošajai secībai. Pēc tam otrajā piegājienā viņu vārdi tiek grupēti atbilstoši viņu vārda otrā burta augošajai secībai. Un process turpinās, līdz atrodam sakārtoto sarakstu.
dfa automātu piemēri
Tagad apskatīsim Radix kārtošanas algoritmu.
Algoritms
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
Radix šķirošanas algoritma darbība
Tagad apskatīsim Radix šķirošanas algoritma darbību.
Darbības, kas tiek izmantotas radix šķirošanas kārtošanai, ir uzskaitītas šādi:
- Pirmkārt, mums ir jāatrod lielākais elements (pieņemsim maks ) no dotā masīva. Pieņemsim 'x' ir ciparu skaits maks . The 'x' tiek aprēķināts, jo mums jāiet cauri visu elementu nozīmīgajām vietām.
- Pēc tam izejiet cauri katrai nozīmīgai vietai. Šeit mums ir jāizmanto jebkurš stabils kārtošanas algoritms, lai sakārtotu katras nozīmīgas vietas ciparus.
Tagad aplūkosim radix kārtošanas darbību, izmantojot piemēru. Lai to saprastu skaidrāk, ņemsim nešķirotu masīvu un mēģināsim to sakārtot, izmantojot radix sort. Tas padarīs skaidrojumu skaidrāku un vienkāršāku.
Dotajā masīvā lielākais elements ir 736 kam ir 3 cipari tajā. Tātad cilpa darbosies līdz pat trīs reizēm (t.i., uz simtiem vietu ). Tas nozīmē, ka masīva kārtošanai ir nepieciešamas trīs piespēles.
Tagad vispirms kārtojiet elementus, pamatojoties uz vienības vietas cipariem (t.i., x = 0 ). Šeit mēs izmantojam skaitīšanas kārtošanas algoritmu, lai kārtotu elementus.
1. caurlaide:
Pirmajā piegājienā saraksts tiek sakārtots, pamatojoties uz cipariem 0 vietā.
Pēc pirmās piespēles masīva elementi ir -
2. caurlaide:
Šajā piegājienā saraksts tiek sakārtots, pamatojoties uz nākamajiem nozīmīgajiem cipariem (t.i., cipariem pie 10thvieta).
konstruktors java
Pēc otrās piespēles masīva elementi ir -
3. caurlaide:
Šajā piegājienā saraksts tiek sakārtots, pamatojoties uz nākamajiem nozīmīgajiem cipariem (t.i., cipariem pie 100thvieta).
Pēc trešās piespēles masīva elementi ir -
Tagad masīvs ir sakārtots augošā secībā.
Radix šķirošanas sarežģītība
Tagad apskatīsim Radix kārtošanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī Radix šķirošanas telpas sarežģītību.
1. Laika sarežģītība
| Lieta | Laika sarežģītība |
|---|---|
| Labākais gadījums | Ω(n+k) |
| Vidējais gadījums | θ(nk) |
| Sliktākajā gadījumā | O(nk) |
Radix šķirošana ir nesalīdzinošs šķirošanas algoritms, kas ir labāks par salīdzinošo šķirošanas algoritmu. Tam ir lineāra laika sarežģītība, kas ir labāka nekā salīdzinošie algoritmi ar sarežģītību O(n logn).
2. Telpas sarežģītība
| Kosmosa sarežģītība | O(n+k) |
| Stabils | JĀ |
- Radix šķirošanas telpas sarežģītība ir O(n + k).
Radix šķirošanas ieviešana
Tagad apskatīsim, kā Radix programmas ir sakārtotas dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu Radix šķirošanas ieviešanai C valodā.
#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;>