Algoritmo de classificação Radix na estrutura de dados

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

O Radix Sort é um algoritmo de ordenação não comparativo. Ele funciona agrupando elementos.ping Os dígitos individuais dos elementos a serem classificados. Em seguida, utiliza-se uma técnica de classificação estável para organizar os elementos com base em sua base numérica. Trata-se de um algoritmo de classificação linear.

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

• Encontrar o elemento de maior valor e obter o número de dígitos desse elemento. Isso fornece o número de iterações que o processo de ordenação realiza.
• Grouping os dígitos individuais dos elementos na mesma posição significativa em cada iteração.
• O grupoping O processo começa pelo dígito menos significativo e termina no dígito mais significativo.
• Ordenar os elementos com base nos dígitos nessa posição significativa.
• Manter a ordem relativa dos elementos que possuem o mesmo valor de chave. Essa propriedade do Radix Sort o torna um método de ordenação estável.

A iteração final retorna uma lista completamente ordenada.

Funcionamento do algoritmo de classificação Radix

Lista de inteiros a serem classificados

Vamos ordenar a lista de números inteiros na figura acima em ordem crescente usando o Radix Sort.

Aqui estão os passos para realizar o processo de Radix Sort:

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

Passo 2) Conte seus dígitos. 835 tem 3 dígitos, então o número de iterações é 3.

Passo 3) Determine a base. Como se trata de um número decimal, a base é 10.

Passo 4) Inicie a primeira iteração.

a) Primeira iteração

Classificando pelo último dígito

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

Passo 1) Calcule o resto da divisão do número inteiro por 10 para obter a casa das unidades dos elementos. Por exemplo, 623 mod 10 resulta em 3, e 248 mod 10 resulta em 8.

Passo 2) Use o algoritmo de ordenação por contagem ou outro algoritmo estável para organizar os números inteiros de acordo com seu dígito menos significativo. Conforme mostrado na figura, 248 cai no 8º grupo, 623 cai no 3º grupo e assim por diante.

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

Lista após a primeira iteração

A lista ainda não está ordenada e requer mais iterações.

b) Segunda iteração

Classificação com base em dígitos na casa das dezenas

Nesta iteração, consideramos o dígito na casa das dezenas para o processo de ordenação.

Passo 1) Divida os números inteiros por 10. Por exemplo, 248 dividido por 10 resulta em 24.

Passo 2) Transforme o resultado da Etapa 1 em 10. 24 mod 10 resulta em 4.

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

Após a segunda iteração, a lista agora se parece com isto:

Lista após a segunda iteração

A lista ainda não está completamente ordenada, pois ainda não está em ordem crescente.

c) Terceira iteração

Classificação com base nos dígitos das centenas.

Na iteração final, queremos obter o dígito mais significativo. Neste caso, é o dígito das centenas de cada um dos números inteiros da lista.

Passo 1) Divida os números inteiros por 100. Por exemplo, 415 dividido por 100 resulta em 4.

Passo 2) Transforme o resultado da Etapa 1 em 10. 4 mod 10 resulta em 4.

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

Lista após a terceira iteração

A lista agora está ordenada em ordem crescente. A iteração final foi concluída e o processo de ordenação está finalizado.

Pseudocódigo do algoritmo de classificação Radix

Segue o pseudocódigo do algoritmo de ordenação por 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 jth 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 in the jth place
    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 integer
    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 in 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

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

Saída:

[162, 248, 415, 623, 835]

Análise de Complexidade do Radix Sort

Há dois tipos de complexidade a serem considerados: complexidade espacial e complexidade temporal.

• Complexidade espacial: O(n + b) onde n é o tamanho do array e b é a base considerada.
• Complexidade temporal: O(d * (n + b)) onde d é o número de dígitos do maior elemento na matriz.

Complexidade espacial do tipo Radix

Duas características a serem consideradas em relação à complexidade espacial:

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

Às vezes, essa base pode ser maior que o tamanho da matriz. A complexidade geral é, portanto, O(n + b).

As seguintes propriedades dos elementos da lista podem tornar o Radix Sort ineficiente em termos de espaço:

• 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

Usando a ordenação por contagem como sub-rotina, cada iteração leva O(n + b) tempo. Se existirem d iterações, o tempo total de execução torna-se O(d * (n + b))Aqui, “O” denota a função de complexidade.

Linearidade da classificação Radix

O Radix Sort é linear quando:

• d é constante, onde d é o número de dígitos do maior elemento.
• b não é significativamente maior que n.

Comparação do Radix Sort com outros métodos de ordenação Algorithms

A complexidade do Radix Sort depende do tamanho do número. Tanto o melhor caso quanto o caso médio têm complexidade O(d * (n + b)). O desempenho varia de acordo com a ordenação interna — a ordenação por contagem é o padrão, mas qualquer ordenação estável funciona.

Aplicações do algoritmo Radix Sort

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

• O Radix Sort pode ser usado como um algoritmo de localização em situações que envolvem grandes intervalos de valores.
• É utilizado para construir uma matriz de sufixos no algoritmo DC3.
• É utilizado em máquinas sequenciais de acesso aleatório, onde os registros são indexados por identificadores de largura fixa.

Perguntas Frequentes