IMPA
 Algoritmos
 2017 – trabalhos


Trabalho 1 – ordenação (para 12/9)

O objetivo do trabalho é fazer uma análise experimental para comparar alguns algoritmos de ordenação.

  1. Implemente os algoritmos estudados em aula (seleção, inserção, mergesort (top-down e bottom-up), quicksort, heapsort). Escreva o programa mais simples possível para testar cada algoritmo. Compare o esforço necessário para a implementação correta de cada algortimo.
  2. Compare o desempenho dos algoritmos em sequências de números inteiros geradas aleatoriamente. Use sequências de 100 até 100000 números. (E mais se for possível.) Meça e compare os tempos de cada algoritmo.
  3. Repita os testes com sequências especiais: ordenadas em ordem crescente, ordenadas em ordem descrescente, com muitas repetições, com poucas repetições.
  4. No caso de mergesort e quicksort, interrompa a recursão quando o subproblema for pequeno e execute ordenação por inserção em cada subproblema. No caso de quicksort, faça o mesmo executando ordenação por inserção uma única vez, ao final do processo. Vale a pena fazer essas modificações? A partir de quando? Para qual definição de pequeno?
  5. Adapte os seus programas para ordenar palavras. Teste o desempenho de cada algoritmo no arquivo BR4.txt contendo 10000 palavras e no arquivo BR5.txt contendo 100000 palavras. Houve mudança do desempenho relativo dos algoritmos agora que comparar valores é mais complicado?