Lista2_AlgOrdComp

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 
ESTRUTURAS DE DADOS E ALGORITMOS 
Lista de Exercícios 
(Análise de algoritmos e algoritmos de ordenação por comparação) 
 
1. Explique a lógica do algoritmo bubble sort. 
 
2. Explique a lógica do algoritmo selection sort. 
 
3. Explique a lógica do algoritmo insertion sort. 
 
4. Faça a análise do algoritmo gnomesort visto em sala de aula. 
 
5. O tempo do merge sort depende da ordem dos valores do vetor a ser ordenado? Explique 
detalhadamente sua resposta. 
 
6. 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 8�� passos, enquanto que o 
merge sort roda em 64����	� passos. Para quais valores de n o insertion sort é melhor que o 
merge sort? 
 
7. O professor Progresso encontrou um algoritmo de ordenação baseado em comparações que gasta 
tempo 
(� lg √�	). Considerando-se o limitante inferior para o tempo de ordenação, isso é 
possível? Justifique.