Lista3_AlgOrdTempoLinear

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Eletrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
 
Lista de exercícios 
Algoritmos de ordenação em tempo linear 
 
1. Ilustre a execução do counting sort considerando a entrada: 6,0,2,0,1,3,4,6,1,3,2. 
 
2. Ilustre a execução do radix sort considerando a entrada: COW, DOG, SEA, RUG, ROW, MOB, BOX, 
TAB, BAR, EAR,TAR, DIG, BIG, TEA, NOW, FOX. 
 
3. Ilustre a execução do bucket sort com 5 baldes considerando a entrada: 0.79, 0.13, 0.16, 0.64, 
0.39, 0.20, 0.89, 0.53, 0.71, 0.42. 
 
4. Qual é o tempo de execução do pior caso para o algoritmo de bucket sort abaixo? E Como se 
caracteriza o pior caso? Que alteração simples no algoritmo preserva seu tempo de execução 
esperado (linear) e torna seu tempo de execução no pior caso igual a O(n * log(n))? 
 
BUCKET-SORT(A) 
1 n = comprimento[A] 
2 for i = 1 to n 
3 inserir ordenado A[i] na lista B[A[i]/100] 
4 concatenar as listas B[0], B[1], ..., B[n-1] juntas em ordem 
 
5. Descreva como você modificaria o RadixSort para ordenar cadeias de caracteres de tamanho 
diferente. Por exemplo, a chave “carrega” deve estar antes de “carregamento” e depois de 
“borboleta”.