Exercício 2: Eficiência de Algoritmos de Ordenação
Condições de conclusão
Na disciplina de Introdução à Ciência da Computação, vocês aprenderam diversos algoritmos de ordenação. No presente exercício você irá desenvolver um programa em Java para analisar o desempenho de diferentes algoritmos em diferentes situações. Em particular, estamos interessados no tempo (em segundos ou milissegundos) que os algoritmos gastam para realizar o seu trabalho.
Aberto: quinta-feira, 19 mar. 2020, 00:00
Vencimento: quarta-feira, 1 abr. 2020, 23:59
Objetivos de aprendizado:
- Exercitar o uso de interfaces e herança
- Refletir sobre o desempenho de algoritmos, como medir e como apresentar os resultados de uma análise de desempenho
- Aprender como medir o tempo de execução de um programa em Java
- Aprender como gerar dados de saída para processamento em outro programa.
Sua análise deve incluir os seguintes aspectos:
- Exercitar pelo menos 4 algoritmos diferentes de ordenação, dois dele com complexidade quadrática (O(n^2)) e dois deles com complexidade O(n log n).
- Avaliar todos os algoritmos em 3 casos: (a) números quase já ordenados, (b) números totalmente aleatórios, (c) vetor em ordem inversa ao que se espera.
- Avaliar os algoritmos com vetores de diferentes tamanhos (pelo menos para vetores de tamanho 10^p onde p = 1, 2, 3, 4, 5, 6).
- Para vetores de elementos de pelo menos 3 tipos: int, float e double.
Você deve minimizar código repetido. Para isso use interfaces e herança quando apropriado. Por exemplo, tenha uma interface-padrão para um algoritmo de ordenação e depois crie as 4 classes implementando a interface usando 4 algoritmos diferentes.
Você deve escrever uma boa bateria de testes JUnit para ter certeza que os 4 algoritmos de ordenação foram implementados de forma correta.
Além do código do seu sistema e da bateria de testes JUnit, você deve entregar também um pequeno relatório PDF (entre 2 e 5 páginas) descrevendo o que você descobriu sobre o desempenho dos algoritmos. Em particular, serão valorizados relatórios que incluam gráficos claros e elucidativos sobre a comparação de desempenho dos diferentes algoritmos e como seu desempenho varia à medida em que aumentamos o tamanho do vetor e variamos outros aspectos. Para os gráficos, você pode usar ferramentas tais como gnuplot e/ou gerar arquivos .csv a partir do seu programa Java e importar o CVS no Excel ou Libre Office.
Observações:
- O exercício deve ser feito individualmente.
- O enunciado abaixo não dá a receita de bolo de como resolver todos os problemas. Você precisará pesquisar na Internet, escrever dúvidas no Fórum e discutir com os colegas.
- Você não precisa implementar do zero os algoritmos de ordenação, pode buscar implementações na Web. Mas você é responsável por garantir que eles funcionam por meio de bons testes.
- Embora seja possível usar coleções neste exercício, não é obrigatório. Teremos exercícios futuros para Coleções.
Nota sobre Ética Acadêmica:
- Você pode discutir soluções com os colegas e no Fórum mas não pode compartilhar o código da sua solução com seus colegas de disciplina.
- Plágio é vedado pelo código de ética da USP e, caso seja detectado, tanto o plagiado quanto o plagiador receberão nota -10 no exercício. No caso de reincidência, ambos terão nota 0 na disciplina.
Critérios de correção:
- Boa utilização de Interface e Herança para evitar a repetição de código (1.5 ponto)
- Implementação correta dos 4 algoritmos de ordenação (dois com complexidade O(n^2) e dois com complexidade O(n log n)) (1 ponto)
- No código, permitir a ordenação de vetores de 3 tipos diferentes de elementos (float, int, double) (1 ponto)
- No código, fazer a comparação dos algoritmos nos três casos de ordenação (vetor com elementos quase ordenados, com elementos aleatórios e com elementos na ordem inversa ao esperado) (0.5 ponto)
- No código, fazer a comparação dos algoritmos com vetores de diferentes tamanhos (pelo menos para vetores de tamanho 10, 100, 1000, 10000, 100000 e 1000000) (0.5 ponto)
- No código Java, medir o tempo de execução do programa para cada caso (0.5 ponto)
- Gerar dados de saída para outro programa (para gerar os gráficos) (0.5 ponto)
- Os testes cobrem bem os principais métodos das classes (1 ponto)
- O código dos testes está bem organizado, com pouco código repetido e um método para cada assert (1 ponto)
- Apresentação e análise dos resultados do Critério 3 no relatório (0.5 ponto)
- Apresentação e análise dos resultados do Critério 4 no relatório (0.5 ponto)
- Apresentação e análise dos resultados do Critério 5 no relatório (0.5 ponto)
- Apresentação, clareza e qualidade estética dos gráficos no relatório (1 ponto)
Sendo que os critérios foram organizados em três grupos:
- Programa Java: critérios de 1 a 7 (55% da nota)
- Testes: critérios 8 e 9 (20% da nota)
- Relatório: critérios 10 a 13 (25% da nota)