Ordenação em tempo linear.
  1. Ilustre a execucao do radix sort considerando a entrada: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR,TAR, DIG, BIG, TEA, NOW, FOX.

Passo 1

Temos 16 strings de três letras cada uma:
COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX
Queremos usar o método LSD (least significant digit) de Radix Sort: em cada passo aplicamos um Counting Sort estável sobre uma posição de caractere, começando pela última posição e indo até a primeira.

Passo 2

Passo 1 do Radix: ordenar pelo terceiro caractere (última coluna), de modo estável.
Primeiro, separamos em “baldes” pela letra nessa posição, preservando a ordem original dentro de cada letra:
A: SEA, TEA
B: MOB, TAB
G: DOG, RUG, DIG, BIG
R: BAR, EAR, TAR
W: COW, ROW, NOW
X: BOX, FOX
Concatenando esses baldes, obtemos a lista após o primeiro passe:
SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX

Passo 3

Passo 2 do Radix: ordenar pelo segundo caractere (coluna do meio), mantendo estabilidade (usando Counting Sort estável).
Baldes por essa letra:
A: TAB, BAR, EAR, TAR
E: SEA, TEA
I: DIG, BIG
O: MOB, DOG, COW, ROW, NOW, BOX, FOX
U: RUG
Concatenando, temos após o segundo passe:
TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUG

Passo 4

Passo 3 do Radix: ordenar pelo primeiro caractere (primeira coluna), de modo estável.
Baldes por essa letra:
B: BAR, BIG, BOX
C: COW
D: DIG, DOG
E: EAR
F: FOX
M: MOB
N: NOW
R: ROW, RUG
S: SEA
T: TAB, TAR, TEA
Concatenando, chega-se à lista completamente ordenada:
BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, RUG, SEA, TAB, TAR, TEA

Resposta

BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, RUG, SEA, TAB, TAR, TEA

Exercícios relacionados