MÉTODOS DE PESQUISA E ORDENAÇÃO EM JAVA
Por: YdecRupolo • 23/11/2017 • 666 Palavras (3 Páginas) • 422 Visualizações
...
Árvore ABB
Elementos
Aleatório
Invertido
Ordenado
500
0,038
0,031
0,028
1.000
0,031
0,049
0,072
5.000
0,115
0,809
0,836
10.000
0,015
2,487
3,827
50.000
0,654
137.465
166.882
Tabela 4 – Tempo de execução em milissegundos – Árvore ABB
5 ÁRVORE AVL
Os mesmos elementos foram inseridos em árvores AVL, cujo balanceamento é feito no momento da inserção de um novo elemento, quando necessário. Após o carregamento dos dados e a busca pelas 500 placas. Veja abaixo o desempenho do método.
Árvore AVL
Elementos
Aleatório
Invertido
Ordenado
500
0,291
0,097
0,037
1.000
0,028
0,019
0,039
5.000
0,006
0,047
0,044
10.000
0,239
0,292
0,179
50.000
0,894
0,694
0,596
Tabela 5 – Tempo de execução em milissegundos – Árvore AVL
6 COMPARAÇÃO ENTRE OS MÉTODOS
No gráfico abaixo, são mostradas para cada método as médias dos tempos de execução em segundos, entre as disposições aleatória, invertida e ordenada.
COMPARAÇÃO ENTRE OS MÉTODOS
Metodos
500
1.000
5.000
10.000
50.000
Quicksort
0,041
0,047
0,138
0,138
0,674
Quicksort com Inserção
0,013
0,013
0,063
0,091
0,437
Hashing
0,027
0,033
0,078
0,117
0,422
ABB
0,032
0,050
0,586
2,154
60,333
AVL
0,141
0,028
0,050
0,236
0,728
Tempo de execução em segundos – Comparação entre os métodos
7 CONCLUSÃO
Concluímos que o quicksort é realmente o mais rápido e eficiente entre os métodos de ordenação que se conhecem para uma ampla variedade de situações. Esse método adota a estratégia “Dividir para conquistar”, ele divide o vetor em 2 sub-vetores cada vez menores, e também houve uma melhoria de desempenho quando combinado com o método de inserção direta, para ordenar poucos elementos do vetor, com números de elementos inferior a 25, principalmente em conjuntos pequenos de dados, com até 5000 elementos. Conforme análise das tabelas 1 e 2, concluímos que o pior caso para o método quicksort ocorre quando os elementos estão aleatórios. Analisando as tabelas 4 e 5, percebe-se que a Árvore Binária de Busca (ABB) é um bom método de pesquisa
e ordenação, porém ao inserir grandes quantidades de elementos ordenados ou inversamente ordenados é muito custoso, pois a árvore fica desbalanceada, e tende a se tornar uma lista encadeada. O método da Árvore AVL é considerado melhor que a ABB, principalmente com grande quantidade de dados, fazendo uma comparação dispostos com 50 mil elementos ordenados foram gastos apenas 0.596s contra 166.882s na árvore ABB, também é visto uma melhoria de eficiência e rapidez quando os elementos estão ordenados inversamente, já que neste caso é evitado esta
degeneração em uma lista encadeada. O método hashing com vetor encadeado apresentou um ótimo desempenho com até 10 mil elementos, com pouca variação de tempo de execução para as disposições
...