Trabalho Pratico I - Analise Comparativa de Algoritmos de Ordenacao IFMG

IFMG Campus Sao Joao Evangelista Sistemas de Informacao Turma SI 20231 Professor Eduardo Trindade eduardotrindadeifmgedubr Algoritmo e Estrutura de Dados II Trabalho Pratico I 20 pontos Observacoes O trabalho deve ser realizado e entregue individualmente E recomendado discutir os problemas e estrategias de solucao com seus colegas Tente solucionar os problemas vocˆe mesmo pois solucionar problemas e desenvolver o raciocınio logico e componente fundamental neste curso Duvidas devem ser postadas no forum para discussao Trabalho Pratico I no Moodle Sua duvida pode ser a mesma de um colega A entrega devera ser feita exclusivamente pelo Moodle Atencao Entregar em um unico arquivo zip ou rar ou 7z ou targz contendo todo o seu trabalho O Arquivo deve conter uma pasta com o projeto implementacao e outra com o relatorio e demais documentos se for o caso O nome do arquivo zip deve ser TP1AEDSIISeuNomezip Caso nao esteja utilizando a linguagem CC favor especificar A data limite de entrega encontrase no Moodle Objetivos Fixar conceitos sobre manipulacao de arquivos Fixar conceitos sobre algoritmos de ordenacao por comparacoes Realizar a implementacao destes algoritmos utilizando vetores Registrar o tempo de execucao dos algoritmos processo de ordenacao e comparacoes conside rando diferentes tamanhos de entradas de dados Analisar a complexidade dos algoritmos implementados Realizar experimentacao com varios tipos e tamanhos de entradas de dados tecendo analises sobre os resultados 1 Descricao Neste trabalho vocˆe devera implementar todos os algoritmos de ordenacao apresentados em aula Bubble Sort Shell Sort Selection Sort Insertion Sort Quick Sort Merge Sort Seu objetivo e fazer um estudo comparativo dos metodos medindo o tempo de execucao o numero de trocas e o numero de comparacoes realizadas para varios tamanhos de vetores de entrada Faca um programa que calcule os tempos e as comparacoes e salve esses dados em um arquivo de texto Instˆancias Uma instˆancia e um caso particular de um problema com dados especıficos Cada conjunto de dados de um problema define uma instˆancia do problema Por exemplo uma instˆancia para o problema de ordenacao e uma sequˆencia de dados com elementos para serem ordenados Neste trabalho os algoritmos implementados serao utilizados para ordenar uma sequˆencia de dados contida em uma das instˆancias fornecidas arquivos txt As instˆancias contem dados descritos linha a linha e se dividem em dois grupos Grupo de Palavras Consiste em uma colecao de dados representados por palavras do dicionario brasileiro que possuem os seguintes tamanhos 29855 e 261791 elementos sendo que para cada tamanho temos trˆes instˆancias com as seguintes caracterısticas aleatorias inversamente ordenadas e ordenadas Grupo de Numeros Essas instˆancias possuem os seguintes tamanhos 1000 10000 100000 e 1000000 elementos sendo que para cada um destes tamanhos temos instˆancias com as seguintes caracterısticas aleatorias quase ordenadas inversamente ordenadas e ordenadas Assim serao fornecidas 22 instˆancias conforme descrito abaixo ListaAleatoria1000txt Arquivo contendo uma sequˆencia aleatoria de 1000 elementos do tipo inteiro ListaQuaseOrdenada1000txt Arquivo contendo uma sequˆencia de 1000 elementos do tipo inteiro com apenas alguns elementos fora de ordem ListaInversamenteOrdenada1000txt Arquivo contendo uma sequˆencia inversamente ordenada de 1000 elementos do tipo inteiro ListaOrdenada1000txt Arquivo contendo uma sequˆencia ordenada de 1000 elemenntos do tipo inteiro ListaAleatoria10000txt Arquivo contendo uma sequˆencia aleatoria de 10000 elementos do tipo inteiro ListaQuaseOrdenada10000txt Arquivo contendo uma sequˆencia de 10000 elementos do tipo inteiro com apenas alguns elementos fora de ordem 2 ListaInversamenteOrdenada10000txt Arquivo contendo uma sequˆencia inversamente ordenada de 10000 elementos do tipo inteiro ListaOrdenada10000txt Arquivo contendo uma sequˆencia ordenada de 10000 elemenntos do tipo inteiro ListaAleatoria100000txt Arquivo contendo uma sequˆencia aleatoria de 100000 elementos do tipo inteiro ListaQuaseOrdenada100000txt Arquivo contendo uma sequˆencia de 100000 elementos do tipo inteiro com apenas alguns elementos fora de ordem ListaInversamenteOrdenada100000txt Arquivo contendo uma sequˆencia inversamente orde nada de 100000 elementos do tipo inteiro ListaOrdenada100000txt Arquivo contendo uma sequˆencia ordenada de 100000 elementos do tipo inteiro ListaAleatoria1000000txt Arquivo contendo uma sequˆencia aleatoria de 1000000 elementos do tipo inteiro ListaQuaseOrdenada1000000txt Arquivo contendo uma sequˆencia de 1000000 elementos do tipo inteiro com apenas alguns elementos fora de ordem ListaInversamenteOrdenada1000000txt Arquivo contendo uma sequˆencia inversamente orde nada de 1000000 elementos do tipo inteiro ListaOrdenada1000000txt Arquivo contendo uma sequˆencia ordenada de 1000000 elementos do tipo inteiro DicionarioAleatorio29855txt Arquivo contendo uma sequˆencia aleatoria de 29855 elementos do tipo string DicionarioOrdenado29855txt Arquivo contendo uma sequˆencia ordenada de 29855 elementos do tipo string DicionarioInversamenteOrdenado29855txt Arquivo contendo uma sequˆencia inversamente or denada de 29855 elementos do tipo string DicionarioAleatorio261791txt Arquivo contendo uma sequˆencia aleatoria de 261791 elementos do tipo string DicionarioOrdenado261791txt Arquivo contendo uma sequˆencia ordenada de 261791 elementos do tipo string DicionarioInversamenteOrdenado261791txt Arquivo contendo uma sequˆencia inversamente ordenada de 261791 elementos do tipo string Implementacao A implementacao deve seguir as seguintes regras 1 O programa podera ser implementado em qualquer linguagem de programacao de sua preferˆencia desde que devidamente comentado e indentado 2 Seu programa devera exibir um menu inicial que pergunte ao usuario qual metodo sera utilizado para ordenacao 3 3 Apos a escolha do metodo apresente um novo menu com uma lista de instˆancias para o usua rio Devese escolher aqui uma das doze instˆancias fornecidas para ordenacao Cada instˆancia corresponde a um arquivo instˆancia fornecido e um tamanho N de dados 4 Definido o metodo e a instˆancia direcione o usuario para a visualizacao da ordenacao do vetor 5 Mostre o numero de comparacoes realizadas e o tempo de execucao do algoritmo considere o processo de ordenacao e comparacoes para calculo Dica para calculo do tempo de execucao sugerese o uso das bibliotecas chrono ou ctime timeh 6 Armazene em um arquivo txt os dados que julgar necessarios para a etapa seguinte de Analise ex comparacoes tempo metodo tamanho da instˆancia etc Seja criativo para elaborar seu programa e utilize melhorias se achar necessario Analise Pelo menos duas analises deverao ser realizadas 1 Complexidade definicao da ordem de complexidade do algoritmo Big O considerando que a instrucao mais relevante e a comparacao 2 Tempo de execucao registrar o tempo que cada algoritmo demorou para resolver cada instˆancia do problema Para obter uma medida estatisticamente mais confiavel sugerese a medicao de um mesmo metodo para uma determinada instˆancia varias vezes 10x e calcule o tempo medio dividindo o tempo total pelo numero de vezes que o algoritmo foi executado Utilize o arquivo de texto gerado em um programa como o Excel Matlab ou Octave para gerar graficos dos seus resultados As Figuras a seguir mostram exemplos de resultados obtidos para diversos metodos de ordenacao Figura 1 Metodos de Ordenacao Resultados Matlab 4 Figura 2 Resultados expostos em Tabela e Grafico Excel Entrega O que devera ser entregue 1 Codigo fonte bem indentado e comentado Codigo fonte contendo todas as especificacoes da etapa de Implementacao e funcoes bem definidas e tratadas 2 Documentacao do Trabalho Relatorio completo do trabalho em formato PDF contendo a Capa Capa formatada e identificada com os dados necessarios e recomendados pela ABNT identificacao aluno e tıtulo do trabalho b Sumario enumeracao das divisoes secoes capıtulos e outras partes do trabalho seguindo a mesma ordem e grafia em que o conteudo nele se sucede c Introducao descricao do problema a ser resolvido e visao geral sobre o funcionamento do programa d Implementacao descricao sobre a implementacao do programa e algoritmos utilizados De vem ser detalhadas as estruturas de dados utilizadas o funcionamento das principais funcoes e procedimentos utilizados o formato de entrada e saıda de dados bem como decisoes toma das relativas aos casos e detalhes de especificacao que possam estar omissos no enunciado e Analise de Complexidade descricao e analise da complexidade dos algoritmos implementa dos notacao Big O e do tempo de execucao para cada metodo implementado f Resultados descricao detalhada dos testes executados apresentando analises comparativas e crıticas Apresente os principais resultados em tabelas eou graficos 5 g Conclusao comentarios gerais sobre o trabalho e consideracoes finais sobre a comparacao entre algoritmos Principais dificuldades encontradas em sua implementacao ou compreensao h Bibliografia referˆencia teorica utilizada para o desenvolvimento do trabalho incluindo sites da Internet se for o caso A referˆencia deve ser citada no texto quando for utilizada i Apˆendice codigo fonte com as principais funcoes utilizadas e detalhadas no trabalho Avaliacao O que sera avaliado 1 Cada aluno devera apresentar o seu trabalho codigo documentacao completa e resultados indi vidualmente para o professor na data de entrega 2 A avaliacao consistira no domınio do conteudo capacidade em responder questionamentos refe rentes a implementacao qualidade da documentacao elaborada e apresentacao do trabalho Comentarios Gerais Clareza indentacao e comentarios no programa serao bem avaliados Apenas ler comentarios durante a apresentacao nao sera bem avaliado O trabalho e individual Trabalhos identificados como copias ou plagio poderao ser zerados Programas que nao compilarem na apresentacao nao serao corrigidos Evite contratempos teste seu trabalho no laboratorio antes e organizese 6