Pesquisa e Ordenação - Aula 09 - Métodos de Ordenação (Comparação de chaves - Radix sort)

# Pesquisa e Ordenação #Aula 09 – Métodos de Ordenação(Ordenação de Raízes - RadixSort)

Prof. Leinylson Fontinele Pereira

Na aula anterior...

Métodos de Ordenação# ShellSort

09:21 Pesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)

O que vamos aprender?

Métodos de Ordenação# RadixSort

09:21 Pesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)

Vamos começar?

09:21 4Pesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)

09:21 5

Ordenação comRadixSort

Pesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)

Ordenação com RadixSort

09:21

Pressupõe que as chaves de entrada possuem limite novalor e no tamanho (quantidade de dígitos);

É essencial utilizar um segundo algoritmo estável pararealizar a ordenação;

Ordena números, considerando um dígito de cada vez;

A partir do menos significativo ou do mais significativoPesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)


09:21

Pegue cada número na sequência e posicione-o em uma dasdez filas, dependendo do valor do dígito sendo processado.

Em seguida, restaure cada fila para a sequência original,começando pela fila de números com um dígito 0 eterminando com a fila de números com o dígito 9.

Quando essas ações tiverem sido executadas para cada dígito,a sequência estará ordenada.



09:31

Como os valores possuem limite, e a quantidade de dígitos é fixa, épossível aplicar o Bucket Sort para cada nível;

Cria-se um balde para cada possível valor dos dígitos (0 − 9, ao invésde para cada faixa de valores), de modo a não ser necessário ordenar osbaldes internamente.

O Bucket Sort é linear neste caso, uma vez que não é necessário ordenaros baldes isoladamente.



09:31Pesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)









Em que 𝑑 é o dígito em relação ao qual as chaves serão ordenadas.



Exemplo no quadro


RadixSort: Exemplo


Lista original: 25 57 48 37 12 92 86 33

1ª passagem: 12 92 33 25 86 57 37 48

RadixSort: Exemplo


1ª passagem: 12 92 33 25 86 57 37 48

Lista classificada: 12 25 33 37 48 57 86 92



RadixSort: Mais um exemplo


0 1 2 3 4 5 6 7 8 9



0 1 2 3 4 5 6 7 8 9



0 1 2 3 4 5 6 7 8 9

Passo 1: Ordenar os números usando o 1º LSD



0 1 2 3 4 5 6 7 8 9

Passo 1



0 1 2 3 4 5 6 7 8 9


09:31

Complexidade:𝑂(𝑛)

Quantidade de dados: Muitos, porém, com chaves detamanhos limitados.

Estabilidade: Usando o LSB sim, usando MSB, não.

Adaptabilidade: Não


Concluindo...

09:31 25Pesquisa e Ordenação: Aula 09 – Métodos de Ordenação (RadixSort)

Nesta aula aprendemos...

09:31



Na próxima aula veremos...

09:31



Material: https://sites.google.com/site/leinylsonnassau

09:31

Material baseado nas aulas de:

Métodos de Ordenação, João Luís Garcia Rosa


Alguma Dúvida?

09:31

Até a próxima aula...

[email protected]

Education

Pesquisa e Ordenação - Aula 09 - Métodos de Ordenação (Comparação de chaves - Radix sort)