Tässä artikkelissa käsittelemme Radix-lajittelualgoritmia. Radix sort on lineaarinen lajittelualgoritmi, jota käytetään kokonaisluvuille. Radix-lajittelussa suoritetaan numeroittainen lajittelu, joka alkaa vähiten merkitsevästä numerosta merkittävimpään numeroon.
Kantalauseen lajittelu toimii samalla tavalla kuin oppilaiden nimien lajittelu aakkosjärjestyksen mukaan. Tässä tapauksessa englanninkielisten 26 aakkosten ansiosta muodostuu 26 kantasanaa. Ensikierroksella opiskelijoiden nimet ryhmitellään heidän nimensä ensimmäisen kirjaimen nousevaan järjestykseen. Sen jälkeen, toisessa kierrossa, heidän nimensä ryhmitellään heidän nimensä toisen kirjaimen nousevaan järjestykseen. Ja prosessi jatkuu, kunnes löydämme lajitellun luettelon.
terävä kulma
Katsotaan nyt Radix-lajittelun algoritmia.
Algoritmi
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-lajittelualgoritmin toiminta
Katsotaan nyt, miten Radix-lajittelualgoritmi toimii.
Kantaluvun lajittelussa käytetyt vaiheet on lueteltu seuraavasti -
- Ensin meidän on löydettävä suurin elementti (oletetaan max ) annetusta taulukosta. Olettaa 'x' on numeroiden lukumäärä max . The 'x' lasketaan, koska meidän täytyy käydä läpi kaikkien elementtien merkittävät paikat.
- Käy sen jälkeen läpi yksitellen jokainen merkittävä paikka. Tässä meidän on käytettävä mitä tahansa vakaata lajittelualgoritmia lajitellaksesi kunkin merkittävän paikan numerot.
Katsotaan nyt kantalukulajittelun toimintaa yksityiskohtaisesti esimerkin avulla. Ymmärtääksesi sen selkeämmin, otetaan lajittelematon taulukko ja yritetään lajitella se kantalukulajittelulla. Se tekee selityksestä selkeämmän ja helpomman.
Annetussa taulukossa suurin elementti on 736 joilla on 3 numeroita siinä. Joten silmukka kulkee jopa kolme kertaa (eli satojen paikka ). Tämä tarkoittaa, että taulukon lajittelemiseen tarvitaan kolme läpimenoa.
Lajittele nyt ensin elementit yksikköpaikkanumeroiden perusteella (esim. x = 0 ). Tässä käytämme laskenta-lajittelualgoritmia elementtien lajitteluun.
Passi 1:
Ensimmäisellä ajolla lista lajitellaan nollan kohdalla olevien numeroiden perusteella.
Ensimmäisen läpimenon jälkeen taulukon elementit ovat -
Passi 2:
Tässä välissä luettelo lajitellaan seuraavien merkitsevien numeroiden perusteella (eli numerot 10:ssäthpaikka).
Toisen läpimenon jälkeen taulukon elementit ovat -
Passi 3:
Tässä välissä luettelo lajitellaan seuraavien merkitsevien numeroiden perusteella (eli numerot 100:ssathpaikka).
valitse multi table sql
Kolmannen ajon jälkeen taulukon elementit ovat -
Nyt matriisi on lajiteltu nousevaan järjestykseen.
Radix-lajittelun monimutkaisuus
Katsotaan nyt Radix-lajittelun aikamonimutkaisuus parhaassa tapauksessa, keskimääräisessä tapauksessa ja pahimmassa tapauksessa. Näemme myös Radix-lajin avaruuden monimutkaisuuden.
1. Aika monimutkaisuus
| Asia | Aika monimutkaisuus |
|---|---|
| Paras tapaus | Ω(n+k) |
| Keskimääräinen tapaus | θ(nk) |
| Pahimmassa tapauksessa | O(nk) |
Radix sort on ei-vertaileva lajittelualgoritmi, joka on parempi kuin vertailevat lajittelualgoritmit. Sillä on lineaarinen aikamonimutkaisuus, joka on parempi kuin vertailualgoritmit, joiden kompleksisuus on O(n logn).
2. Tilan monimutkaisuus
| Avaruuden monimutkaisuus | O(n + k) |
| Vakaa | JOO |
- Radix-lajittelun avaruuden kompleksisuus on O(n + k).
Radix-lajittelun toteutus
Katsotaan nyt Radixin ohjelmien lajittelua eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma Radix-lajittelun toteuttamiseksi C-kielellä.
#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;>