MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MONITOR Paulo E. Silveira

E-MAIL peas@ime.usp.br

MAC 122 - Princípios de Desenvolvimento de Algoritmos
http://panda.ime.usp.br

Exercício-Programa 3 - Entrega: 5 de novembro

Ordenação de vetores

O objetivo desse exercício é verificar empiricamente os resultados que obtivemos a respeito da complexidade dos algoritmos de ordenação que estudamos. 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 trocas entre 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, 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.

Faça um relatório sobre seus experimentos. Você pode incluir outros testes que julgar interessantes.