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

Legjobb eset összetettsége –Akkor fordul elő, ha nincs szükség rendezésre, azaz a tömb már rendezve van. A Radix rendezés legjobb eseti időbeli összetettsége az Ω(n+k) .Átlagos ügykomplexitás -Ez akkor fordul elő, ha a tömb elemei összekeveredett sorrendben vannak, ami nem megfelelően növekvő és nem megfelelően csökkenő sorrendben van. A Radix rendezés átlagos ügyidő-bonyolultsága az θ(nk) .A legrosszabb eset összetettsége -Ez akkor fordul elő, ha a tömbelemeket fordított sorrendben kell rendezni. Ez azt jelenti, hogy tegyük fel, hogy a tömb elemeit növekvő sorrendbe kell rendeznie, de az elemei csökkenő sorrendben vannak. A Radix rendezés legrosszabb időbeli összetettsége az 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 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&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;>