Lista de exercicios 3 - Ord Tempo Linear

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
Aula de exercícios sobre algoritmos de ordenação em tempo linear
1. Ilustre a execucao do counting sort considerando a entrada:
6,0,2,0,1,3,4,6,1,3,2.
2. 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.
3. Ilustre a execucao 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 * lg(n))?
BUCKET-SORT(A) 
1 n = comprimento[A] 
2 for i = 1 to n 
3 do 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”.