UNIVERSIDADE
FEDERAL DE MINAS GERAIS
INSTITUTO
DE CIÊNCIAS EXATAS
DEPARTAMENTO
DE CIÊNCIA DA COMPUTAÇÃO
ALGORITMOS
E ESTRUTURAS DE DADOS II
Prof.
Raquel O. Prates 17
de maio de 2006
Data de entrega: 06 de junho de 2006 (SEM possibilidade de
adiamento)
Penalidade por atraso: 10% por dia de atraso
Objetivo do trabalho: O objetivo deste trabalho é
permitir aos alunos implementar alguns dos algoritmos de ordenação vistos e
analisar seu desempenho.
Descrição do Trabalho:
O trabalho
consiste em implementar e comparar o desempenho de 4 algoritmos de ordenação vistos em sala: Seleção,
Inserção, QuickSort Recursivo e HeapSort 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.
Você deverá fazer
tabelas e/ou gráficos comparando a performance
de cada algoritmo. Mais
especificamente, você deverá
realizar testes com vetores
de tamanhos 20, 200, 2000, 20000 e
200000 elementos. Três diferentes tipos de vetores devem ser utilizados: aleatórios, ordenados em ordem crescente,
e ordenados em ordem decrescente.
O seu
programa deverá mostrar o relatório de execução contendo 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.
A interface do seu programa deverá permitir ao usuário
(1) selecionar o algoritmo
de ordenação desejado; (2) selecionar o tipo do vetor a ser ordenado (aleatório, crescente ou decrescente). O programa deverá mostrar na
tela ao usuário
os vetores antes e após a ordenação (o usuário deverá conseguir ver os
2 em uma só tela), além
do relatório de execução. O
programa executável a ser entregue deverá fazer a ordenação
de um vetor de 30 elementos.
Considerações sobre o
trabalho:
· O trabalho poderá ser feito em
duplas.
· O trabalho poderá ser feito em C ou
PASCAL
· O aluno deve se preocupar com a
qualidade do código sendo gerado, assim, o programa deve estar dividido em
subrotinas, deve-se usar constantes sempre que apropriado, selecionar nomes
mnemônicos para variáveis, o programa não deve fazer uso de variáveis globais
ou de comandos GOTO.
· O estudo comparativo feito na
documentação terá um peso maior do que a documentação dos trabalhos anteriores.
O que deve ser entregue:
1.
O
código do programa (eletrônico)
2.
O
programa executável
3.
Listagem dos resultados de pelo menos uma
execução de cada algoritmo com 30 elementos aleatórios
incluindo a impressão dos vetores. (Obs. Imprima a saída real do seu
programa,
sem edição).
4.
Estudo comparativo dos algoritmos: Forneça tabelas e/ou gráficos
comparativos dos seus resultados e discuta se os resultados obtidos
estão de acordo com a teoria vista em sala.
5.
A
documentação do programa, contendo:
a)
Introdução:
descrição do problema a ser resolvido e visão geral sobre o funcionamento do programa.
b)
Implementação:
descrição sobre a implementação do programa. Deve ser detalhada a estrutura de
dados utilizada (diagramas ilustrativos podem auxiliar a explicação da
estrutura), o funcionamento das principais funções e procedimentos utilizados,
o formato de entrada e saída de dados, bem como decisões tomadas relativas aos
casos e detalhes de especificação que porventura estejam omissos no enunciado.
Deve estar descrito também a linguagem e compilador usados, assim como a
justificativa da escolha pela linguagem.
c)
Estudo
de Complexidade: estudo da ordem de complexidade do tempo de execução dos
procedimentos implementados e do programa como um todo (notação O).
d)
Conclusão:
comentários gerais sobre o trabalho e as principais dificuldades encontradas em
sua implementação.
e)
Bibliografia:
bibliografia que porventura tenha sido utilizada para o desenvolvimento do
trabalho, incluindo sites da Internet se for o caso
Será
marcada uma entrevista da dupla com um dos monitores para apresentar o
trabalho. Os 2 membros do grupo devem saber responder a todas as perguntas dos
monitores.