Bucket Sort
Gabriel C.S.
EDA0001 – TADS – 2013
UDESC – Joinville
Consiste em dividir os elementos do vetor
a ser ordenado em baldes, ordenando
primeiramente o conteúdo dos baldes, e
depois agrupando os elementos.
 Melhor caso, Complexidade Linear, O(n).
 Pior caso, Quadrático,
O(n²).

Definição
BUCKET SORT(A, n)
 para i ← 1 até n faça
 insira A[i] na lista ligada B[⌊n A[i]⌋]
 para i ← 0 até n − 1 faça
 ordene a lista B[i] com algum algoritmo de
ordenação
 5 Concatene as listas B[0], B[1], . . . ,B[n − 1]

Pseudocódigo

http://www.cs.usfca.edu/~galles/visualiza
tion/BucketSort.html
Exemplo




Vantagens:
Não realiza comparações
É estável, preserva a ordem de chaves iguais
Tempo Linear


Desvantagens:
Precisa de mais memória para ordenar o
conjunto
O algoritmo se torna muito caro quando o
vetor chave é muito extenso

Vantagens e Desvantagens
Explique com suas palavras o algoritmo
Bucket Sort, e demonstre com um
exemplo
 Insira 10 números em um vetor e faça a
ordenação dele utilizando o Bucket Sort e
o Bubble Sort como ordenação dos
buckets.

Exercícios Sugeridos
Counting Sort
Lucas Casas
EDA0001 – TADS – 2013
UDESC – Joinville
 Vantagens:
Ordena vetores em tempo linear
 Não realiza comparações
 É um algoritmo de ordenação estável

 Desvantagens:

Usa 2 outros vetores na ordenação,
utilizando mais espaço na memória
Vantagens e Desvantagens

Esta forma de ordenação pressupõe que
cada elemento dentro do vetor “a” é um
inteiro entre 1 e k (k = maior inteiro do
vetor).

A ideia é saber para cada elemento x do
vetor, quantos elementos são iguais ou
inferiores a x.
Funcionamento







Recebe o vetor “a” (que possui os valores
desordenados)
Cria vetor cnt[MaiorValor(a)+1] e
b[tamanho(a)]
Inicializa todas as posições de cnt = 0.
Percorre o vetor “a”, para cada posição i de a
faz cnt[a[i]-1]++.
Acumula em cada elemento de cnt o
elemento somado ao elemento anterior.
Guarda em b os valores de a ordenados de
acordo com b[cnt[a[i]++]=a[i]
Copia “b” para “a”.
Funcionamento
countingsort(A[], B[], k)
for i = 1 to k do
C[i] = 0
for j = 1 to length(A) do
C[A[j]] = C[A[j]] + 1
for 2 = 1 to k do
C[i] = C[i] + C[i-1]
for j = 1 to length(A) do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
Pseudocódigo
 Recebe
um vetor de entrada, com os
valores desordenados
1
A=
2
2
5
3
3
4
0
5
2
6
3
7
0
8
3
 Então
gera um vetor B com o mesmo
tamanho de A
1
2
3
4
5
6
7
8
B=
E
um vetor C com o tamanho igual ao
maior elemento + 1
C=
0
1
2
3
0
0
0
0
Simulação
4
0
5
0
 Incrementamos
valores em A[i]
C=
 Depois
C[i] de acordo com os
0
1
2
3
2
0
2
3
4
0
5
1
fazemos C[i] = C[i] + C[i-1]
C=
0
1
2
3
2
2
4
7
Simulação
4
7
5
8
 Depois
fazemos B[C[A[i]]] = A[i], o que
vai colocar o valor de A[i] de forma
ordenada no vetor B
 Em seguida é feito o decremento de
C[A[i]]
C=
0
1
2
3
2
2
4
7
4
7
5
8
C[3] = C[3] – 1:
C=
0
1
2
3
2
2
4
6
Simulação
4
7
5
8
 Após
este ultimo passo o vetor B está
ordenado, podemos passar os valores
para o vetor A
B=

1
2
3
4
5
6
0
0
2
2
3
3
7
3
8
5
http://www.cs.usfca.edu/~galles/visualization/CountingSort.html
Simulação

Ordene o seguinte conjunto numérico
utilizando o Counting Sort:
{2, 3, 5, 3, 3, 3, 5, 6, 6, 6, 5, 5, 2, 2, 2, 7}

Para o vetor [3, 1, 2, 5, 4, 2, 2, 5], qual o
valor de k (tamanho do vetor C)?
Exercícios Sugeridos
Radix Sort
Vagner Pagotti
EDA0001 – TADS – 2013
UDESC – Joinville
radix quadratum 9 aequalis 3
=
base do quadrado 9 é igual a 3
Significado






Século XIX
Herman Hollerith (1860-1929)
Máquina de Tabulação de Cartões
Necessidade de ordenar as fichas
Harold H. Seward (1930–2012)
MIT – 1945 – Projeto Apollo
Origem
Complexidade
Notação
Significado
Constante
O(1)
Não varia com o número de entradas
Linear
O(n)
Varia linearmente
Logarítmica
O(log n)
Varia de forma logaritimica
Linearítimica
O(n log n)
Varia n vezes a variação logaritimica
Quadrática
O(n²)
Varia de forma quadrada
Radix Sort = O(n)
Classificação





Ordenação pela posição (LSB/MSB)
Algoritmo não comparativo
Algoritmo de complexidade linear
Complexidade de tempo = O(n.k)
Complexidade de espaço = O(n+s)
n = número de elementos
k = tamanho string
s = tamanho do alfabeto
Definição

Vantagens
◦ Baixa complexidade
◦ Execução rápida (linear)
◦ Estabilidade

Desvantagens
◦ Necessita mais memória
◦ Depende do tipo de dado
◦ Depende do valor máximo
Vantagens e Desvantagens
Entrada: V = vetor de inteiros
 Criar matriz de dígitos: D = matriz[10][*]
 Calcular Passos: P = número de dígitos do
maior de V
 Para cada passo:

◦ Para cada item de V:
 Calcular dígito do número (entre 0 a 9)
 Adicionar o número na matriz D[digito]
◦ Para cada item na matriz D:
 Colocar cada item no vetor V

Saida: vetor V ordenado
Algoritmo LSB - Numérico
LSB
Entrada
25
18
123
345
Passo 1
7
603
789
43
11
Passo 2
Passo 3
025
0
120
120
0
603
007
603
0
007
011
018
1
011
011
1
011
018
007
1
120
123
123
2
123
2
120
123
011
2
345
3
603
3
018
3
007
4
043
4
120
4
603
5
025
5
123
5
789
6
345
6
025
6
603
043
7
007
007
7
043
7
789
011
8
018
018
8
345
8
120
9
789
789
9
789
9
Saída
123
025
603
043
345
7
11
Exemplo
18
043
025
345
789
25
120
43
120
123
018
025
043
345
345
603
789



Entrada: V = vetor de strings, P = posição a
ser ordenada (inicialmente zero)
Criar matriz de string com uma posição para
cada caractere (ASCII): D = matriz[128][*]
Para cada item de V:
◦ Adicionar a string na matriz de acordo com o
caractere da posição informada: D[caractere]

Para cada item na matriz D:
◦ Se o vetor do caractere possuí mais de um item,
chamar a função recursivamente passando a lista
de itens do caractere e a posição informada + 1
◦ Colocar cada item no vetor V

Saida: vetor V ordenado
Algoritmo MSB – Lexicográfico
MSB
JATO
DADO
DEDO
PATO
LATA
D
F
J
L
M
P
ADO
OCA
ATO
ATA
AR
ATO
EDO
ACA
APA
D
A
E
DO
DO
MAR
FOCA
FACA
F
A
O
CA
CA
A
J
JA
DADO
DEDO
Exemplo
JAPA
A
TO
M
PA
Saída
MACA
ACA
Passo 3
Passo 2
Passo 1
Entrada
FACA
FOCA
JAPA
CA
P
T
A
O
JATO
R
LATA
MA
MACA
C
R
A
MAR
PATO
Construir uma função que recebe um
vetor de 10 inteiros e ordene os números
utilizando o algoritmo de ordenação
“Radix LSB”.
 Construir uma função que recebe uma
lista encadeada simples que contém itens
(tipo de informação) de valores inteiros e
ordene a lista com o algoritmo de
ordernação “Radix LSB”.

Exercícios Sugeridos