Š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 10^thvieta).

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 100^thvieta).

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

Labākā gadījuma sarežģītība —Tas notiek, ja nav nepieciešama šķirošana, t.i., masīvs jau ir sakārtots. Radix kārtošanas labākā laika sarežģītība ir Ω(n+k) .Vidējā gadījuma sarežģītība —Tas notiek, ja masīva elementi ir sajauktā secībā, kas nav pareizi augoša un nepareizi dilstoša. Radix kārtošanas gadījuma vidējā sarežģītība ir θ(nk) .Sliktākā gadījuma sarežģītība -Tas notiek, ja masīva elementi ir jākārto apgrieztā secībā. Tas nozīmē, ka jums ir jākārto masīva elementi augošā secībā, bet tā elementi ir dilstošā secībā. Radix kārtošanas vissliktākā laika sarežģītība ir 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

• 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&apos;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;>