Algoritmo de classificação Radix na estrutura de dados

O que é o algoritmo de classificação Radix?

Radix Sort é um algoritmo de classificação não comparativo. Funciona agrupando os dígitos individuais dos elementos a serem classificados. Uma técnica de classificação estável é então usada para organizar os elementos com base em sua raiz. É um algoritmo de classificação linear.

O processo de classificação envolve as seguintes propriedades:

Encontrar o elemento máximo e adquirir o número de dígitos desse elemento. Isso nos dá o número de iterações que o processo de classificação seguirá.
Agrupe os dígitos individuais dos elementos na mesma posição significativa em cada iteração.
O processo de agrupamento começará no dígito menos significativo e terminará no dígito mais significativo.
Classificando os elementos com base nos dígitos nessa posição significativa.
Manter a ordem relativa dos elementos que possuem o mesmo valor de chave. Esta propriedade da classificação radix a torna uma classificação estável.

A iteração final nos dará uma lista completamente ordenada.

Funcionamento do algoritmo de classificação Radix

Vamos tentar classificar a lista de inteiros na figura acima em ordem crescente usando o algoritmo Radix Sort.

Aqui estão as etapas para realizar o processo de classificação Radix:

Passo 1) Identifique o elemento com o valor máximo na lista. Neste caso, é 835.

Passo 2) Calcule o número de dígitos do elemento máximo. 835 tem exatamente 3 dígitos.

Passo 3) Determine o número de iterações com base na etapa 2. 835 tem 3 dígitos, o que significa que o número de iterações será 3.

Passo 4) Determine a base dos elementos. Como este é um sistema decimal, a base será 10.

Passo 5) Inicie a primeira iteração.

a) Primeira iteração

Na primeira iteração, consideramos o valor posicional unitário de cada elemento.

Passo 1) Modifique o número inteiro por 10 para obter a posição unitária dos elementos. Por exemplo, 623 mod 10 nos dá o valor 3 e 248 mod 10 nos dá 8.

Passo 2) Use classificação por contagem ou qualquer outra classificação estável para organizar os inteiros de acordo com seu dígito menos significativo. Como pode ser visto na figura, 248 cairão no 8º balde. 623 cairá no terceiro balde e assim por diante.

Após a primeira iteração, a lista agora fica assim.

Como você pode ver na figura acima, a lista ainda não está classificada e requer mais iteração para ser totalmente classificada.

b) Segunda iteração

Nesta iteração, consideraremos o dígito no 10^th local para o processo de classificação.

Passo 1) Divida os inteiros por 10. 248 dividido por 10 dá 24.

Passo 2) Modifique a saída da etapa 1 por 10. 24 mod 10 nos dá 4.

Passo 3) Siga a etapa 2 da iteração anterior.

Após a segunda iteração, a lista agora fica assim

Você pode ver na figura acima que a lista ainda não está completamente classificada, pois ainda não está em ordem crescente.

c) Terceira iteração

Para a iteração final, queremos obter o dígito mais significativo. Neste caso, são os 100^thlugar para cada um dos inteiros da lista.

Passo 1) Dividir os inteiros por 100… 415 dividido por 100 dá 4.

Passo 2) Modifique o resultado da etapa 1 por 10. 4 mod 10 nos dá 4 novamente.

Passo 3) Siga a etapa 3 da iteração anterior.

Como podemos ver, a lista agora está ordenada em ordem crescente. A iteração final foi concluída e o processo de classificação está concluído.

Pseudocódigo do algoritmo de classificação Radix

Aqui está o pseudocódigo para o algoritmo de classificação Radix

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Programa para Implementar Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Saída:

162 248 415 623 835

Python Programa para algoritmo de classificação Radix

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Saída:

[162,248,415,623,835]

Análise de complexidade do Radix Sort

Existem dois tipos de complexidade a serem considerados: complexidade de espaço e complexidade de tempo.

Complexidade do espaço: O(n+b) onde n é o tamanho do array eb é a base considerada.
Complexidade de tempo: O(d*(n+b)) onde d é o número de dígitos do maior elemento da matriz.

Complexidade espacial do tipo Radix

Dois recursos para focar na complexidade do espaço

Número de elementos na matriz, n.
A base para representar os elementos, b.

Às vezes, essa base pode ser maior que o tamanho do array.

A complexidade geral é, portanto, O(n+b).

As seguintes propriedades dos elementos na lista podem tornar o espaço de classificação radix ineficiente:

Elementos com grande número de dígitos.
A base dos elementos é grande, como números de 64 bits.

Complexidade de tempo do tipo Radix

Você pode usar a classificação por contagem como uma sub-rotina, pois cada iteração levaráeO(n+b) tempo. Se existirem d iterações, o tempo total de execução torna-se O(d*(n+b)). Aqui, “O” significa a função de complexidade.

Linearidade da classificação Radix

Radix Sort é linear quando

d é constante, onde d é o número de dígitos do maior elemento.
b não é muito maior em comparação com n.

Comparações de Radix Sort com outros algoritmos comparativos

Como vimos, a complexidade da classificação Radix é baseada no tamanho de uma palavra ou número. Terá a mesma complexidade para os casos médio e melhor. E isso é O(d*(n+b)). Além disso, difere de acordo com a técnica de classificação usada no meio. Por exemplo, você pode usar classificação por contagem ou classificação rápida para o algoritmo de classificação intermediária dentro da classificação Radix.

Aplicações do algoritmo Radix Sort

Aplicações importantes do Radix Sort são:

Radix Sort pode ser usado como um algoritmo de localização onde grandes intervalos de valores são usados.
É usado na construção de uma matriz de sufixos no algoritmo DC3.
É usado em uma máquina sequencial de acesso aleatório presente em um computador típico onde os registros são digitados.

Você pode gostar: