W tym artykule omówimy algorytm sortowania Radix. Sortowanie radiacyjne to algorytm sortowania liniowego używany w przypadku liczb całkowitych. Sortowanie Radix polega na sortowaniu cyfra po cyfrze, rozpoczynającym się od cyfry najmniej znaczącej do cyfry najbardziej znaczącej.
Proces sortowania radix działa podobnie do sortowania nazwisk uczniów, według kolejności alfabetycznej. W tym przypadku istnieje 26 podstaw utworzonych z powodu 26 alfabetów w języku angielskim. W pierwszym przebiegu nazwiska uczniów grupowane są w kolejności rosnącej pierwszej litery ich imion. Następnie w drugim przebiegu ich nazwiska są grupowane według rosnącej kolejności drugiej litery ich imienia. Proces trwa, dopóki nie znajdziemy posortowanej listy.
konwersja ciągu na datę
Przyjrzyjmy się teraz algorytmowi sortowania Radix.
Algorytm
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
Działanie algorytmu sortowania Radix
Przyjrzyjmy się teraz działaniu algorytmu sortowania Radix.
Kroki stosowane w sortowaniu metodą podstawową są wymienione w następujący sposób:
- Najpierw musimy znaleźć największy element (załóżmy, że maks ) z podanej tablicy. Przypuszczać 'X' będzie liczbą cyfr w maks . The 'X' jest obliczana, ponieważ musimy przejść przez znaczące miejsca wszystkich elementów.
- Następnie przejdź kolejno przez każde istotne miejsce. W tym przypadku musimy użyć dowolnego stabilnego algorytmu sortowania, aby posortować cyfry każdego znaczącego miejsca.
Przyjrzyjmy się teraz szczegółowo działaniu sortowania radix na przykładzie. Aby to lepiej zrozumieć, weźmy nieposortowaną tablicę i spróbujmy ją posortować za pomocą sortowania radix. Dzięki temu wyjaśnienia będą jaśniejsze i łatwiejsze.
W danej tablicy największym elementem jest 736 które mają 3 w nim cyfry. Zatem pętla wykona się maksymalnie trzy razy (tj miejsce setki ). Oznacza to, że do posortowania tablicy potrzebne są trzy przebiegi.
Teraz najpierw posortuj elementy na podstawie cyfr jednostkowych (tj. x = 0 ). Tutaj używamy algorytmu sortowania przez zliczanie do sortowania elementów.
Przejście 1:
W pierwszym przebiegu lista jest sortowana na podstawie cyfr na miejscu 0.
Po pierwszym przejściu elementy tablicy są -
ciągi znaków na liczby całkowite
Przejście 2:
W tym przebiegu lista jest sortowana na podstawie kolejnych znaczących cyfr (tj. cyfr na 10tmiejsce).
Po drugim przejściu elementy tablicy są -
Przejście 3:
W tym przebiegu lista jest sortowana na podstawie kolejnych cyfr znaczących (tj. cyfr przy 100tmiejsce).
Po trzecim przejściu elementy tablicy są -
Teraz tablica jest posortowana rosnąco.
Złożoność sortowania radiacyjnego
Przyjrzyjmy się teraz złożoności czasowej sortowania Radix w najlepszym przypadku, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania Radix.
1. Złożoność czasowa
| Sprawa | Złożoność czasu |
|---|---|
| Najlepszy przypadek | Ω(n+k) |
| Przeciętny przypadek | θ(nk) |
| Najgorszy przypadek | O(nk) |
Sortowanie radiacyjne to algorytm sortowania nieporównawczego, który jest lepszy od algorytmów sortowania porównawczego. Ma liniową złożoność czasową, która jest lepsza niż algorytmy porównawcze o złożoności O(n logn).
2. Złożoność przestrzeni
| Złożoność przestrzeni | O(n + k) |
| Stabilny | TAK |
- Złożoność przestrzenna sortowania Radix wynosi O (n + k).
Implementacja sortowania Radix
Przyjrzyjmy się teraz programom Radixa sortującym w różnych językach programowania.
Program: Napisz program realizujący sortowanie Radix w języku 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;>