PESQUISA E ORDENAÇÃO

[NOME DA INSTITUIÇÃO OCULTADO]

[NOME DOS ALUNOS OCULTADOS]

PESQUISA OPERACIONAL

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

VITÓRIA

2010

---

SUMÁRIO

1. INTRODUÇÃO............................................................................... 4
2. ANÁLISE........................................................................................ 6
3. CONCLUSÃO................................................................................10
4. BIBLIOGRAFIA..............................................................................12

---

RESUMO

        Este trabalho tem como objetivo demonstrar os métodos e algoritmos de pesquisa e ordenação estudados, tais como: QuickSort, HeapSort, Pesquisa Binária, Árvore Binária entre outros.

---

1. INTRODUÇÃO

Existem vários algoritmos para pesquisa e ordenação. Abaixo segue uma sucinta descrição de alguns que serão abordados neste trabalho:

• QuickSort: método de ordenação por comparação não-estável. Muito rápido e eficiente.
• HeapSort: O princípio de funcionamento deste método baseia-se na idéia de uma heap. Uma heap é uma árvore binária com as seguintes características:

• A maior chave está sempre na raiz da árvore.
• O sucessor à esquerda do elemento de índice i é o elemento de índice 2i e o sucessor à direita é o elemento de índice 2i + 1, sendo que a chave de cada nó é maior ou igual às chaves de seus filhos.

• Pesquisa Binária: A pesquisa em uma tabela pode ser muito mais eficiente se os registros estiverem ordenados. A estratégia da Pesquisa Binária é a seguinte:

• Compara-se a chave de pesquisa com a chave do registro que está no meio do vetor:

• Se a chave de busca for menor que a chave deste registro, então o registro procurado deve estar na primeira metade da tabela;
• Se maior, então deve estar na segunda metade;
• Se igual, a pesquisa foi realizada com sucesso.

• O processo deve ser repetido até se encontrar o registro (pesquisa com sucesso) ou ficar apenas um registro com chave diferente da chave de pesquisa (pesquisa sem sucesso).

• Árvore Binária: São estruturas de dados muito eficientes para armazenar informações. São utilizadas quando há necessidade dos seguintes requisitos:

• Acessos direto e seqüencial eficientes;
• Facilidade de inserção e remoção de elementos;
• Alta taxa de utilização de memória;
• Utilização de memória primária e secundária.
  Ao analisar esses requisitos de forma separada, podemos achar estruturas de dados melhores, mas ao juntarmos todos ou alguns dos requisitos, as árvores de busca são a melhor solução.

• Árvore AVL: a árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade. As operações de busca, inserção e eliminação de elementos possuem complexidade O(log n) (no qual n  é o número de elementos da árvore). Inserções e eliminações podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.
• Hashing: Os métodos de pesquisa apresentados são baseados na comparação entre a chave de pesquisa e as chaves armazenadas na tabela. O método de transformação de chave (hashing) é completamente diferente, pois os registros são armazenados em uma tabela e podem ser endereçados diretamente através de uma transformação aritmética sobre a chave de pesquisa.

---

1. ANÁLISE

Abaixo a análise feita sobre o tempo de cada algoritmo e método de pesquisa nas diversas ocasiões (tempo medido em milissegundos):

• 500 registros

QuickSort

	Vetor	Ordenação	Pesquisa	Gravação
Aleatório	13	8	4	5
Ordenado	2	2	1	7
Inverso	2	3	0	10

QuickSort com Inserção Direta

	Vetor	Ordenação	Pesquisa	Gravação
Aleatório	13	4	4	5
Ordenado	2	2	1	7
Inverso	2	2	0	10

HeapSort

	Vetor	Ordenação	Pesquisa	Gravação
Aleatório	13	9	4	5
Ordenado	2	7	1	7
Inverso	2	6	0	10

Árvore Binária de Busca Balanceada (ABB Balanceada)

	Árvore	Balanceamento	Pesquisa	Gravação
Aleatório	2	0	1	5
Ordenado	2	1	0	8
Inverso	3	0	1	12

Árvores AVL

	Árvore + Balanceamento	Pesquisa	Gravação
Aleatório	2	1	7
Ordenado	0	1	9
Inverso	0	1	15

Hashing com Vetor Encadeado

	Árvore	Pesquisa	Gravação
Aleatório	2	0	???
Ordenado	1	0	???
Inverso	1	0	???