Trabalho algoritmo

Universidade Federal de Ouro Preto – UFOP
Instituto de Ciências Exatas e Biológicas – ICEB
Departamento de Computação – DECOM
Disciplina: Algoritmos e Estruturas de Dados I – CIC102
Professor: David Menotti ([e-mail])

Trabalho Prático 3
Algoritmos de Ordenação Interna
Valor: 0,6 pontos (6% da nota total)
Documentação não-Latex: -0,1 pontos

Data de entrega: 08/11/2008

O objetivo deste trabalho é comparar o desempenho dos algoritmos de ordenação vistos em sala.
Você deverá implementar os algoritmos BubbleSort, SelectSort, InsertSort, ShellSort, QuickSort,
HeapSort e MergeSort e testá-los com diversos vetores de entrada (vetores de números inteiros), contabilizando o número de comparações de chaves, o número de movimentações de registros e o tempo de execução. Para isso você deverá colocar contadores em seu código e instrumentá-lo de forma a obter o tempo de execução (o código de um “timer” para Windows está inserido ao final do enunciado).
No caso do Quicksort, você deverá implementar a variação “mediana de três”, em que o pivô é escolhido usando a mediana entre a chave mais à esquerda, a chave mais à direita, e a chave central
(como no algoritmo original). Você deverá fazer tabelas comparando a performance de cada algoritmo. Mais especificamente, você deverá realizar testes com vetores de tamanhos 100, 1000,
10000 e 100000 elementos. Quatro diferentes tipos de vetores devem ser utilizados: aleatórios, ordenados, quase ordenados (10% fora da ordem) e inversamente ordenados.
Para os vetores aleatórios, repita os testes pelo menos 10 vezes, de forma a obter médias do tempo de execução e dos contadores. O próprio programa deve gerar os vetores dos quatro tipos de entradas. O seu programa deverá imprimir o método utilizado, o tipo e tamanho do vetor, o tempo de execução e o número de comparações e movimentações efetuado. Deverá haver também uma opção no programa para imprimir os vetores antes e depois da execução.
Um detalhe