logo

TechCodeview

Radix sorteringsalgoritme

I denne artikel vil vi diskutere Radix-sorteringsalgoritmen. Radix sort er den lineære sorteringsalgoritme, der bruges til heltal. I Radix sortering er der ciffer for ciffer sortering udføres, der startes fra det mindst betydende ciffer til det mest betydende ciffer.

Processen med radix-sortering fungerer på samme måde som sorteringen af ​​elevernes navne i henhold til den alfabetiske rækkefølge. I dette tilfælde er der 26 radix dannet på grund af de 26 alfabeter på engelsk. I det første pas er elevernes navne grupperet efter den stigende rækkefølge af det første bogstav i deres navne. Derefter, i den anden omgang, grupperes deres navne efter den stigende rækkefølge af det andet bogstav i deres navn. Og processen fortsætter, indtil vi finder den sorterede liste.

java-date nu

Lad os nu se Radix-sorteringsalgoritmen.

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

Arbejde med Radix sorteringsalgoritme

Lad os nu se, hvordan Radix-sorteringsalgoritmen fungerer.

De trin, der bruges i sorteringen af ​​radix-sortering, er angivet som følger -

  • Først skal vi finde det største element (antag max ) fra det givne array. Formode 'x' være antallet af cifre i max . Det 'x' er beregnet, fordi vi skal gennemgå de væsentlige steder for alle elementer.
  • Derefter skal du gennemgå et efter et hvert væsentligt sted. Her er vi nødt til at bruge enhver stabil sorteringsalgoritme til at sortere cifrene for hvert signifikant sted.

Lad os nu se, hvordan radix-sortering fungerer i detaljer ved at bruge et eksempel. For at forstå det mere klart, lad os tage et usorteret array og prøve at sortere det ved hjælp af radix sort. Det vil gøre forklaringen klarere og lettere.

Radix sorteringsalgoritme

I det givne array er det største element 736 det har 3 cifre i den. Så løkken vil løbe op til tre gange (dvs. til hundrede sted ). Det betyder, at der kræves tre gennemløb for at sortere arrayet.

Sorter nu først elementerne på basis af enhedspladscifre (dvs. x = 0 ). Her bruger vi tællesorteringsalgoritmen til at sortere elementerne.

Beståelse 1:

I det første gennemløb er listen sorteret på baggrund af cifrene på 0's plads.

Radix sorteringsalgoritme

Efter den første gennemgang er array-elementerne -

Radix sorteringsalgoritme

Beståelse 2:

I dette pas er listen sorteret på basis af de næste signifikante cifre (dvs. cifre ved 10thplacere).

Radix sorteringsalgoritme

Efter den anden gennemgang er array-elementerne -

Radix sorteringsalgoritme

Beståelse 3:

I dette pas er listen sorteret på basis af de næste signifikante cifre (dvs. cifre ved 100thplacere).

Radix sorteringsalgoritme

Efter det tredje gennemløb er array-elementerne -

Radix sorteringsalgoritme

Nu er arrayet sorteret i stigende rækkefølge.

Radix sorterer kompleksitet

Lad os nu se tidskompleksiteten af ​​Radix-sortering i bedste tilfælde, gennemsnitligt tilfælde og værste tilfælde. Vi vil også se rumkompleksiteten af ​​Radix sort.

1. Tidskompleksitet

Sag Tidskompleksitet
Bedste sag Ω(n+k)
Gennemsnitlig tilfælde θ(nk)
Worst Case O(nk)
    Best case kompleksitet -Det opstår, når der ikke er behov for sortering, dvs. arrayet er allerede sorteret. Den bedst mulige tidskompleksitet af Radix-sortering er Ω(n+k) .Gennemsnitlig sagskompleksitet -Det opstår, når array-elementerne er i rodet rækkefølge, der ikke er korrekt stigende og ikke korrekt faldende. Den gennemsnitlige sagstidskompleksitet for Radix-sortering er θ(nk) .Worst Case Complexity -Det opstår, når array-elementerne skal sorteres i omvendt rækkefølge. Det betyder, at du skal sortere array-elementerne i stigende rækkefølge, men dets elementer er i faldende rækkefølge. Den værste tidskompleksitet af Radix-sortering er O(nk) .

Radix sort er en ikke-komparativ sorteringsalgoritme, der er bedre end de komparative sorteringsalgoritmer. Den har lineær tidskompleksitet, der er bedre end de komparative algoritmer med kompleksitet O(n logn).

2. Rumkompleksitet

Rumkompleksitet O(n + k)
Stabil JA
  • Rumkompleksiteten af ​​Radix-sortering er O(n + k).

Implementering af Radix sort

Lad os nu se Radix' programmer sortere på forskellige programmeringssprog.

kruskals algoritme

Program: Skriv et program til at implementere Radix sort i C-sprog.

 #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;>