MÉTODOS DE PESQUISA E ORDENAÇÃO EM JAVA
Por: patricktellesb • 14/3/2016 • Trabalho acadêmico • 757 Palavras (4 Páginas) • 852 Visualizações
FUNDAÇÃO DE ASSISTÊNCIA E EDUCAÇÃO – FAESA
FACULDADES INTEGRADAS ESPIRITO-SANTENSES
GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
ANDERSON
JOÃO HELITON SILVA BRANDEMBURG
RAINER BOLSONE
MÉTODOS DE PESQUISA E ORDENAÇÃO EM JAVA
VITÓRIA
2015
1 INTRODUÇÃO
Neste trabalho foi feito a análise e comparação de alguns métodos de pesquisa e ordenação, tais como: ShellSort + Pesquisa Binária, HeapSort + Pesquisa Binária, QuickSort + Pesquisa Binária, Quicksort com Inserção Direta + Pesquisa Binária, Árvore Binária de Pesquisa Balanceada, Árvore AVL, Hashing com Vetor Encadeado. Os métodos foram implementados e testados em conjuntos de 500, 1000, 5000, 10000 e 50000 elementos, dispostos em conjuntos ordenados, aleatórios e invertidos. Foram calculados os tempos de execução de todos os métodos de pesquisa e ordenação para cada um dos conjuntos, para fins de comparação e desempenho de cada método. Cada elemento representa uma multa, tendo como atributos: placa do veículo, nome do proprietário, local, data e horário da multa.
2 QUICKSORT + PESQUISA BINÁRIA
Implementamos o método QuickSort e posteriormente foi feita uma Pequisa Binária por 500 placas de veículos.
2.1 COM INSERÇÃO DIRETA
Foram computados os tempos de execução quando combinado o método QuickSort com o método Inserção Direta, quando necessário ordenar uma parte do vetor com elementos menor que 25. Os resultados obtidos são mostrados na Tabela 1.
QuickSort com Inserção Direta | |||
Elementos | Aleatório | Invertido | Ordenado |
500 | 0,013 | 0,012 | 0,016 |
1.000 | 0,021 | 0,016 | 0,014 |
5.000 | 0,047 | 0,069 | 0,065 |
10.000 | 0,128 | 0,073 | 0,073 |
50.000 | 0,042 | 0,285 | 0,607 |
Tabela 1 – Tempo de execução em milissegundos – QuickSort com Inserção
2.2 SEM INSERÇÃO DIRETA
Utilizando somente o método QuickSort para a ordenação, foram obtidos os seguintes tempos mostrados na Tabela 2.
QuickSort | |||
Elementos | Aleatório | Invertido | Ordenado |
500 | 0,034 | 0,034 | 0,044 |
1.000 | 0,044 | 0,048 | 0,049 |
5.000 | 0,091 | 0,088 | 0,097 |
10.000 | 0,137 | 0,118 | 0,161 |
50.000 | 0,767 | 0,638 | 617 |
Tabela 2 – Tempo de execução em milissegundos – QuickSort
3 HASHING COM VETOR ENCADEADO
Foi medido o desempenho do algoritmo de hashing com vetor encadeado. Os tempos são expostos na Tabela 3 a seguir.
Hashing com vetor encadeado | |||
Elementos | Aleatório | Invertido | Ordenado |
500 | 0,028 | 0,025 | 0,028 |
1.000 | 0,035 | 0,033 | 0,032 |
5.000 | 0,084 | 0,075 | 0,075 |
10.000 | 0,132 | 0,121 | 0,099 |
50.000 | 0,415 | 0,501 | 0,352 |
Tabela 3 – Tempo de execução em milissegundos – Hashing com vetor encadeado
4 ÁRVORE BINÁRIA DE BUSCA (ABB)
Os diferentes conjuntos de dados foram carregados em árvores binárias de busca (ABB). Após o balanceamento, foram feitas as pesquisas pelas mesmas 500 placas. Os tempos computados são mostrados a seguir na Tabela 4.
Á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 |
...