Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Funcionamento do método de ordenação Radix

0 votos
9 visitas
perguntada Nov 8 em Ciência da Computação por Renan Abrantes (16 pontos)  

Como funciona o algoritmo de ordenação Radix? Qual a diferença do método MSD e LSD?

Compartilhe

1 Resposta

0 votos
respondida Nov 8 por Renan Abrantes (16 pontos)  
editado Nov 8 por Renan Abrantes

O método de ordenação Radix é uma ótima escolha para ordenar por elementos únicos (Exemplo: ordenação de palavras em ordem alfabética). O uso deste método é aliado a outros algoritmos de ordenação, principalmente para ordenação de poucos elementos, como o Counting Sort, para as chaves decorrentes da posição do elemento.

Decorrente da análise pela posição do elemento, o Radix Sort pode ser implementado de 2 principais formas: inciando a ordenação pela primeira posição do valor, algoritmo mais significativo, chamado de Radix Sort MSD (Most Significant Digit) ou inciando a ordenação pela última posição do valor, algoritmo menos significativo, chamado de Radix Sort LSD (Least Significant Digit).

Podemos exemplicar o funcionamento de cada tipo deste método partindo da lista desordenada:

[432,045,121,788,001,788,023]

A imagem será apresentada aqui.

No caso do Radix Sort LSD, o algoritmo parte da ordenação no caso A da figura acima, após a ordenação do elemento menos significativo é realizado a ordenação em loop até o algarismo mais significativo. Desta forma, por conta da leitura da lista em sequência, os elementos mantém a ordem do elemento menos significativo ao passar pela ordenação dos demais elementos mais significativos.

Já no caso do Radix Sort MSD, o algoritmo parte da ordenação no caso C da figura acima, após a ordenação é chamada uma função recursiva para cada elemento único ordenado em caminho ao elemento menos significativo. Assim, este tipo de aplicação é ideal para lidar com programação paralela.

Em uma implantação em python do Radix Sort LSD pode ser realizado da seguinte forma:

def Radix_LSD(lista): # Realiza a ordenação a partir da Unidade e segue por meio de um laço for até a base maior
    maior_elemento = max(lista) # Encontra a base maior
    unidade = 1 # Inicia com as unidades
    for i in range(len(str(maior_elemento))):
        lista = CountingSort(lista, unidade)
        unidade = 10**(i+1)
    return lista

Inicialmente a função recebe uma lista desordenada como argumento, para encontrar a quantidade de ordenações necessárias é preciso saber a quantidade de chaves do maior número. Em seguida é realizada a ordenação utilizando o método CountingSort dos dígitos dos algarismos menos significativos e segue avançando até o o algarismo mais significativo.

Neste caso, a complexidade desta ordenação é O(N+k), sendo k a base dos elementos ordenados (Nesta implementação foi utilizada a base decimal, k=10)

O Counting Sort é um algoritmo de ordenação estável, possuindo complexidade para todos os casos de O(N). Este método identifica para cada elemento a quantidade de elementos que ele na lista, desta forma é possivel saber a posição a posição do elemento. A implementação foi realizada de seguinte forma:

def Gen_list(n): # Cria lista no padrão [0,...,0]
    lista = []
    for i in range(n):
        lista.append(0)
    return lista # Retorna uma lista no padrão [0,...,0]

def CountingSort(lista, unidade): # Algoritmo utilizado como Sub-rotina para o Radix LSD 
otimizado para ordanação de numeros de 1 digito
    ordenado = Gen_list(len(lista)) # Lista de zeros
    contagem = Gen_list(10) # Baldes para algoritmos de 0 a 9

    for i in range(len(lista)):
        uni = lista[i] // unidade # Busca a unidade de base 10
        contagem[uni % 10] += 1 # Conta quantos algarismos tem de cada

    for i in range(1, 10):
        contagem[i] += contagem[i - 1] # Faz uma soma acumulativa das lista

    for i in range(len(lista) - 1,-1,-1): # Realiza a ordenação com base apenas na base 
        uni = lista[i] // unidade
        ordenado[contagem[uni % 10] - 1] = lista[i]
        contagem[uni % 10] -= 1

    for i in range(len(lista)):
        lista[i] = ordenado[i] # Saida da lista 
    return lista

Já a implementação do Radix Sort MSD pode ser realizado da seguinte forma:

def Algarismo(x,d): # Encontra o algarismo do numero x na posicao d Ex: Para d = 1 e x = 12, retorna 2
    return int((x/(10**(d - 1))))%10

def Gen_matriz(n): # Cria lista no padrão [[],...,[]]
    lista = []
    for i in range(n):
        lista.append([])
    return lista # Retorna uma lista no padrão [[],...,[]]

def Radix_MSD (lista, i): # Realiza a ordenação a partir da base maior e segue por meio de iteração for até a unidade
    if len(lista) <= 1: # Final da iteração ao chegar na unidade
        return lista
    baldes = Gen_matriz(10) # Baldes de algarismos, sendo cada linha da matriz utilizada por uma base
    saida = []
    for elem in lista:
        if(i <= 0):
            saida.append(elem) 
        else:
            if i > 0:
                baldes[Algarismo(elem,i)].append(elem) 
    baldes = [Radix_MSD(balde, i - 1) for balde in baldes ] # Realiza a iteração da função caso possua mais bases a percorrer
    out = saida.copy()
    for balde in baldes:
        for alg in balde:
            out += [alg]  # Saida iteração
    return out

Ao inciar pelo algarismo mais significativo é preciso que para avançar a ordenação dos algarismos menos significativos seja mantido a ordem dos mais significativos. Para resolver este problema foi utilizado uma matriz, funcionando como um "balde" que: ao atingir o algarismo menos significativo, por interação da função, retorna para rotina primária despejando os valores ordenados para formar a matriz com dados ordenados.

Neste caso, a complexidade desta ordenação é O(N*k), sendo k a quantidade de elementos significativos, esta complexidade é variável, podendo ser menor, pois podem ter elementos que são únicos para uma posição de elemento significativo, não precisando avançar até o ultimo algarismo.

Utilizando a lista como teste:

lista = [118,99,20,10,15,10,5,220,221,333,999,35,35,35,55,3,9,7,35]  # Lista a ser ordenada por Radix 

A visualização dos resultados podem ser observados pelo seguinte código:

print("Radix Sort LSD")
print()
print("Não Ordenado: " + str(lista.copy()))
resultado = Radix_LSD(lista.copy())   # Radix LSD
print("Ordenado: " + str(resultado))
print()
print("Radix Sort MSD")
print()
print("Não Ordenado: " + str(lista.copy()))
maior_elemento = max(lista.copy())  
resultado = Radix_MSD(lista.copy(), len(str(maior_elemento))) # Radix MSD
print("Ordenado: " + str(resultado))

O resultado obtido foi:

Radix Sort LSD

Não Ordenado: [118, 99, 20, 10, 15, 10, 5, 220, 221, 333, 999, 35, 35, 35, 55, 3, 9, 7, 35]
Ordenado: [3, 5, 7, 9, 10, 10, 15, 20, 35, 35, 35, 35, 55, 99, 118, 220, 221, 333, 999]

Radix Sort MSD

Não Ordenado: [118, 99, 20, 10, 15, 10, 5, 220, 221, 333, 999, 35, 35, 35, 55, 3, 9, 7, 35]
Ordenado: [3, 5, 7, 9, 10, 10, 15, 20, 35, 35, 35, 35, 55, 99, 118, 220, 221, 333, 999]

...