Quarto Exercício-Programa

Estudo Experimental com Algoritmos de Ordenação

Entrega: 2 de julho

Para isso, você deve implementar os diversos algoritmos de ordenação que foram apresentados nas aulas e fazer pelo menos os seguintes testes (pode fazer outros se desejar, é claro):

• cronometar e contabilizar o número de comparações e atribuições envolvendo elementos do vetor em diversas execuções dos algoritmos para instâncias de diferentes tamanhos, e diferentes características (ordenado em ordem crescente e decrescente, parcialmente ordenado, gerado aleatoriamente, etc);
• construir tabelas e gráficos com esses dados para verificar se as complexidades teóricas se confirmam nos testes;
• construir algoritmos de ordenação combinados, que misturem, dependendo do tipo e tamanho da instância, execuções dos algoritmos acima, de forma que o tempo de processamento seja o melhor possível.

Junto com o seu EP, você deve entregar um relatório sobre seus experimentos. Você pode incluir outros testes que julgar interessantes. A nota do seu EP vai basear-se fortemente neste relatório.

O seu EP será apenas usado para conferirmos que suas tabelas e dados foram gerados adequadamente. Por isso, se você quiser, pode pegar implementações destes algoritmos de ordenação disponíveis na internet. Claro, escolha sempre uma fonte confiável para copiar, e dê os créditos devidamente, incluindo no código do EP e no seu relatório comentários dizendo de onde você obteve as implementações.

Gerador de números aleatórios em C

Como cronometrar os algoritmos em C

time.h

Avisos

• Não serão aceitos exercícios-programa atrasados, portanto comece cedo a fazer o seu EP!
• Todos os exercícios-programas devem ter um cabeçalho do seguinte tipo:

      /********************************************************/
      /* Fulano de Tal                                        */
      /* Exercicio-Programa xx                                */
      /* Disciplina yy            Professor:  Ciclano de Tal  */
      /********************************************************/
  

• Exercícios com erros de sintaxe (ou seja, erros de compilação) receberão nota ZERO.
• Seu programa deve estar bem indentado, bem documentado e organizado. Isso será fortemente levado em conta na sua nota.
• A entrega do EP deve ser feita no Sistema Moodle.
• Todos os alunos envolvidos com cola nos EPs serão reprovados na disciplina sem mais. Assim, não copie o EP de outra pessoa, nem empreste seu EP ou parte dele para ninguém. Seja cuidadoso para que alguém não copie seu EP sem a sua permissão.
• Guarde com você atê o final do semestre os arquivos de seus programas, pois eles podem ser solicitados pelo professor caso surja alguma dúvida.