ExercicioOrdenacao2

Prévia do material em texto

Aquecimento para a Avaliação de Análise de Algoritmos
1) Para os algoritmos abaixo, informe qual sua classe assintótica para o pior 
e melhor caso. Detalhe qual seria a instância a ser fornecida de modo que 
ocorra o pior ou melhor caso.
a) BubbleSort
b) InsertionSort
c) QuickSort
d) CountSort
e) HeapSort
2) Ilustre como ficaria a ordenação da instância A = {6, 4, 8, 3, 9, 5, 10, 
1, 7, 2} utilizando o método de ordenação HeapSort.
3) Seja o algoritmo descrito abaixo, faça sua análise assintótica para pior e 
melhor caso:
QUICKSORT(A, lo, hi)
if (lo < hi)
p = pivot(A, lo, hi);
 left, right = partition(A, p, lo, hi);
 quicksort(A, lo, left);
 quicksort(A, right, hi);
 end if
4) Descreva as propriedades de um heap de máxima. Faça um algoritmo para 
tornar   um   vetor   qualquer   em   um   heap   de   máxima   e   faça   sua   análise 
assintótica.
5) Quais a limitação para o uso do CountSort? Cite dois exemplos: um para 
para uma instância que possa ser usada no CountSort e outro para uma 
instância para a qual o CountSort não é viável e justifique sua resposta.