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

Algoritmos e Estruturas de Dados II 2º Semestre de 2006 Profs. Jussara, Luiz e Raquel

Aula Prática – Árvore e Ordenação

Data: 26/10/2006

A atividade pode ser realizada individualmente ou em dupla, de acordo com a preferência de cada aluno.

Ordenação:

Crie um vetor aleatório de 8 números inteiros.

Para cada um dos métodos vistos em sala (Bolha, Seleção, Inserção, Shellsort, Quicksort, Heapsort) faça:

1) Faça a ordenação do seu conjunto manualmente

2) Selecione no site (http://www.cs.pitt.edu/~kirk/cs1501/animations/Sort1.html) o método utilizado

3) Inspecione o código, tentando entender ele implementa o método em questão, mesmo que de forma diferente do código visto em sala.

4) Acompanhe a ordenação do seu conjunto, verificando se os passos foram os mesmos feitos por você na sua ordeanação manual. Em caso negativo, verifique se a diferença foi por causa da implementação utilizada, ou se você cometeu algum erro.

5) Anote o número de comparações e trocas necessárias para ordenar o conjunto

Ao fim da execução dos métodos, verifique as diferenças entre os números obtidos para as trocas e comparações. Os números obtidos estão de acordo com a análise de complexidade feita em sala? Como você explica métodos que têm a mesma complexidade e obtiveram números de comparações/cópias distintos?

Árvore:

Vá no site: http://www.iu.hio.no/~ulfu/AlgDat/applet/binarytreesome/

Para iniciar selecione uma árvore binária padrão (escolha na opção Tree o valor Standard) e depois a opção Insert. Para inserir os elementos selecione um conjunto de números randômicos e depois para cada um deles a sua posição dentre as disponíveis na árvore.

Pratique seu conhecimento sobre caminhamento na árvore. Para isso escolha o tipo de caminhamento, clique no botão Iterate e então vc deve clicar no nó da árvore que seria impresso a cada momento utilizando este caminhamento.

Caso vc tenha dúvidas o Hint explica de forma geral o caminhamento e o Solve o mostra para vc. Neste caso, tente entender e então fazer você mesmo.

Comparação entre métodos de ordenação:

Utilizando o programa disponível em: http://thomas.baudel.name/Visualisation/VisuTri/

1) Compare os métodos da Bolha, Inserção e Seleção e verifique a diferença no seu desempenho (comparações, trocas e tempo). Está de acordo com o que vimos em sala de aula.

2) Faça a comparação para diferentes tipos de entrada (aleatório, ordenado, ordem inverse). Qual deles é melhor em cada caso?

3) Faça o mesmo para os métodos Shellsort, Quicksort e Heapsort.

4) Faça as mesmas comparações utilizando os 6 métodos.

5) Caso surjam dúvidas visite as informações apresentadas no site sobre o método e veja se consegue solucioná-las.