Merge Sort, Quick Sort e Heap Sort

Escola

Análise de Algoritmos

Nome

Local e data

Resumo

Neste trabalho consiste em implementação, e análise de desempenho de três algoritmos de ordenação chamados de MergeSort, HeapSort e QuickSort. No qual percebe-se que o algoritmo MergeSort contem o melhor desempenho para ordenações em grande escala.

Sumário

Instrodução 2
MergeSort 3
HeapSort 5
QuickSort 8
Análise de Tempo 10
Desvio Padrão 11
Conclusão 11

Lista de tabelas e gráficos

Figura 1. Gráfico de média dos tempos para os algoritmos......................9
Figura 2. Gráfico de Desvio padrão dos algoritmos......................................9
Tabela 1. Média de tempo dos testes................................................................10
Tabela 2. Desvio padrão dos algoritmos.........................................................10

Introdução

Este trabalho tem como finalidade observar o desempenho dos algoritmos de ordenação MergeSort, HeapSort e QuickSort. Sendo utilizado vetores de diferentes tamanhos para cálculo de tempo e comparando-os entre si.

Desenvolvimento

1 – MergeSort

Este com certeza foi o algoritmo com maior número de problemas, principalmente pelo uso de memória que é superior que os demais tornando assim difícil alcançar a marca de 10 milhões de vetores para ordenação. O primeiro guia para implementação do código foi o exposto na aula do professor que me ministra esta matéria, logo o código não se apresentou eficaz, mesmo adicionando as mudanças necessárias como o uso de ponteiros, finalizando o primeiro código, só era capaz de ordenar vetores com até 1.000 valores de inteiros, obrigando assim a mudar a lógica desta implementação, conforme a mudança dos códigos, assim, melhorando-o foi alcançada a marca de maior valor exigido, 10 milhões de inteiros que se finalizou com o código a seguir:

//
// main.c
// MergeSort
//
//