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

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

Introdução

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

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

Vamos começar?

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

21:30 6

Busca

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

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

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

Busca Linear

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

Busca Ordenada

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

Busca Binária

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

Busca Binária

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

Busca Binária: exemplo

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

21:30 14

Busca em Vetor de Struct

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

Busca em Vetor de Struct

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

Busca em Vetor de Struct

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

21:30 17

Ordenação

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

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!

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].

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

21:30 21

Ordenação comBubbleSort

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

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

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

Ordenação com BubbleSort

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

Ordenação com BubbleSort

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

Ordenação com BubbleSort

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

Ordenação com BubbleSort

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

21:30 28

Ordenação comInsertionSort

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

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.

Ordenação com InsertionSort

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

Pior caso = 𝑂(𝑛²)

Melhor caso = 𝑂(𝑛)

Ordenação com InsertionSort

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

Ordenação com InsertionSort

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

Ordenação com InsertionSort

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

21:30 34

Ordenação comSelectionSort

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

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 = 𝑂(𝑛²)

Ordenação com SelectionSort

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

Ordenação com SelectionSort

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

SelectionSort: Troca de conteúdo de variáveis

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

SelectionSort: Troca de conteúdo de variáveis

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

SelectionSort: Troca de conteúdo de variáveis

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

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?

Ordenação com SelectionSort

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

Ordenação com SelectionSort

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

21:30 45

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

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:𝑂(𝑛𝑙𝑜𝑔𝑛)

Ordenação com MergeSort

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

Ordenação com MergeSort

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

Ordenação com MergeSort

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

Ordenação com MergeSort

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

Intercalação de Vetores

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

Intercalação de Vetores

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

Ordenação com MergeSort

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

Ordenação com MergeSort

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

21:30 55

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

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)

Ordenação com QuickSort

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

Ordenação com QuickSort

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

Ordenação com QuickSort

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

Ordenação com QuickSort

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

Ordenação com QuickSort

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

21:30 62

Ordenação comHeapSort

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

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)

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)

Ordenação com HeapSort

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

Ordenação com HeapSort

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

Ordenação com HeapSort

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

Ordenação com HeapSort

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

Concluindo...

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

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

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

Alguma Dúvida?

21:30

Até a próxima aula...

leinylson@gmail.com