A ESTRUTURA DE DADOS I

[pic 1]

Implementação das árvores AVL e Rubro-Negra, Algoritmos de ordenação: Seleção, Quick Sort, Merge Sort, Heap Sort e Counting Sort.

Victor Hugo, Jhonatan Castelo, Vanessa, Arnold

Professor: Pedro Alberto Gomes

1. Árvore AVL

A arvore binária de pesquisa AVL tem comportamento mas demorado na inserção e remoção de chaves do que a arvore rubro-negra, porém a busca é muito mais rápida, isso se deve ao fato de que a arvore AVL é rigidamente balanceada, e também por isso ela faz mais rotações o que faz com que ela seja mais lenta na inserção e remoção. em todos os teste foram feitos 10 inserções para cada quantidade de chaves, com 100 inserções obteve média de 60-70 ms, com 1000 inserções 30-40 ms, 10000 inserções 2500-3000 ms, já a busca por chaves foi medida em nano segundos com média de 800-4000 ns.

[pic 2]

1. Árvore Rubro-Negra

A arvore rubro-negra foi muito superior na inserção de chaves com tempos abaixo de 1 ms, por isso foram feitos testes em nano segundos tanto na inserção quanto na busca.

[pic 3]

1. Algoritmos de ordenação

1. Seleção: É um algoritmo de ordenação que consiste em pegar o menor elemento de um vetor e colocá-lo na sua primeira posição, depois pegar o segundo menor e colocá-lo imediatamente após o ordenado anterior, e assim sucessivamente. Espera-se que ele seja o mais lento em tempo de ordenação.

[pic 4]

Verificou-se que na seleção a ordenação é muito mais lenta que os outros métodos, tanto que foi usado um número de entradas menor que estes outros métodos, e mesmo assim o tempo foi grande. Além disso, na ordenação de 1000 entradas nem chegou a fazer a contagem de tempo, pois a execução ficou extremamente lenta.

1. Quick Sort: É o método de “dividir para conquistar”, que consiste em escolher um elemento pivô e separar os menores para o lado esquerdo, e os maiores para o lado direito. Espera-se que ele seja o mais rápido em tempo de ordenação.

[pic 5]

Verificou-se que o método de ordenação Quick Sort é o mais rápido e obteve o melhor desempenho comparado aos outros métodos.

1. Merge Sort: É outro método que utiliza o “dividir para conquistar”, que consiste em dividir o vetor em duas partes iguais, depois em mais duas, e assim por diante até sobrarem apenas um ou dois elementos, os quais apenas o menor é selecionado e retirado de sua parte, depois os menores entre os restantes são comparados e assim vai até serem unidos. Espera-se que ele tenha um bom tempo de execução.

[pic 6]

Verificou-se que o Merge Sort tem um tempo de execução pior que o Quick Sort, porém, ainda é bem mais e rápido que a Seleção e um pouco mais rápido que o HeapSort.

1. Heap Sort: É um método que funciona como uma árvore binária. Espera-se que ele seja bastante eficiente com o tempo de execução.

[pic 7]

Verificou-se que o HeapSort tem um tempo de execução pior que o Merge Sort nos melhores e piores casos, porém em casos médios, o Heap Sort se comportou melhor. Além disso, tem um tempo de execução melhor que o da Seleção.