Métodos de Pesquisa e Ordenação em Java

ASSOCIAÇÃO EDUCACIONAL DE VITÓRIA

FACULDADES INTEGRADAS SÃO PEDRO

CURSO DE GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

MAURICIO PEDROSO MOURA RIBEIRO

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

VITÓRIA

2018

1. INTRODUÇÃO

        Ao se trabalhar com grandes volumes de dados em um ambiente produtivo os algoritmos de pesquisa e ordenação precisam sofrer constante monitoramento afim de avaliar a sua eficiência de acordo com o crescimento das massas de dados as quais os mesmos atuarão. No contexto em questão, trabalharemos com 15 arquivos de dados de multas, com organizações diferenciadas (aleatória, ordenada e invertido) e com diferentes quantidades de registros (500, 1000, 5000, 10000, 50000) contendo as informações de placa, proprietário, local, data e hora e outro contendo apenas placas, que será utilizado para realização de pesquisas nas massas de dados.

Durante o primeiro semestre de 2018, na disciplina de Pesquisa e Ordenação, ministrada pela professora Cinthia Caliari, estudamos algoritmos de pesquisa e ordenação com uma abordagem predominante teórica. Neste trabalho, estes algoritmos serão implementados utilizando a linguagem de programação Java e programação orientada a objetos.

        Buscaremos apresentar de forma concisa a implementação dos principais métodos (Quicksort + Pesquisa Binária, Heapsort + Pesqusia Binária e Insertion Sort + Pesquisa Binária), simular os processos de pesquisa e ordenação com as diferentes bases de dados, cronometrando o tempo de execução das simulações e posteriormente gerar uma análise comparativa dos resultados.

---

2.         ESTRUTURA DO PROGRAMA

        O programa foi desenvolvimento entorno de 3 classes. A classe Multa responsável por instanciar o objeto Multa e seus atributos. A MultaVet responsável pela criação, organização, armazenado das Multas e dos métodos de manipulação das mesmas. E o Programa Principal (main) responsável por armazenar os métodos de leitura de arquivo, assim como rodar todos os passos do algoritmo do capítulo 3, expondo os resultados da execução para cada arquivo e método.

2.1        Classe Multa

[pic 1][pic 2]

[pic 3][pic 4]

---

2.2        Classe MultaVet[pic 5][pic 6]

[pic 7][pic 8][pic 9]

2.3        Programa Principal

[pic 10]

[pic 11][pic 12][pic 13]

---

3.         METODOLOGIA

        Para a realizar as simulações, devemos considerar os seguintes passos:

1. Comece a contar o tempo;
2. Carregue os dados de multas do arquivo “X” de (500/1000/5000/10000/50000) registros e da organização Z (aleatória, ordenada, inversa) para um vetor;
3. Ordene o vetor pela placa. Se houver duas ou mais placas iguais, os registros devem estar ordenados por data (dd/mm/aaaa) e por horário (hh:mm).
4. Grave todos os registros em um arquivo.
5. Utilize pesquisa binária para pesquisar as 400 placas contidas no arquivo de placas e grave os dados de cada multa encontrada no arquivo gerado pelo item 4, além de apresentar o total de multas encontradas. Caso não encontre nenhuma multa para determinada placa, gravar a mensagem “Sem multas”;
6. Finalize o tempo e guarde o tempo de execução.
7. Repita 5 vezes os processos dos itens 1 a 5 para cada método e arquivo.
8. Pegue o tempo total divida por 5 para obter a média do tempo de execução de cada método para cada arquivo.

3.1        Ordenação por placa/data/hora

Ao analisar os passos acima temos um grande desafio e a principal questão esta relacionado a ordenação dos dados de multas pela placa/data/hora. A forma mais eficiente encontrada para realizar tal ordenação foi criar uma lógica onde o programa ao instanciar um objeto multa converte a informação de placa + data + hora em um double gerando um ID único para cada registro de multa.

Para isso é necessário realizar o tratamento dos dados individualmente para atender os requisitos e gerar o ID.

3.1.1         Placa

        Ao receber a informação de placa o construtor deve converter os três primeiros caracteres em números conforme a tabela abaixo e concatena-los com os 4 dígitos em sequência.

        

DICIONÁRIO DE CONVERSÃO

A

->

10

F

->

15

K

->

20

P

->

25

U

->

30

B

->

11

G

->

16

L

->

21

Q

->

26

V

->

31

C

->

12

H

->

17

M

->

22

R

->

27

W

->

32

D

->

13

I

->

18

N

->

23

S

->

28

X

->

33

E

->

14

J

->

19

O

->

24

T

->

29

Y

->

34

Z

->

35

Ex:

Utilizamos para este exemplo e para os demais a seguinte informação (placa/data/hora):

...