Ebben a cikkben a Radix rendezési algoritmust tárgyaljuk. A Radix rendezés az egész számokhoz használt lineáris rendezési algoritmus. A Radix rendezésben számjegyenkénti rendezés történik, amely a legkisebb jelentőségű számjegytől a legjelentősebb számjegyig kezdődik.
A radix rendezés folyamata hasonlóan működik, mint a tanulónevek ábécé sorrend szerinti rendezéséhez. Ebben az esetben az angol 26 ábécé miatt 26 gyök keletkezik. Az első menetben a tanulók nevei a nevük kezdőbetűjének növekvő sorrendjében vannak csoportosítva. Ezt követően a második menetben nevüket a nevük második betűjének növekvő sorrendje szerint csoportosítják. És a folyamat addig folytatódik, amíg meg nem találjuk a rendezett listát.
vezérlési struktúrák python
Most pedig lássuk a Radix rendezés algoritmusát.
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
A Radix rendezési algoritmus működése
Most pedig lássuk a Radix rendezési algoritmus működését.
A radix rendezés rendezésénél használt lépések a következők:
- Először meg kell találnunk a legnagyobb elemet (tegyük fel max ) az adott tömbből. Tegyük fel 'x' a számjegyek száma max . A 'x' kiszámítása, mert az összes elem jelentős helyén át kell mennünk.
- Ezt követően menjen végig egyenként minden jelentős helyen. Itt bármilyen stabil rendezési algoritmust kell használnunk az egyes jelentős helyek számjegyeinek rendezéséhez.
Most egy példa segítségével nézzük meg részletesen a radix rendezés működését. Hogy jobban megértsük, vegyünk egy rendezetlen tömböt, és próbáljuk meg rendezni a radix sort segítségével. Világosabbá és könnyebbé teszi a magyarázatot.
Az adott tömbben a legnagyobb elem az 736 amelyek rendelkeznek 3 számjegyek benne. Tehát a hurok akár háromszor is lefut (azaz a százas hely ). Ez azt jelenti, hogy három lépésre van szükség a tömb rendezéséhez.
Most először rendezze az elemeket az egységhely számjegyei alapján (pl. x = 0 ). Itt a számláló rendezési algoritmust használjuk az elemek rendezésére.
1. bérlet:
Az első lépésben a lista a 0 helyén lévő számjegyek alapján rendeződik.
Az első lépés után a tömb elemei:
2. bérlet:
Ebben a lépésben a lista a következő jelentős számjegyek (azaz a 10-es számjegyek) alapján rendeződik.thhely).
A második lépés után a tömb elemei:
3. bérlet:
Ebben a lépésben a lista a következő jelentős számjegyek (azaz a 100-as számjegyek) alapján rendeződik.thhely).
A harmadik lépés után a tömb elemei:
dinamikus java tömb
Most a tömb növekvő sorrendben van rendezve.
Radix rendezés összetettsége
Most pedig lássuk a Radix rendezés időbeli összetettségét legjobb, átlagos és legrosszabb esetben. Látni fogjuk a Radix fajta térbonyolultságát is.
1. Időbonyolultság
| Ügy | Idő összetettsége |
|---|---|
| Legjobb eset | Ω(n+k) |
| Átlagos eset | θ(nk) |
| Legrosszabb esetben | O(nk) |
A Radix rendezés egy nem összehasonlító rendezési algoritmus, amely jobb, mint az összehasonlító rendezési algoritmusok. Lineáris időbonyolultsága jobb, mint az O(n logn) komplexitású összehasonlító algoritmusok.
2. A tér összetettsége
| A tér összetettsége | O(n + k) |
| Stabil | IGEN |
- A Radix rendezés térkomplexitása O(n + k).
Radix rendezés megvalósítása
Most nézzük meg, hogy a Radix programjai különböző programozási nyelveken vannak rendezve.
Program: Írjon programot a Radix rendezés megvalósítására C nyelven.
#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;>