Neste artigo, discutiremos o algoritmo de classificação Radix. Radix sort é o algoritmo de classificação linear usado para números inteiros. Na classificação Radix, é realizada uma classificação dígito por dígito, que começa do dígito menos significativo para o dígito mais significativo.
O processo de classificação radix funciona de forma semelhante à classificação dos nomes dos alunos, de acordo com a ordem alfabética. Nesse caso, são 26 bases formadas devido aos 26 alfabetos do inglês. Na primeira passagem, os nomes dos alunos são agrupados de acordo com a ordem crescente da primeira letra de seus nomes. Depois disso, na segunda passagem, seus nomes são agrupados de acordo com a ordem crescente da segunda letra do seu nome. E o processo continua até encontrarmos a lista ordenada.
registrar memória
Agora, vamos ver o algoritmo de classificação Radix.
Algoritmo
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
Funcionamento do algoritmo de classificação Radix
Agora, vamos ver o funcionamento do algoritmo de classificação Radix.
As etapas usadas na classificação da classificação radix são listadas a seguir -
- Primeiro, temos que encontrar o maior elemento (suponha máx. ) da matriz fornecida. Suponha 'x' seja o número de dígitos em máx. . O 'x' é calculado porque precisamos percorrer os locais significativos de todos os elementos.
- Depois disso, percorra um por um cada lugar significativo. Aqui, temos que usar qualquer algoritmo de classificação estável para classificar os dígitos de cada casa significativa.
Agora vamos ver o funcionamento do radix sort em detalhes usando um exemplo. Para entender isso mais claramente, vamos pegar um array não classificado e tentar classificá-lo usando classificação radix. Isso tornará a explicação mais clara e fácil.
Na matriz fornecida, o maior elemento é 736 que têm 3 dígitos nele. Portanto, o loop será executado até três vezes (ou seja, até o centenas de lugares ). Isso significa que são necessárias três passagens para classificar a matriz.
Agora, primeiro classifique os elementos com base nos dígitos das unidades (ou seja, x = 0 ). Aqui, estamos usando o algoritmo de classificação por contagem para classificar os elementos.
Passe 1:
Na primeira passagem, a lista é ordenada com base nos dígitos na casa do 0.
Após a primeira passagem, os elementos da matriz são -
Passe 2:
Nesta passagem, a lista é ordenada com base nos próximos dígitos significativos (ou seja, dígitos em 10ºlugar).
Após a segunda passagem, os elementos da matriz são -
Passe 3:
Nesta passagem, a lista é ordenada com base nos próximos dígitos significativos (ou seja, dígitos em 100ºlugar).
seletor de consultas
Após a terceira passagem, os elementos da matriz são -
Agora, a matriz está classificada em ordem crescente.
Complexidade de classificação Radix
Agora, vamos ver a complexidade de tempo da classificação Radix no melhor caso, no caso médio e no pior caso. Veremos também a complexidade espacial da classificação Radix.
1. Complexidade de tempo
| Caso | Complexidade de tempo |
|---|---|
| Melhor caso | Ω(n+k) |
| Caso médio | θ(nk) |
| Pior caso | O(nk) |
A classificação Radix é um algoritmo de classificação não comparativo que é melhor que os algoritmos de classificação comparativa. Possui complexidade de tempo linear que é melhor que os algoritmos comparativos com complexidade O (n logn).
2. Complexidade Espacial
| Complexidade Espacial | O (n + k) |
| Estábulo | SIM |
- A complexidade espacial da classificação Radix é O (n + k).
Implementação da classificação Radix
Agora, vamos ver os programas do Radix ordenados em diferentes linguagens de programação.
Programa: Escreva um programa para implementar a classificação Radix em linguagem 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;>