TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

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

Por:   •  14/3/2016  •  Trabalho acadêmico  •  757 Palavras (4 Páginas)  •  790 Visualizações

Página 1 de 4

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

...

Baixar como (para membros premium)  txt (6.4 Kb)   pdf (170.3 Kb)   docx (15.6 Kb)  
Continuar por mais 3 páginas »
Disponível apenas no TrabalhosGratuitos.com