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

Melhor complexidade de caso -Ocorre quando não há necessidade de classificação, ou seja, o array já está classificado. A complexidade de tempo do melhor caso da classificação Radix é Ω(n+k) .Complexidade média do caso -Ocorre quando os elementos da matriz estão em uma ordem confusa que não está subindo nem descendo corretamente. A complexidade média do tempo do caso da classificação Radix é θ(nk) .Complexidade do pior caso -Ocorre quando os elementos da matriz precisam ser classificados na ordem inversa. Isso significa que você precisa classificar os elementos do array em ordem crescente, mas seus elementos estão em ordem decrescente. A complexidade de tempo de pior caso da classificação Radix é 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

• 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&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;>