V tomto článku budeme diskutovať o Radixovom triediacom algoritme. Radix sort je lineárny triediaci algoritmus, ktorý sa používa pre celé čísla. V Radixovom triedení sa vykonáva triedenie číslica po číslici, ktoré začína od najmenej významnej číslice po najvýznamnejšiu číslicu.
Proces radixového triedenia funguje podobne ako triedenie mien študentov podľa abecedného poradia. V tomto prípade existuje 26 radixov vytvorených vďaka 26 abecedám v angličtine. V prvom prechode sú mená žiakov zoskupené podľa vzostupného poradia prvého písmena ich mien. Potom sa v druhom prechode ich mená zoskupia podľa vzostupného poradia druhého písmena ich mena. A proces pokračuje, kým nenájdeme zoradený zoznam.
hibernovať dialekt
Teraz sa pozrime na algoritmus Radixovho triedenia.
Algoritmus
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
Fungovanie Radixovho triediaceho algoritmu
Teraz sa pozrime na fungovanie Radixovho triediaceho algoritmu.
Kroky použité pri triedení radix sort sú uvedené nasledovne -
- Najprv musíme nájsť najväčší prvok (predpokladajme max ) z daného poľa. Predpokladajme 'X' byť počet číslic v max . The 'X' sa vypočítava, pretože potrebujeme prejsť cez významné miesta všetkých prvkov.
- Potom prejdite jedno po druhom každé významné miesto. Tu musíme použiť akýkoľvek stabilný triediaci algoritmus na triedenie číslic každého významného miesta.
Teraz sa pozrime na fungovanie radix sort pomocou príkladu. Aby sme to pochopili jasnejšie, zoberme si netriedené pole a skúsme ho zoradiť pomocou radix sort. Vysvetlenie bude jasnejšie a jednoduchšie.
V danom poli je najväčší prvok 736 ktoré majú 3 číslice v ňom. Slučka teda prebehne až trikrát (t.j. do stovky miesta ). To znamená, že na zoradenie poľa sú potrebné tri prechody.
Teraz najskôr zoraďte prvky na základe číslic jednotky (t.j. x = 0 ). Tu používame triediaci algoritmus počítania na triedenie prvkov.
Priechod 1:
V prvom prechode je zoznam zoradený na základe číslic na mieste 0.
Po prvom prechode sú prvky poľa -
Priechod 2:
V tomto prechode je zoznam zoradený na základe nasledujúcich platných číslic (t. j. číslic na 10thmiesto).
obsahuje podreťazec java
Po druhom prechode sú prvky poľa -
Priechod 3:
V tomto prechode je zoznam zoradený na základe nasledujúcich platných číslic (t. j. číslic na 100thmiesto).
Po treťom prechode sú prvky poľa -
Teraz je pole zoradené vo vzostupnom poradí.
Zložitosť triedenia Radix
Teraz sa pozrime na časovú zložitosť Radixovho triedenia v najlepšom prípade, priemernom prípade a najhoršom prípade. Uvidíme aj priestorovú zložitosť Radix sortu.
1. Časová zložitosť
| Prípad | Časová zložitosť |
|---|---|
| Najlepší prípad | Ω(n+k) |
| Priemerný prípad | θ(nk) |
| V najhoršom prípade | O(nk) |
Radix sort je nekomparatívny triediaci algoritmus, ktorý je lepší ako porovnávacie triediace algoritmy. Má lineárnu časovú zložitosť, ktorá je lepšia ako porovnávacie algoritmy so zložitosťou O(n logn).
2. Zložitosť priestoru
| Vesmírna zložitosť | O(n + k) |
| Stabilný | ÁNO |
- Priestorová zložitosť Radixovho triedenia je O(n + k).
Implementácia Radix sort
Teraz sa pozrime na programy Radixu v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu Radix sort v jazyku 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;>