UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
Disciplina: Programação C++
Professor: Renato E. N. de Moraes
Aluno:
Turma: 9EC
Data: 29/09/10
Semestre: 2010-1 Valor: 10,0 pts
Trabalho 03 - Estruturas Dinâmicas
Nota:
Este é um trabalho individual onde deve ser desenvolvido um documento em formato de
monografia conforme modelo dado em aula. O objetivo do documento é mostrar ao leitor a
comparação de três algoritmos de classificação implementados de diferentes formas. O documento deve mostrar e justificar qual é a melhor forma de implementação ou, equivalentemente,
como as diferentes implementações se comportam para os diferentes algoritmos/casos e porquê
isso acontece.
Para cada algoritmo deve ser apresentado o pseudo-código usado na implementação. Um
pseudo-código consiste de um programa com linhas numeradas e explicadas (referenciadas)
durante o texto. Ainda para cada algoritmo, deve ser apresentado o seu comportamento para
o caso aleatório. No final, todos os três algoritmos devem ser comparados (o quê comparar?).
Todas as comparações devem ser explicadas e justificadas no texto. Acrescentar gráficos do tipo
log × log nas suas análises. Insira também na sua análise os resultados dos mesmos algoritmos
do trabalho 01.
Para comparação, os algoritmos devem ser executados todos em uma mesma máquina (mesmas entradas) e a configuração da máquina deve estar citada no texto, bem como compilador e
sistema operacional usados.
Os algoritmos devem ser implementados em C++, os gráficos devem ser gerados pelo gnuplot
e a monografia deve ser editada no LATEX.
Dos três algoritmos a serem implementados será exigido o QuickSort. Os demais algoritmos
serão escolhidos (justificar a escolha) pelo autor do trabalho.
O quê deve ser implementado:
• Construa um gabarito de classes e funções de uma estrutura dinâmica ao estilo de C. O
seu gabarito deve fornecer as três opções de algoritmo de classificação para o usuário do
gabarito.
• Implemente cada algoritmo usando como base os contêineres da STL (implementar para
todos):
– vector
– deque
– list
• Faça um programa que utilize os algoritmos de classificação fornecidos pela STL.
A versão impressa da monografia (não código) deve ser entregue ao professor até o dia
20/10/10. Cada dia útil de atraso implica em perda de 10% da nota final.
Bom trabalho!!
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/