Trabalho PAA

Prévia do material em texto

Fundação Centro de Análise, Pesquisa e Inovação Tecnológica 
 FUCAPI 
 
 
 
 
 
 
 
 
 
Projeto de Análise de Algoritmos 
 
 
Patrícia de Lima Melo 
Rick Jones M. Ferreira 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 MANAUS 
SETEMBRO- 2016 
 
 
 
 
 
 
 
 
Patrícia de Lima Melo 
Rick Jones M. Ferreira 
 
 
 
 
 
 
 
 
 
 
 
 
 
Análise de custo dos algoritmos QuickSort e HeapSort 
 
 
 
 
 
 
 
 
 
 
 
 
 Trabalho apresentado à Professora 
Josiane Rodrigues da Silva da disciplina 
Projeto de Análise de Algoritmos, turno 
Noturno do curso de Engenharia da 
Computação 
 
 
 
 
 
Faculdade FUCAPI 
 
MANAUS 
 
 
Introdução 
 
 
Este trabalho tem por objetivo fazer uma breve explicação dos algoritmos de ordenação 
QuickSort e HeapSort falando de sua análise de custo do tempo e mostrar um relatório 
dos experimentos realizados através da implementação dos mesmos. 
 
 
Algoritmo de ordenação Quicksort 
 
A ideia básica do quickSort é dividir e conquistar, nesse caso temos um 
elemento que é escolhido como pivô e que a partir dele particionamos/ dividimos o 
vetor e é utilizado o próprio vetor de entrada para fazer a ordenação. O método 
particiona, que é a função que vai determinar aonde o vetor vai ser dividido, faz com 
que os dados sejam rearranjados de forma que os valores menores do que o pivô sejam 
colocados antes dele e os menores depois e recursivamente ordena as duas partições de 
modo que ele fique em ordem crescente. 
 
Performance do QuickSort 
 
- Melhor caso 
O melhor caso ocorre quando o particionamento faz ter a quantidade de 
elementos tanto no lado esquerdo quanto direito serem iguais fazendo com que a 
varredura dos dois lados do vetor seja eficiente. Logo a função de custo para o melhor 
caso é T(n) = O(nlogn). 
 
- Pior caso 
O pior caso ocorre quando o particionamento fica totalmente desbalanceado isso 
ocorre quando se escolhe como pivô o menor ou o maior elemento fazendo assim o 
quicksort varrer todos os elementos do vetor. Outras situações que levam ao pior caso é 
quando a entrada está ordenada ou a entrada está em ordem inversa. Logo a função de 
custo para o pior caso é de ordem quadrática T(n) = Θ(n²). 
 
- Caso médio 
O caso médio a partição produz uma mistura de divisões boas e ruins. Logo no 
caso médio temos a função de custo T(n) = O(nlogn) 
 
 
 
 
 
 
Algoritmo de ordenação HeapSort 
 
 O heapSort é baseada em uma estrutura de dados chamada heap. Heap é uma 
estrutura de dados organizada como uma árvore binária. 
 A ideia básica do heapsort é selecionar o menor elemento do vetor e depois 
trocar com o item que está na primeira posição do vetor. O primeiro passo é construir o 
heap a partir dos dados, depois disso são retirados os maiores valores do heap e 
colocados no novo array ordenado. Para esse primeiro elemento, ele deve ser a posição 
0 do array. O próximo passo é a reconstrução do heap e a remoção do próximo maior 
elemento e a inserção deste elemento no array ordenado. Depos de removido todos os 
elementos do heap, o array está ordenado. 
 De acordo com [Ziviane 2004] o algoritmo heapsort possui complexidade 
O(nlogn) independente da entrada. 
 
Desempenho do QuickSort e HeapSort através do experimento 
 
Analise dos algoritmos em cima de vetores de tamanho de 1000, 10000, 15000, 
20000, 30000. 
A verificação será feita numa amostra de 5 vetores de tamanho diferentes com 
90% de números iguais e o restante distinto. E uma outra verificação numa amostra de 5 
vetores de tamanho diferentes com elementos aleatórios e sem números iguais. 
 
 
 
 
 Figura 1. Grafico de desempenho Quicksort com elementos 90% iguais 
 
 
Figura 2. Grafico de desempenho Heapsort com elementos 90% iguais 
 
 
Verificando os graficos de desempenho da Figura 1 e Figura 2 o HeapSort teve 
um desempenho melhor em relação ao tempo de ordenação para vetores com elementos 
repetidos. 
 
 Figura 3. Grafico de desempenho Quicksort com elementos aleatórios 
 
 
Figura 4. Grafico de desempenho Heapsort com elementos aleatórios 
 
 
 
 Ao analisar os gráficos de desempenho das Figuras 3 e Figura 4 o QuickSort 
teve um desempenho melhor em relação ao tempo de ordenação para vetores com 
elementos aleatórios. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Conclusão 
 
 Pôde-se observar que para vetores em que 90% de seus elementos 
são repetidos o desempenho do heapsort foi melhor que o do quicksort. Ao 
analisar os vetores com elementos aleatórios o desempenho do quicksort 
foi melhor. Porém pôde-se ver uma estabilidade do heapsort em ambas 
situações já que os elementos de entrada não interferem no seu 
desempenho. 
 
 
 
Referências 
 
Ziviani, N. (2004). Projeto de Algoritmos: com implementações em Pascal e C. Cengage 
Learning (Thomson / Pioneira), São Paulo, 1st edition 
http://www.ime.usp.br/~pf/algoritmos/aulas/hpsrt.html -> acessado dia 25/09/2016 
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/quick.html -> acessado dia 
25/09/2016