71
# Estrutura de Dados # Aula 14 Técnicas de Pesquisa e Ordenação Prof. Leinylson Fontinele Pereira

Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Embed Size (px)

Citation preview

Page 1: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

# Estrutura de Dados #Aula 14 – Técnicas de Pesquisa e Ordenação

Prof. Leinylson Fontinele Pereira

Page 2: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Na aula anterior...

Árvores# Conceito

# Elementos

# Tipos

# Onde são utilizadas?

21:30 Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 3: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Introdução

21:30 3 Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 4: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

O que vamos aprender?

Técnicas# Pesquisa

# Ordenação

# Comparação dos algoritmos

21:30 Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 5: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Vamos começar?

21:30 5 Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 6: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 6

Busca

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 7: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Busca Recuperação de dados armazenados em um repositório ou base de

dados

Tipo de busca depende dos dados

Dados estão estruturados (vetor, lista, árvore)

Dados ordenados (ou não ordenados)

Valores duplicados

Page 8: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Tipos de busca e métodos abordados

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Busca

Dados armazenados em um vetor

Dados ordenados

Métodos

Busca Linear

Busca Ordenada

Busca Binária

Page 9: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca Linear

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 10: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca Ordenada

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 11: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca Binária

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 12: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca Binária

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 13: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca Binária: exemplo

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 14: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 14

Busca em Vetor de Struct

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 15: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca em Vetor de Struct

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 16: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Busca em Vetor de Struct

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 17: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 17

Ordenação

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 18: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Ordenar corresponde ao processo de rearranjar um conjuntode objetos em ordem ascendente ou descendente

O objetivo principal da ordenação é facilitar a recuperaçãoposterior de itens do conjunto ordenado

As ordens mais utilizadas são a numérica e lexicográfica

Existem diversos algoritmos de ordenação!

Page 19: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

O problema da ordenação consiste em rearranjar um

vetor 𝑣[0. . 𝑛1] em ordem crescente

Ou seja, permutar os elementos do vetor de modo que

tenhamos 𝑣[0] ≤ 𝑣[1] ≤ . . . ≤ 𝑣[𝑛 − 1].

Page 20: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

O Problema da Separação

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Rearranjar um vetor 𝑣[𝑝. . 𝑟] de modo que todos oselementos pequenos fiquem na parte esquerda do vetore todos os elementos grandes fiquem na parte direita

Page 21: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 21

Ordenação comBubbleSort

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 22: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com BubbleSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

O principio do bolha é a troca de valores entre posiçõesconsecutivas fazendo com que os valores mais altos“borbulhem” para o final do vetor.

Pior caso = 𝑂(𝑛²)

Melhor caso =𝑂(𝑛)

Não recomendado para grandes conjuntos de dados

Page 23: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com BubbleSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Compara pares de elementos adjacentes e os troca delugar se estiverem na ordem errada

Page 24: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com BubbleSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 25: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com BubbleSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 26: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com BubbleSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 27: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com BubbleSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 28: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 28

Ordenação comInsertionSort

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 29: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com InsertionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Em cada passo, a partir do 𝑖 = 2, oI-ésimo elemento da sequência fonteé apanhado e transferido para asequência destino, sendo inserido noseu lugar apropriado.

Page 30: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com InsertionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Pior caso = 𝑂(𝑛²)

Melhor caso = 𝑂(𝑛)

Page 31: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com InsertionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 32: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com InsertionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 33: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com InsertionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 34: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 34

Ordenação comSelectionSort

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 35: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com SelectionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Procura-se o 1ºmenor e se posiciona na 1ª posição

Procura-se o 2ºmenor e se posiciona na 2ª posição

...

Pior caso = 𝑂(𝑛²)

Melhor caso = 𝑂(𝑛²)

Page 36: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com SelectionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 37: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com SelectionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 38: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

SelectionSort: Troca de conteúdo de variáveis

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 39: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

SelectionSort: Troca de conteúdo de variáveis

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 40: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

SelectionSort: Troca de conteúdo de variáveis

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 41: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com SelectionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Quanto tempo o algoritmo consome para fazer o serviço?

Page 42: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com SelectionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 43: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com SelectionSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 44: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 45

Ordenação comMergeSortEstrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 45: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Idéia básica: Dividir e Conquistar

Divide, recursivamente, o conjunto de dados até quecada subconjunto possua 1 elemento

Melhor caso:𝑂(𝑛𝑙𝑜𝑔𝑛)

Pior caso:𝑂(𝑛𝑙𝑜𝑔𝑛)

Page 46: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 47: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 48: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 49: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 50: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Intercalação de Vetores

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 51: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Intercalação de Vetores

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 52: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 53: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com MergeSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 54: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 55

Ordenação comQuickSortEstrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 55: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com QuickSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Ordenação por troca de partições

Dividir e Conquistar

Um elemento é escolhido como pivô Valores menores que o pivô são colocados antes dele e os

maiores, depois

Melhor caso:𝑂(𝑛𝑙𝑜𝑔𝑛) Pior caso (raro): 𝑂(𝑛2)

Page 56: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com QuickSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 57: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com QuickSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 58: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com QuickSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 59: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com QuickSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 60: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com QuickSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 61: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

21:30 62

Ordenação comHeapSort

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 62: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com HeapSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Heap: vetor que simula uma árvore binária completa (exceçãodo último nível)

Todo elemento pai do vetor possui dois elementos como filhos

pai(i) -> filhos: (2 ∗ 𝑖 + 1) e (2 ∗ 𝑖 + 2)

Page 63: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com HeapSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Todo elemento pai do vetor possui dois elementos como filhos

pai(i) -> filhos: (2 ∗ 𝑖 + 1) e (2 ∗ 𝑖 + 2)

Page 64: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com HeapSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 65: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com HeapSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 66: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com HeapSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 67: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Ordenação com HeapSort

21:30Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 68: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Concluindo...

21:30 69 Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 69: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Nesta aula aprendemos... Técnicas

# Pesquisa

# Ordenação

# Comparação dos algoritmos

21:30 Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 70: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Material: https://sites.google.com/site/leinylsonnassau

21:31

Material baseado nas aulas de:

Linguagem C Descomplicada , Dr. André R. Backes

Estrutura de Dados: Aula 14 – Técnicas de Pesquisa e Ordenação

Page 71: Estrutura de Dados Aula 14 - Técnicas de Pesquisa e Ordenação (conceitos e algoritmos)

Alguma Dúvida?

21:30

Até a próxima aula...

[email protected]