În acest articol, vom discuta despre algoritmul de sortare Radix. Sortarea prin bază este algoritmul de sortare liniară care este utilizat pentru numere întregi. În sortarea Radix, există o sortare cifră cu cifră care începe de la cifra cea mai puțin semnificativă la cea mai semnificativă cifră.
Procesul de sortare radix funcționează similar cu sortarea numelor elevilor, în ordinea alfabetică. În acest caz, există 26 de radix formate datorită celor 26 de alfabete în limba engleză. În prima trecere, numele elevilor sunt grupate în ordinea crescătoare a primei litere a numelor lor. După aceea, în a doua trecere, numele lor sunt grupate în ordinea crescătoare a celei de-a doua litere a numelui lor. Și procesul continuă până când găsim lista sortată.
furnică vs maven
Acum, să vedem algoritmul de sortare Radix.
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
Funcționarea algoritmului de sortare Radix
Acum, să vedem funcționarea algoritmului de sortare Radix.
Pașii utilizați în sortarea sortării radix sunt enumerați după cum urmează -
- În primul rând, trebuie să găsim cel mai mare element (să presupunem max ) din tabloul dat. Presupune 'X' fie numărul de cifre din max . The 'X' este calculat deoarece trebuie să parcurgem locurile semnificative ale tuturor elementelor.
- După aceea, parcurgeți unul câte unul fiecare loc semnificativ. Aici, trebuie să folosim orice algoritm de sortare stabil pentru a sorta cifrele fiecărui loc semnificativ.
Acum să vedem funcționarea sortării radix în detaliu, folosind un exemplu. Pentru a înțelege mai clar, să luăm o matrice nesortată și să încercăm să o sortăm folosind radix sort. Va face explicația mai clară și mai ușoară.
În tabloul dat, cel mai mare element este 736 care au 3 cifre din el. Deci, bucla va rula de până la trei ori (adică până la sute de loc ). Asta înseamnă că sunt necesare trei treceri pentru a sorta matricea.
Acum, mai întâi sortați elementele pe baza cifrelor locului unității (adică, x = 0 ). Aici, folosim algoritmul de sortare de numărare pentru a sorta elementele.
Trecerea 1:
În prima trecere, lista este sortată pe baza cifrelor de la locul lui 0.
După prima trecere, elementele matricei sunt -
Trecerea 2:
În această trecere, lista este sortată pe baza următoarelor cifre semnificative (adică, cifrele la 10thloc).
După a doua trecere, elementele matricei sunt -
Trecerea 3:
În această trecere, lista este sortată pe baza următoarelor cifre semnificative (adică, cifre la 100thloc).
După a treia trecere, elementele matricei sunt -
Acum, matricea este sortată în ordine crescătoare.
Complexitatea sortării Radix
Acum, să vedem complexitatea temporală a sortării Radix în cel mai bun caz, mediu și cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a sortării Radix.
1. Complexitatea timpului
| Caz | Complexitatea timpului |
|---|---|
| Cel mai bun caz | Ω(n+k) |
| Caz mediu | θ(nk) |
| Cel mai rău caz | O(nk) |
Radix sort este un algoritm de sortare non-comparativ care este mai bun decât algoritmii de sortare comparativă. Are o complexitate liniară de timp care este mai bună decât algoritmii comparativi cu complexitatea O(n logn).
vlc pentru a descărca youtube
2. Complexitatea spațială
| Complexitatea spațială | O(n + k) |
| Grajd | DA |
- Complexitatea spațială a sortării Radix este O(n + k).
Implementarea sortării Radix
Acum, să vedem programele de sortare Radix în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa sortarea Radix în limbajul C.
#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;>