Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

Última alteração: Fevereiro 26, 2002

ENGENHARIA DE CONTROLE E AUTOMAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Nivio Ziviani

Monitora: Claudine Santos Badue

Trabalho Prático 3

Data de Entrega: 07-março-2002

Comentários Gerais

1.: Comece a fazer este trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.
2.: Penalização por atraso: vide texto apresentação da disciplina.
3.: Este trabalho exercita conceitos sobre métodos de ordenação apresentados no Capítulo 3 do livro Projeto de Algoritmos Com Implementações em Pascal e C.
4.: Vão valer pontos clareza, indentação e comentários no programa.

Algoritmos de Ordenação: Estudos Comparativos

O objetivo deste trabalho é testar e avaliar o desempenho de vários métodos de ordenação. Você deverá escrever um programa em Pascal, bem modularizado, que contenha os seguintes pontos:

1.: declaração dos tipos utilizados (TipoChave, TipoItem, Vetor, etc.);
2.: criar diferentes listas de itens a serem ordenados, utilizando um gerador de números aleatórios para gerar as chaves, que devem ser números inteiros. Crie arquivos de tamanhos diversos. É melhor manter as listas de chaves em arquivos permanentes, para que possam ser reutilizados para avaliar diferentes métodos de ordenação;
3.: imprimir as chaves não ordenadas, se o usuário desejar;
4.: ordenar as chaves, utilizando algoritmos diferentes;
5.: imprimir as chaves ordenadas, se o usuário desejar;
6.: determinar o tempo de processamento necessário na fase de ordenação, utilizando o relógio da máquina;
7.: manter contadores (que devem ser atualizados pelos procedimentos de ordenação) para armazenar o número de comparações e de movimentações de itens executados pelos algoritmos.

Métodos a Serem Estudados

Neste trabalho, estude o comportamento dos seguintes algoritmos:

(1) Seleção, (2) Inserção, (3) Quicksort, (4) Heapsort.

Como Fazer

Execute o programa algumas vezes, com cada algoritmo de ordenação, com massas de dados diferentes, para obter a média dos tempos de execução, do número de comparações e do número de movimentações. Utilize o procedimento Permut abaixo para obter uma permutacao randômica das chaves.

Program Teste;

type Vetor= array[1..20] of integer;

procedure Permut (var A: Vetor; n: integer);
{ Obtem permutacao randomica dos numeros entre 1 e n }
var i, j, b: integer;
begin
  for i:= n downto 2 do 
  begin
    j:= Trunc (i * Random + 1);
    b:= A[i];
    A[i] := A[j];
    A[j] := b;
  end;
end;

var A: Vetor;
    n, i: integer;

begin
  randomize;
  n := 10;
  for i := 1 to n do A[i] := i;
  Permut (A, n);
  for i:= 1 to n do Write(A[i]," ");
  writeln;
end.

Repita o experimento com uma massa de dados que force o pior caso do método em estudo.

O que deve ser apresentado

1.: Listagem do programa em Pascal.
2.: Listagem dos testes executados.
3.: Estudo da complexidade do tempo de execução dos procedimentos implementados usando (notação O).
4.: Gráficos e/ou tabelas comparando os resultados dos experimentos. Dê a sua interpretação dos resultados obtidos.

Avaliação

1.

Execução

(a): Execução correta: 20%
(b): Saída legível: 10%

2.

Estilo de programação

(a): Código bem estruturado: 10%
(b): Código legível: 10%

3.

Documentação

(a): Comparação e interpretação dos resultados obtidos: 50%