logo

TechCodeview

Radix sorteringsalgoritm

I den här artikeln kommer vi att diskutera Radix-sorteringsalgoritmen. Radix sort är den linjära sorteringsalgoritmen som används för heltal. I Radix-sorteringen utförs siffra för siffra sortering som startas från den minst signifikanta siffran till den mest signifikanta siffran.

Processen att sortera radix fungerar på samma sätt som sorteringen av elevers namn, enligt alfabetisk ordning. I det här fallet finns det 26 radix bildade på grund av de 26 alfabeten på engelska. I det första passet grupperas elevernas namn i stigande ordning på den första bokstaven i deras namn. Efter det, i det andra passet, grupperas deras namn enligt den stigande ordningen för den andra bokstaven i deras namn. Och processen fortsätter tills vi hittar den sorterade listan.

strsep

Låt oss nu se algoritmen för Radix-sorteringen.

Algoritm

 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

Fungerar av Radix sorts algoritm

Låt oss nu se hur Radix sorteringsalgoritm fungerar.

Stegen som används vid sortering av radixsortering är listade enligt följande -

  • Först måste vi hitta det största elementet (antag max ) från den givna arrayen. Anta 'x' vara antalet siffror i max . De 'x' beräknas eftersom vi behöver gå igenom de betydande platserna för alla element.
  • Efter det, gå igenom en efter en varje betydande plats. Här måste vi använda vilken stabil sorteringsalgoritm som helst för att sortera siffrorna för varje betydande plats.

Låt oss nu se hur radixsortering fungerar i detalj med hjälp av ett exempel. För att förstå det tydligare, låt oss ta en osorterad array och försöka sortera den med hjälp av radix sort. Det kommer att göra förklaringen tydligare och lättare.

Radix sorteringsalgoritm

I den givna arrayen är det största elementet 736 som har 3 siffror i den. Så slingan kommer att köras upp till tre gånger (dvs. till hundratals plats ). Det betyder att det krävs tre pass för att sortera arrayen.

Sortera nu först elementen på basis av enhetsplatssiffror (dvs. x = 0 ). Här använder vi räknesorteringsalgoritmen för att sortera elementen.

Pass 1:

I första passet sorteras listan utifrån siffrorna på 0:s plats.

Radix sorteringsalgoritm

Efter det första passet är arrayelementen -

Radix sorteringsalgoritm

Pass 2:

I detta pass sorteras listan på basis av nästa signifikanta siffror (d.v.s. siffror vid 10thplats).

Radix sorteringsalgoritm

Efter det andra passet är arrayelementen -

Radix sorteringsalgoritm

Pass 3:

I detta pass sorteras listan på basis av nästa signifikanta siffror (d.v.s. siffror vid 100thplats).

Radix sorteringsalgoritm

Efter det tredje passet är arrayelementen -

Radix sorteringsalgoritm

Nu är matrisen sorterad i stigande ordning.

använder internet

Radix sorts komplexitet

Låt oss nu se tidskomplexiteten hos Radix-sorteringen i bästa fall, genomsnittsfall och värsta fall. Vi kommer också att se rymdkomplexiteten hos Radix sort.

1. Tidskomplexitet

Fall Tidskomplexitet
Bästa fall Ω(n+k)
Genomsnittligt fall θ(nk)
Värsta fall O(nk)
    Best Case Complexity -Det inträffar när det inte krävs någon sortering, dvs arrayen är redan sorterad. Den bästa tidskomplexiteten för Radix-sort är Ω(n+k) .Genomsnittlig ärendekomplexitet -Det inträffar när arrayelementen är i blandad ordning som inte är korrekt stigande och inte korrekt fallande. Den genomsnittliga falltidskomplexiteten för Radix-sort är θ(nk) .Worst Case Complexity -Det inträffar när arrayelementen måste sorteras i omvänd ordning. Det betyder att du måste sortera arrayelementen i stigande ordning, men dess element är i fallande ordning. Det värsta tänkbara tidskomplexiteten hos Radix-sort är O(nk) .

Radix sort är en icke-jämförande sorteringsalgoritm som är bättre än de jämförande sorteringsalgoritmerna. Den har linjär tidskomplexitet som är bättre än de jämförande algoritmerna med komplexiteten O(n logn).

2. Rymdkomplexitet

Rymdkomplexitet O(n + k)
Stabil JA
  • Rymdkomplexiteten för Radix-sortering är O(n + k).

Implementering av Radix sort

Låt oss nu se Radix-programmen sortera i olika programmeringsspråk.

Program: Skriv ett program för att implementera 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&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;>