I denne artikkelen vil vi diskutere Radix-sorteringsalgoritmen. Radix sort er den lineære sorteringsalgoritmen som brukes for heltall. I Radix sortering er det siffer for siffer sortering utføres som startes fra det minst signifikante sifferet til det mest signifikante sifferet.
Prosessen med radix-sortering fungerer på samme måte som sorteringen av elevers navn, i henhold til alfabetisk rekkefølge. I dette tilfellet er det 26 radix dannet på grunn av de 26 alfabetene på engelsk. I det første passet blir navnene på elevene gruppert i henhold til stigende rekkefølge på den første bokstaven i navnene deres. Etter det, i det andre passet, blir navnene deres gruppert i henhold til den stigende rekkefølgen til den andre bokstaven i navnet deres. Og prosessen fortsetter til vi finner den sorterte listen.
linux mint kanel vs mate
La oss nå se algoritmen til Radix-sortering.
Algoritme
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
Arbeid av Radix-sortalgoritmen
La oss nå se hvordan Radix-sorteringsalgoritmen fungerer.
Trinnene som brukes i sorteringen av radix-sortering er listet opp som følger -
- Først må vi finne det største elementet (anta maks ) fra den gitte matrisen. Anta 'x' være antall sifre i maks . De 'x' er beregnet fordi vi trenger å gå gjennom de betydelige stedene for alle elementer.
- Etter det, gå gjennom en etter en hvert viktig sted. Her må vi bruke en hvilken som helst stabil sorteringsalgoritme for å sortere sifrene til hvert betydelig sted.
La oss nå se hvordan radix-sortering fungerer i detalj ved å bruke et eksempel. For å forstå det klarere, la oss ta en usortert matrise og prøve å sortere den ved hjelp av radix sort. Det vil gjøre forklaringen klarere og enklere.
I den gitte matrisen er det største elementet 736 som har 3 sifre i den. Så løkken vil løpe opptil tre ganger (dvs. til hundrevis plass ). Det betyr at tre passeringer kreves for å sortere matrisen.
Sorter nå elementene på grunnlag av enhetsplasseringssifre (dvs. x = 0 ). Her bruker vi tellesorteringsalgoritmen for å sortere elementene.
Pass 1:
I første pass sorteres listen på grunnlag av sifrene på 0-plassen.
Etter den første passeringen er array-elementene -
Pass 2:
I dette passet blir listen sortert på grunnlag av de neste signifikante sifrene (dvs. sifrene ved 10thplass).
Etter den andre passeringen er matriseelementene -
Pass 3:
I dette passet blir listen sortert på grunnlag av de neste signifikante sifrene (dvs. sifrene ved 100thplass).
Etter den tredje passeringen er array-elementene -
Nå er matrisen sortert i stigende rekkefølge.
Radix sortere kompleksitet
La oss nå se tidskompleksiteten til Radix-sortering i beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle. Vi vil også se romkompleksiteten til Radix sort.
1. Tidskompleksitet
| Sak | Tidskompleksitet |
|---|---|
| Beste sak | Ω(n+k) |
| Gjennomsnittlig sak | θ(nk) |
| Worst Case | O(nk) |
Radix sort er en ikke-komparativ sorteringsalgoritme som er bedre enn de komparative sorteringsalgoritmene. Den har lineær tidskompleksitet som er bedre enn de komparative algoritmene med kompleksitet O(n logn).
2. Romkompleksitet
| Plass kompleksitet | O(n + k) |
| Stabil | JA |
- Romkompleksiteten til Radix-sortering er O(n + k).
Implementering av Radix sort
La oss nå se programmene til Radix sortere på forskjellige programmeringsspråk.
kruskals algoritme
Program: Skriv et program for å implementere Radix sort i C-språk.
#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;>