Šiame straipsnyje aptarsime Radix rūšiavimo algoritmą. Radix sort yra linijinis rūšiavimo algoritmas, naudojamas sveikiesiems skaičiams. Rikiuojant simboliu, atliekamas rūšiavimas pagal skaitmenis, kuris pradedamas nuo mažiausiai reikšmingo skaitmens iki reikšmingiausio skaitmens.
Radix rūšiavimo procesas veikia panašiai kaip mokinių vardų rūšiavimas pagal abėcėlę. Šiuo atveju dėl 26 abėcėlių anglų kalboje susidaro 26 raidės. Pirmajame važiavime mokinių vardai sugrupuojami pagal jų vardų pirmosios raidės didėjimo tvarką. Po to, antrajame važiavime, jų vardai sugrupuojami pagal antrosios vardo raidės didėjimo tvarką. Ir procesas tęsiasi tol, kol randame surūšiuotą sąrašą.
skirtumas tarp dvejetainio medžio ir dvejetainio paieškos medžio
Dabar pažiūrėkime Radix rūšiavimo algoritmą.
Algoritmas
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 rūšiavimo algoritmo veikimas
Dabar pažiūrėkime, kaip veikia Radix rūšiavimo algoritmas.
Veiksmai, naudojami rūšiuojant radikso rūšiavimą, išvardyti taip:
- Pirmiausia turime rasti didžiausią elementą (tarkime maks ) iš nurodyto masyvo. Tarkime 'x' turi būti skaitmenų skaičius maks . The 'x' apskaičiuojamas, nes turime pereiti reikšmingas visų elementų vietas.
- Po to eikite po vieną kiekvieną reikšmingą vietą. Čia turime naudoti bet kokį stabilų rūšiavimo algoritmą, kad surūšiuotume kiekvienos reikšmingos vietos skaitmenis.
Dabar pažiūrėkime, kaip veikia radikso rūšiavimas, naudodami pavyzdį. Norėdami tai suprasti aiškiau, paimkime nerūšiuotą masyvą ir pabandykite jį surūšiuoti naudodami radix sort. Tai padarys paaiškinimą aiškesnį ir lengvesnį.
Pateiktame masyve didžiausias elementas yra 736 tai turi 3 skaitmenys jame. Taigi, kilpa veiks iki trijų kartų (t. y. iki šimtų vieta ). Tai reiškia, kad norint rūšiuoti masyvą, reikia trijų kartų.
Dabar pirmiausia surūšiuokite elementus pagal vieneto vietos skaitmenis (t. y. x = 0 ). Čia mes naudojame skaičiavimo rūšiavimo algoritmą elementams rūšiuoti.
1 leidimas:
Pirmuoju važiavimu sąrašas rūšiuojamas pagal 0 vietoje esančius skaitmenis.
Po pirmojo praėjimo masyvo elementai yra -
2 leidimas:
Šiame įraše sąrašas rūšiuojamas pagal kitus reikšmingus skaitmenis (t. y. skaitmenis po 10thvieta).
Po antrojo praėjimo masyvo elementai yra -
3 leidimas:
Šiame įraše sąrašas rūšiuojamas pagal kitus reikšmingus skaitmenis (t. y. skaitmenis po 100thvieta).
Po trečiojo praėjimo masyvo elementai yra -
Dabar masyvas rūšiuojamas didėjančia tvarka.
viršutinis indeksas iliustratoriuje
Radix rūšiavimo sudėtingumas
Dabar pažiūrėkime, koks yra Radix rūšiavimo sudėtingumas geriausiu, vidutiniu ir blogiausiu atveju. Taip pat pamatysime Radix rūšiavimo erdvės sudėtingumą.
1. Laiko sudėtingumas
| Byla | Laiko sudėtingumas |
|---|---|
| Geriausias atvejis | Ω(n+k) |
| Vidutinis atvejis | θ(nk) |
| Blogiausiu atveju | O (nk) |
Radix rūšiavimas yra nelyginamasis rūšiavimo algoritmas, kuris yra geresnis už lyginamuosius rūšiavimo algoritmus. Jis turi linijinį laiko sudėtingumą, kuris yra geresnis nei lyginamieji algoritmai, kurių sudėtingumas O(n logn).
2. Erdvės sudėtingumas
| Erdvės sudėtingumas | O(n + k) |
| Stabilus | TAIP |
- Radix rūšiavimo erdvės sudėtingumas yra O(n + k).
Radix rūšiavimo įgyvendinimas
Dabar pažiūrėkime, kaip Radix programos rūšiuojamos skirtingomis programavimo kalbomis.
Programa: Parašykite programą, kuri įdiegtų Radix sort C kalba.
#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;>