Aula de Exercícios 02 (Lista de exercicios 3 - 1o estagio)

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 análise de algoritmos e algoritmos de ordenação 
1. Suponha que um certo problema X depende de um parametro inteiro positivo . Meu algoritmo 
para o problema consome tempo . Meu amigo diz ter um algoritmo melhor, que consome 
tempo . Devo ficar impressionado? 
2. O professor Progresso encontrou um algoritmo de ordenação baseado em comparações que gasta 
tempo √ . Considerando-se o limitante inferior para o tempo de ordenação, isso é 
possível? Justifique. 
3. Explique a lógica do algoritmo bubble sort. 
4. Explique a lógica do algoritmo selection sort. 
5. Explique a lógica do algoritmo insertion sort. 
6. Faça a análise do algoritmo gnomesort visto em sala de aula. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7. O tempo do merge sort depende da ordem dos valores do vetor a ser ordenado? Explique 
detalhadamente sua resposta. 
8. Suponha que estamos comparando implementacoes de insertion sort e merge sort em uma 
mesma máquina. Para entradas de tamanho n, insertion sort roda em passos, enquanto que o 
merge sort roda em passos. Para quais valores de n o insertion sort é melhor que o 
merge sort? 
9. Ilustre a execucao do counting sort considerando a entrada: 6,0,2,0,1,3,4,6,1,3,2. 
10. 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. 
11. 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. 
procedure gnomeSort(a[]) 
 pos := 1 c 
 while pos < length(a) no pior caso pos é incrementado uma vez e decrementado outra vez. 
 Assim, pos assume os valores K (incrementando K vezes) e depois K-1 
 (decrementando K vezes). Isso o K pode ser 2,3,4,5,..length(a). 
 Assim temos a expressao 2*(2+3+4+5+...+N) = O(n2). 
 if (a[pos] >= a[pos-1]) c 
 pos := pos + 1 c 
 else 
 swap (a[pos],a[pos-1]) c 
 if (pos > 1) c 
 pos := pos - 1 c 
 else 
 pos := pos + 1 c 
 end if 
 end if 
 end while 
end procedure