MÉTODOS DE PESQUISA E ORDENAÇÃO EM JAVA

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