Radix Sort

Uma radix ou base é uma representação de um número que mostra quantos dígitos são necessários para representar um número posicional. Por exemplo, para representar o número binário, o valor da radix é 2 (representamos o binário com 0 ou 1). Para representar o número decimal, o valor do radix é 10 (representamos o número decimal com números de 0 a 9).

Como funciona o algoritmo de classificação do REDIX

Vamos supor que tenhamos a seguinte lista de matrizes e queremos classificar esta matriz usando a classificação Radix:

Usamos mais dois conceitos neste algoritmo, que são:

1. 1. Dígito menos significativo
   2. Dígito mais significativo

1. Dígito menos significativo (LSD): O valor do expoente de um número decimal extremamente próximo da posição mais à direita é referido como LSD.

Por exemplo, o número decimal "2563" tem o valor de dígito menos significativo de "3".

2. Digit mais significativo (MSD): O MSD é o inverso exato do LSD. Um valor MSD é o dígito mais à esquerda de qualquer número decimal.

Por exemplo, o número decimal "2563" tem o valor de dígito mais significativo de "2".

Etapa 1: Procure o elemento mais importante (valor máximo)

Como já sabemos, esse algoritmo funciona nos dígitos para classificar os números. Então, para isso, esse algoritmo requer o número máximo de dígitos para a iteração. Nosso primeiro passo é descobrir o número máximo de elementos nesta matriz. Depois de encontrar o valor máximo de uma matriz, temos que contar o número de dígitos nesse número para as iterações.

Etapa 2: conte o número de dígitos do elemento máximo

Temos que contar o número de dígitos do elemento máximo de uma matriz, porque então podemos descobrir quantas iterações precisamos para classificar a matriz.

Então, como já descobrimos, o elemento máximo é 167 e o número de dígitos é 3. Precisamos de três iterações para classificar a matriz.

Etapa 3: classificar os elementos pelo dígito menos significativo

O primeiro arranjo de dígitos é feito pelo dígito menos significativo. A partir da imagem a seguir, podemos ver que todos os dígitos menores e menos significativos estão dispostos no lado esquerdo. Nesse caso, nos concentramos apenas no dígito menos significativo.

Mais uma coisa que podemos notar aqui é que alguns dígitos são classificados automaticamente, mesmo que seus dígitos unitários sejam diferentes, mas os outros são iguais.

Por exemplo, Os números 36 na posição de índice 7 e o número 32 na posição 3 do índice 3 têm dígitos unitários diferentes, mas têm o mesmo outro número, que é 3. Obviamente, o número 32 vem antes do número 36. Após os primeiros arranjos de elementos, podemos ver que agora 32 vem antes de 36, que é classificado automaticamente.

Etapa 4: classificando os elementos de acordo com o próximo dígito (dezenas dígitos)

Agora, organizamos os elementos da matriz no décimo dígito. Como já sabemos, essa classificação deve ser concluída em 3 iterações porque o número máximo de elementos tem 3 dígitos. Esta é a nossa segunda iteração e podemos assumir que a maioria dos elementos da matriz é classificada após esta iteração.

Os resultados dados mostram que a maioria dos elementos da matriz já está classificada (abaixo de 100). Se tivéssemos apenas dois dígitos como nosso número máximo, apenas duas iterações são suficientes para obter a matriz classificada.

Etapa 5: classificando os elementos com base no dígito mais significativo

Agora, entramos na terceira iteração com base no dígito mais significativo (centenas de lugar). Esta iteração classifica os três elementos de dígitos da matriz. Após essa iteração, todos os elementos da matriz estão em ordem classificada.

Depois de organizar os elementos baseados no MSD, nossa matriz agora está totalmente classificada.

Entendemos os conceitos do algoritmo de classificação da radix. Mas precisamos de mais um algoritmo para implementar o tipo de radix, e esse é o Contando o algoritmo de classificação. Vamos entender isso Contando o algoritmo de classificação.

Contando o algoritmo de classificação

Agora explicamos cada etapa do algoritmo de classificação de contagem.

A matriz fornecida é a nossa matriz de entrada e os números mostrados acima da matriz são os números de índice dos elementos correspondentes.

Etapa 1: pesquise o elemento máximo

O primeiro passo no algoritmo de classificação de contagem é procurar o elemento máximo em toda a matriz. A melhor maneira de procurar o elemento máximo é atravessar toda a matriz e comparar os elementos em cada iteração - o elemento de valor maior é atualizado até o final da matriz.

Durante a primeira etapa, descobrimos que o elemento máximo é 9 na posição de índice 8.

Etapa 2: Faça uma nova variedade de tamanhos comparáveis

Criamos uma nova variedade de tamanhos semelhantes. Como já sabemos, o valor máximo da matriz é 9, então haverá um total de 10 elementos. Como resultado, exigimos um tamanho máximo de matriz de + 1.

Como podemos ver na imagem anterior, temos um tamanho total da matriz de 10 com valores de 0. Na próxima etapa, preenchemos esta matriz de contagem com elementos classificados.

Etapa 3: preencha a nova matriz de acordo com a frequência de cada elemento

Nesta etapa, contamos cada elemento e, de acordo com a frequência deles, preenche os valores correspondentes na matriz.

Por exemplo, Como podemos ver, o elemento 6 está presente duas vezes na matriz de entrada. Então, entramos no valor de frequência de 2 no índice 6.

Etapa 4: determine a frequência cumulativa

Agora, contamos a frequência cumulativa da matriz preenchida. Esta frequência cumulativa é usada posteriormente para classificar a matriz de entrada.

Podemos calcular a frequência cumulativa adicionando o valor atual ao valor anterior do índice, conforme mostrado na captura de tela a seguir:

O último valor da matriz na matriz cumulativa deve ser o número total de elementos.

Etapa 5: Classificação da matriz por frequência comutativa

Agora, usamos a matriz de frequência cumulativa para mapear cada elemento da matriz para produzir uma matriz classificada.

Por exemplo, o primeiro elemento na matriz 5 que escolhemos. Então, o valor de frequência cumulativa correspondente no índice 5, que tem um valor de 7. Diminuímos o valor em 1 e temos 6. Colocamos o valor 5 no índice na posição 6 e também diminuímos a frequência cumulativa no índice 5 por 1.

A frequência cumulativa está no índice 5 após ser diminuída por um.

Vamos entender esse conceito com mais um exemplo.

O próximo elemento na matriz é 2. Escolhemos o valor do índice de 2 na matriz de frequência comutativa. Diminuímos o valor no índice 2 e obtemos 1. Colocamos o elemento da matriz 2 na posição 1 do índice 1. No final, diminuímos o valor da frequência no índice 2 por 1, como mostrado na captura de tela a seguir:

A partir da matriz classificada anterior, podemos ver que apenas um lugar é deixado antes de 2 (posição do índice 1) e um valor menor que 2 na matriz original, que é 1. Então, ele vai da maneira certa de classificar a matriz.

Não precisamos lembrar de reduzir o valor cumulativo em cada iteração. Após duas das iterações anteriores, a matriz cumulativa se parece com o seguinte:

Etapa 6: Matriz final

Executamos a etapa 5 até que todos os elementos da matriz sejam preenchidos na matriz classificada. Depois de ser preenchido, nossa matriz se parece com o seguinte:

Programa C ++ para Algoritmo de Classificação de Radix

Este exemplo é baseado na explicação neste tutorial de dica do Linux

#incluir
usando namespace std;
Void radixsortalgo (int a [], int size_of_a)
// Na primeira etapa (etapa 1), finalizamos o valor máximo na matriz.
int maximumumumber = a [0];
para (int i = 1; imaximumMumber = max (maximumumumber, a [i]);

// Na segunda etapa (etapa 2), estamos calculando o número de dígitos de
// O elemento máximo da matriz
int digitsCount = 0;
while (maximumumumber> 0)
DigitSCount ++;
maximumMumber /= 10;

// Agora estamos atualizando uma nova matriz (etapas 3,4 e 5)
para (int i = 0; iint pwr = pow (10, i);
int new_a [size_of_a];
// Este é um count_array que é usado para a matriz de contagem
// Para classificar os dígitos de 0 a 9.
int count_array [10];
MEMSET (count_array, 0, sizeof (count_array));
// calculando a frequência de cada elemento da matriz
for (int j = 0; jint num = (a [j]/pwr) % 10;
count_array [num] ++;

// Esta é uma frequência comulativa
for (int j = 1; j; j<10;j++)
count_array [j] += count_array [j-1];

// estamos mapeando a matriz de frequência com cada elemento
// da matriz para descobrir a posição desejada na matriz atualizada
for (int j = size_of_a-1; j> = 0; j-)
int num = (a [j]/pwr) % 10;
new_a [count_array [num] -1] = a [j];
count_array [num]-;

// Agora, estamos atualizando a matriz com a nova matriz
for (int j = 0; ja [j] = new_a [j];

// Finalmente, imprimimos o resultado da matriz classificada
for (int j = 0; jcout<cout<
int main ()
// Esta variedade de valores será classificada usando o algoritmo de classificação do Radix.
int a [] = 155, 10, 51, 38, 16, 811, 755, 3, 91, 6;
// estamos calculando o tamanho da matriz
int size_of_a = sizeof (a)/sizeof (size_of_a);
// chamando para o método de algoritmo de classificação da radix
radixsortalgo (a, size_of_a);
retornar 1;

Saída da classificação C+ em execução

linuxhint@desktop: ~ $ ./radix
3 6 10 16 38 51 91 155 755 811
linuxhint@desktop: ~ $

Complexidade do tempo do algoritmo de classificação da radix

Vamos calcular a complexidade do tempo do algoritmo de classificação da radix.

Etapa 1: Para calcular o número máximo de elementos em toda a matriz, atravessamos toda a matriz. Portanto, o tempo total necessário é O (n).

Etapa 2: Vamos supor que o total de dígitos no número máximo é k. Portanto, o tempo total que é levado para calcular o número de dígitos em um número máximo é O (k).

Etapas 3 a 5: Essas etapas funcionam nos próprios dígitos, então eles levam o (k) vezes junto com a contagem do algoritmo de classificação em cada iteração - o (k * n).

Como resultado, a complexidade total do tempo é O (k * n).

Conclusão

Estudamos a classificação da Radix e o algoritmo de contagem. Existem diferentes tipos de algoritmos de classificação que estão disponíveis no mercado. O melhor algoritmo também depende dos requisitos. Não é fácil dizer qual algoritmo é o melhor. Mas com base na complexidade do tempo, estamos tentando descobrir o melhor algoritmo. E com base nisso, a Radix Sort também é um dos melhores algoritmos para classificar.