A CLASSIFICAÇÃO E PESQUISA

[pic 1]

[pic 2][pic 3]

[pic 4]

[pic 5]

CAMPO GRANDE

2018

EDUARDO AMARAL DE OLIVEIRA[pic 6]

[pic 7]

Classificação e pesquisa

Trabalho de tutoria apresentado ao Curso de Engenharia da Computação da Instituição Anhanguera-Uniderp.

Professora: Adriane Cristina C S Veronez

Campo Grande

2018

SUMÁRIO[pic 8]

1. PESQUISA DE DADOS        3

1.1. PESQUISA SEQUENCIAL        3

1.2. PESQUISA BINÁRIA        3

2. MÉTODOS DE ORDENAÇÃO        4

2.1. MÉTODOS SIMPLES        4

2.1.1. INSERTION SORT        4

2.2. MÉTODOS EFICIENTES        4

2.2.1 QUICK SORT        4

3. ARVORE BINARIA        5

4. ÁRVORES AVL        6

5. TABELAS HASH        7

REFERÊNCIA…………………………………………………………………………………………8

1. PESQUISA DE DADOS

1.1. PESQUISA SEQUENCIAL

Quando itens de dados são armazenados em uma coleção, como uma lista, dizemos que eles têm uma relação linear ou sequencial. Cada item de dados é armazenado em uma posição relativa aos outros. Nas listas vetores, essas posições relativas são os valores de índice dos itens individuais. Como esses valores de índice são ordenados, é possível para nós visitá-los em sequência. Este processo dá origem a nossa primeira técnica de pesquisa, a pesquisa sequencial.

A partir do primeiro item da lista, simplesmente passamos de item para item, seguindo o pedido sequencial até encontrar o que estamos procurando ou ficar sem itens. Se ficarmos sem itens, então o item que procuramos não estava presente.

No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após (N+1)/2 comparações. O algoritmo de busca linear é um algoritmo O(n).

1.2. PESQUISA BINÁRIA

Caso você possua uma lista com os valores ordenados de forma numérica ou alfabética, é possível fazer uma busca muito mais rápida. Ao invés de pesquisar a lista em sequência, uma busca binária começará examinando o item do meio. Se esse item for aquele que estamos procurando, a busca termina. Se não for o item correto, podemos usar a natureza ordenada da lista para eliminar a metade dos itens restantes. Se o item que procuramos for maior do que o item do meio, sabemos que toda a metade inferior da lista, bem como o item do meio, podem ser eliminados de uma consideração mais aprofundada.

Repetimos então o processo com a metade superior. Comece comparando o item do meio com o que estamos procurando. Novamente, encontramos ou dividimos a lista pela metade, eliminando grande parte do nosso espaço de busca.

A complexidade desse algoritmo é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).

2. MÉTODOS DE ORDENAÇÃO

2.1. MÉTODOS SIMPLES

Os métodos simples são adequados para pequenos vetores, são programas pequenos e fáceis de entender. Possuem complexidade C(n) = O(n²), ou seja, requerem O(n²) comparações. Exemplos: Insertion Sort, Selection Sort, Bubble Sort, Comb Sort.

Nos algoritmos de ordenação as medidas de complexidade relevantes são:

• Número de comparações C(n) entre chaves.
• Número de movimentações M(n) dos registros dos vetores.
• Onde n é o número de registros.

2.1.1. INSERTION SORT

Insertion Sort ou ordenação por inserção é o método que percorre um vetor de elementos da esquerda para a direita e à medida que avança vai ordenando os elementos à esquerda. Possui complexidade C(n) = O(n) no melhor caso e C(n) = O(n²) no caso médio e pior caso. É considerado um método de ordenação estável.

O funcionamento do algoritmo é bem simples: consiste em cada passo a partir do segundo elemento selecionar o próximo item da sequência e colocá-lo no local apropriado de acordo com o critério de ordenação.

2.2. MÉTODOS EFICIENTES

Os métodos eficientes são mais complexos nos detalhes, requerem um número menor de comparações. São projetados para trabalhar com uma quantidade maior de dados e possuem complexidade C(n) = O(n log n). Exemplos: Quick sort, Merge sort, Shell sort, Heap sort, Radix sort, Gnome sort, Count sort, Bucket sort, Cocktail sort, Timsort.

2.2.1 QUICK SORT

O Algoritmo Quicksort, criado por C. A. R. Hoare em 1960, é o método de ordenação interna mais rápido que se conhece para uma ampla variedade de situações.

Provavelmente é o mais utilizado. Possui complexidade C(n) = O(n²) no pior caso e C(n) = O(n log n) no melhor e médio caso e não é um algoritmo estável.

É um algoritmo de comparação que emprega a estratégia de “divisão e conquista”. A ideia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores. Os problemas menores são ordenados independentemente e os resultados são combinados para produzir a solução final.

Basicamente a operação do algoritmo pode ser resumida na seguinte estratégia: divide sua lista de entrada em duas sub-listas a partir de um pivô, para em seguida realizar o mesmo procedimento nas duas listas menores até uma lista unitária.

Funcionamento do algoritmo:

Escolhe um elemento da lista chamado pivô. Reorganiza a lista de forma que os elementos menores que o pivô fique de um lado, e os maiores fiquem de outro. Esta operação é chamada de “particionamento”. Recursivamente ordena a sub-lista abaixo e acima do pivô.

3. ARVORE BINARIA

Uma árvore binária de busca é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação).