V tomto článku se budeme zabývat algoritmem řazení Radix. Radix sort je lineární třídicí algoritmus, který se používá pro celá čísla. Při řazení Radix se provádí řazení číslice po číslici, které začíná od nejméně významné číslice po nejvýznamnější číslici.
Proces radix sort funguje podobně jako řazení jmen studentů podle abecedního pořadí. V tomto případě existuje 26 radixů vytvořených kvůli 26 abecedám v angličtině. V prvním průchodu jsou jména studentů seskupena podle vzestupného pořadí prvního písmene jejich jmen. Poté, ve druhém průchodu, jsou jejich jména seskupena podle vzestupného pořadí druhého písmene jejich jména. A proces pokračuje, dokud nenajdeme seřazený seznam.
zřetězení java řetězec
Nyní se podívejme na algoritmus Radixova řazení.
Algoritmus
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
Práce s Radixovým třídicím algoritmem
Nyní se podívejme, jak funguje Radix sort Algorithm.
Kroky použité při třídění radix sort jsou uvedeny následovně -
- Nejprve musíme najít největší prvek (předpokládejme max ) z daného pole. Předpokládat 'X' být počet číslic v max . The 'X' se počítá, protože potřebujeme projít významná místa všech prvků.
- Poté projděte jedno po druhém každé významné místo. Zde musíme použít jakýkoli stabilní třídicí algoritmus k seřazení číslic každého významného místa.
Nyní se podívejme na fungování radix sort podrobně na příkladu. Abychom tomu porozuměli jasněji, vezměme netříděné pole a zkusme ho seřadit pomocí radix sort. Vysvětlování bude jasnější a jednodušší.
V daném poli je největší prvek 736 které mají 3 číslice v něm. Smyčka tedy poběží až třikrát (tj stovky míst ). To znamená, že k seřazení pole jsou zapotřebí tři průchody.
Nyní nejprve seřaďte prvky na základě číslic jednotky (tj. x = 0 ). Zde používáme k řazení prvků algoritmus počítání.
Průchod 1:
V prvním průchodu je seznam setříděn na základě číslic na místě 0.
Po prvním průchodu jsou prvky pole -
Průchod 2:
V tomto průchodu se seznam třídí na základě následujících platných číslic (tj. číslic na 10čtmísto).
Po druhém průchodu jsou prvky pole -
Průchod 3:
V tomto průchodu se seznam třídí na základě následujících platných číslic (tj. číslic na 100čtmísto).
Po třetím průchodu jsou prvky pole -
Nyní je pole seřazeno ve vzestupném pořadí.
obsahuje v řetězci
Složitost řazení Radix
Nyní se podívejme na časovou složitost Radixova řazení v nejlepším, průměrném a nejhorším případě. Uvidíme také prostorovou složitost Radix sortu.
1. Časová složitost
| Pouzdro | Časová složitost |
|---|---|
| Nejlepší případ | Ω(n+k) |
| Průměrný případ | θ(nk) |
| Nejhorší případ | O(nk) |
Radix sort je nesrovnávací třídicí algoritmus, který je lepší než srovnávací třídicí algoritmy. Má lineární časovou složitost, která je lepší než srovnávací algoritmy se složitostí O(n logn).
2. Prostorová složitost
| Vesmírná složitost | O(n + k) |
| Stabilní | ANO |
- Prostorová složitost Radixova řazení je O(n + k).
Implementace Radix sort
Nyní se podívejme na řazení programů Radix v různých programovacích jazycích.
Program: Napište program pro implementaci Radix sort v jazyce 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;>