Ordenação - BucketSort

Prévia do material em texto

BucketSort 
Cloves Oliveira dos Santos 
Características 
 
 
• BucketSort → Ordenação de Balde; 
 
• Números inteiros (a1, a2, ..., an); 
 
• Sequência numérica não muito extensa. 
Como Funciona 
 
 
Baseado em um vetor principal V: 
 
• Define um vetor balde Vb com o maior índice I, onde I = an; 
 
• Armazena cada número x de V em Vb com mesmo índice; 
 
• Retorna cada elemento sequencialmente de Vb para V. 
Exemplo 
Considere o vetor V = {3, 2, 4, 0}; 
 
Passo 1: 
• Como o maior número contido em V é o 4, então: 
Vb = { 
[0]
, 
[1]
, 
[2]
, 
[3]
, 
[4]
} 
Passo 2: 
• Organizar cada número de V em Vb tendo: [índice de Vb] = 
[valor x | x є V] 
 V = {3, 2, 4, 0} 
 
Vb = { 0 
[0]
, 
[1]
, 2 
[2]
, 3 
[3]
, 4 
[4]
} 
 
Exemplo 
 
 
Passo 3: 
• Retornando os valores para o vetor principal: 
Vb = { 0 
[0]
, 
[1]
, 2 
[2]
, 3 
[3]
, 4 
[4]
} 
 
 V = {0, 2, 3, 4} 
 
Fontes: 
NONATO, Luis G.; VIEIRA, Victor H. BucketSort. Disponível em: 
http://www.lcad.icmc.usp.br/~nonato/ED/Ordenacao/node56.ht
m 
 
OLIVEIRA, Cleber. Video aula do Algoritmo de ordenação 
BucketSort. Disponível em: 
https://www.youtube.com/watch?v=3ZLAZxFFMks 
 
Autor desconhecido. Bucket sort. Disponível em: 
http://pt.wikipedia.org/wiki/Bucket_sort 
Dúvidas?