Metodo de ordenação c++

MINISTÉRIO DA EDUCAÇÃO UNIVERSIDADE FEDERAL DOS VALES DO JEQUITINHONHA E MUCURI FACULDADE DE CIÊNCIAS EXATAS E TECNOLÓGICAS DEPARTAMENTO DE COMPUTAÇÃO CURSO DE SISTEMAS DE INFORMAÇÃO

TRABALHO PRÁTICO 3: ORDENAÇÃO

Alba Assis Campos Polyana Ribas Bernardes

DIAMANTINA 2011

ÍNDICE

1- Introdução .................................................................................................... 03

2- Implementação............................................................................................. 04

3- Estudo de complexidade .............................................................................. 07

4- Análise de tempo ......................................................................................... 09

5- Conclusão .................................................................................................... 13

6-Bibliografia......................................................................................................14

2

1. Introdução
O problema a ser resolvido é relativo à medição do tempo de cada algoritmo de ordenação, sendo eles: InsertionSort, InsertionSort Adaptativo, SelectionSort, BubbleSort, ShellSort, QuickSort, MergeSort, MergeSortBU, PQSort e o HeapSort. Neste programa, medimos o tempo de execução de cada algoritmo de ordenação para vetores pequenos (50 números), até vetores grandes (60.000 números). Em cada case, faremos a medição do tempo para vetores aleatórios, crescentes e decrescentes, para que possa ser avaliado os melhores e piores casos e os casos médios, de cada algoritmo de ordenação e em cada distribuição de dados. Foram gerados gráficos no programa Excel, para que uma melhor visualização dos resultados do tempo, pelo número de dados, pudesse ser obtida.

3

2. Implementação
Para a implementação do programa utilizamos alocação dinâmica para os vetores vet, vet_cres, vet_decres e vet_aux, a função “rand” para gerar os números aleatórios, a biblioteca “Timer.h” para