Baixe o app para aproveitar ainda mais
Prévia do material em texto
CLASSIFICAÇÃO E PESQUISA Prof. Odair Moreira de Souza Unidade 01 Encontro 03 Algoritmos de Classificação Recapitulando... • Introdução à classificação de dados e pesquisa •Algoritmos de Classificação: • shellSort(); • mergeSort(); 29-Aug-17 3Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza Conteúdo Algoritmos de classificação de dados: • quickSort(); • heapSort(); 29-Aug-17 4Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza quickSort(); quickSort(); •Melhoramento do bubble-sort •Troca de elementos distantes são mais efetivas •Dividir para conquistar •Idéia básica: •Dividir o vetor em dois vetores menores que serão ordenados independentemente e combinados para produzir o resultado final 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 6 quickSort(); •Algoritmo para o particionamento: • 1. Escolha arbitrariamente um pivô x. • 2. Percorra o vetor a partir da esquerda até que A[i] ≥ x. • 3. Percorra o vetor a partir da direita até que A[j] ≤ x. • 4. Troque A[i] com A[j]. • 5. Continue este processo até os apontadores i e j se cruzarem. •Ao final, o vetor A[Esq..Dir] está particionado de tal forma que: •Os itens em A[Esq], A[Esq + 1], . . . , A[j] são menores ou iguais a x. •Os itens em A[i], A[i + 1], . . . , A[Dir] são maiores ou iguais a x. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 7 quickSort(); •A parte mais delicada do método é o processo de partição. •O vetor A [Esq ... Dir] é rearranjado por meio da escolha arbitrária de um pivô x. •O vetor A é particionado em duas partes: •Parte esquerda: chaves ≤ x. •Parte direita: chaves > x. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 8 quickSort(); •Divisão: seleciona um elemento x (chamado pivô) e divide v em: •L elementos menores ou iguais a x •G elementos maiores ou iguais a x •Recursão: ordenar L e G 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 9 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 10 quickSort(); •Situação crítica na escolha do Pivô: 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 11 quickSort(); •Aplicar o algoritmo quickSort no conjunto de chaves: •A = {25, 57, 35, 37, 12, 86, 92, 33} •Demostração •Visualização 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 12 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 13 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 14 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 15 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 16 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 17 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 18 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 19 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 20 •Uma execução do QuickSort pode ser representada por uma árvore binária; •Cada nó representa uma chamada recursiva e exibe: • 1. A sequência não ordenada e seu pivô • 2. A sequência ordenada (na volta das chamadas recursivas) •A raiz representa a chamada inicial a QuickSort •Os nós-folha tem 0 ou 1 elementos quickSort(); 29-Aug-17 21 quickSort(); 29-Aug-17 22 quickSort(); 29-Aug-17 23 quickSort(); 29-Aug-17 24 quickSort(); 29-Aug-17 25 quickSort(); 29-Aug-17 26 quickSort(); 29-Aug-17 27 quickSort(); 29-Aug-17 28 quickSort(); •Exercício: •Ordene os subvetores, repetindo o processo para cada um deles. A = {12, 95, 35, 12, 17, 86, 92, 05, 59} O processo é aplicado até que toda partição contenha apenas um (ou nenhum) item. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 29 quickSort(); – Complexidade •Pior caso: •C(n) = O(n²) •O pior caso ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos extremos de uma coleção já ordenada. • Isto faz com que o procedimento QUICKSORT seja chamado recursivamente n vezes, eliminando apenas um item em cada chamada. •O pior caso pode ser evitado empregando pequenas modificações no algoritmo. •Para isso basta escolher três itens quaisquer do vetor e usar a mediana dos três como pivô. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 30 quickSort(); – Complexidade • Melhor caso: C(n) = 2C(n/2) + n = nlog n − n + 1 • Esta situação ocorre quando cada partição divide a coleção em duas partes iguais. • Caso médio de acordo com Sedgewick e Flajolet (1996, p. 17): • C(n) ≈ 1,386nlog n − 0,846n, • Isso significa que em média o tempo de execução do Quicksort é • O(nlog n) 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 31 quickSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 32 quickSort(); •Vantagens: •É extremamente eficiente para ordenar arquivos de dados. •Necessita de apenas uma pequena pilha como memória auxiliar. •Requer cerca de n log n comparações em média para ordenar n itens. •Desvantagens: •Tem um pior caso O(n²) comparações. •Sua implementação é muito delicada e difícil: •Um pequeno engano pode levar a efeitos inesperados para algumas entradas de dados. •O método não é estável. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 33 quickSort(); • QUICK SORT É ESTÁVEL? 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 34 Exercício 1. Escreva um programa que carregue um vetor com 10 números inteiros e o ordene em ordem crescente, usando o método quickSort(). O programa deve gerar um segundo vetor sem os números repetidos. Exemplo: Números digitados: 5, 9, 4, 5, 6, 2, 5, 9, 1, 4 Vetor ordenado: 1, 2, 4, 4, 5, 5, 5, 6, 9, 9, Segundo vetor gerado: 1, 2, 4, 5, 6, 9 29-Aug-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 35 heapSort(); heapSort(); •Basicamente a mesma ideia do funcionamento do algoritmo de classificação por seleção. •Algoritmos: • 1. Seleciona o menor item do conjunto; • 2. Troque-o com o item da primeira posição do conjunto; • 3. Repita estas operações com os n-1 itens, depois com os n-2 itens, isso até o fim. •O custo para encontrar o menor (ou maior) item entre n itens é n-1 comparações. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 37 heapSort(); •É uma estrutura de dados onde a chave de cada item reflete sua habilidade relativa de abandonar o conjunto de itens rapidamente. •Aplicações: •Sistema Operacionais no gerenciamento dos processos. •Métodos numéricos iterativos são baseados na seleção repetida de um item com maior (menor) valor. •Sistemas de gerência de memória usam a técnica de substituir a página menos utilizada na memória principal por uma nova página. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 38 heapSort(); •Heap: vetor que pode ser visto como uma árvore binária totalmente preenchida em todos os níveis exceto, possivelmente,o último. •O último nível é preenchido da esquerda para a direita até um certo ponto. •O vetor A que representa um heap possui dois atributos: • tamanho (length[A]) e número de elementos no vetor (heap_size[A]). 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 39 heapSort(); •Propriedade: •O valor de um nodo é sempre menor ou igual ao valor de seu nodo pai • A[Pai(i)] ≥ A[i], ∀ i ≤ heap_size[A] •O elemento de maior valor encontra-se armazenado na raiz da árvore 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 40 Um heap é uma estrutura na qual cada cada pai é maior que cada um de seus filhos. heapSort(); •Num vetor com N elementos, indexados de 0 a N-1, organizado num heap, cada nó tem seus filhos calculados por: 2i+1 e 2(i+1). •Exemplo: •0 -> 1 e 2 •1 -> 3 e 4 •2 -> 5 e 6 •... •N -> 2n+1 e 2(n+1) 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 41 heapSort(); •No primeiro passo, é necessário organizar o vetor a ser ordenado como um heap. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 42 heapSort(); •Heap •Filhos do nó i: • filho esquerdo = 2i + 1 • filho direito = 2i + 2 •Pai do nó i: (i-1)/2 •Folhas de i/2 em diante 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 43 heapSort(); •Obtemos um heap aplicando uma função que "desce" um elemento, trocando-o com o maior dos filhos, caso ele não seja maior que um deles. •Este algoritmo deve ser realizado repetidamente, até que a regra de heap seja satisfeita, ou até que não haja mais filhos para comparar (o valor chegou a uma folha). 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 44 heapSort(); – Implementação Heapify: Garante a manutenção da propriedade do heap. Executa em O(logn) BuildHeap: Produz um heap a partir de um vetor não ordenado. Executa em O(n) Heapsort: Procedimento de ordenação local. Executa em O(nlogn) 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 45 heapSort(); – Implementação Heapify: Reorganiza heaps Supõe que as árvores binárias correspondentes a Esquerda(i) e Direita(i) são heaps, mas A[i] pode ser menor que seus filhos 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 46 heapSort(); •Aplicar o algoritmo heapSort no conjunto de chaves: •A = {25, 57, 35, 37, 12, 86, 92, 33} •Demostração •Visualização 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 47 heapSort(); 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 48 heapSort(); – Complexidade: •HeapSort Vantagens: • O comportamento do Heapsort é sempre O(nlog n), qualquer que seja a entrada. •Desvantagens: • O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort. • O Heapsort não é estável. •Recomendado: • Para aplicações que não podem tolerar eventualmente um caso desfavorável. • Não é recomendado para arquivos com poucos registros, por causa do tempo necessário para construir o heap. 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 49 heapSort(); – Complexidade: •Pior Caso: O(N log N) •Caso médio: O(N log N) •Melhor Caso: O(N log N) •Espaço Pior Caso: O(n) total, O(1) auxiliar 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 50 heapSort(); – Complexidade: •HeapSort – Exercícios: • 1. Utilize o procedimento Build-Heap para construir um heap a partir do vetor V = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7} • 2. Por que no laço do procedimento Build-Heap fazemos o valor da variável “i” variar de length[A]/2 até 1 ao invés de de 1 até length[A]/2? 29-Aug-17 TSI32B - Estrutura, pesquisa e ordenação de dados Odair Moreira de Souza 51 Exercício 2. Escreva um programa que carregue um vetor com 10 números inteiros e o ordene em ordem crescente, usando o método heapSort(). O programa deve gerar um segundo vetor sem os números repetidos. Exemplo: Números digitados: 5, 9, 4, 5, 6, 2, 5, 9, 1, 4 Vetor ordenado: 1, 2, 4, 4, 5, 5, 5, 6, 9, 9, Segundo vetor gerado: 1, 2, 4, 5, 6, 9 29-Aug-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 52 Resumo da Aula 29-Aug-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 53 •Algoritmos de classificação: •quickSort(); •heapSort(); Material 29-Aug-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 54 • ASCENCIO, A. F. G.; Araújo, G. S. Estrutura de dados: algoritmos, análise da complexidade e implementação em Java e c/c++; Pearson, 2012. • Cap. 2 - Algoritmos de Ordenação • DEITEL, Harvey M.; DEITEL, Paul J. Java: como programar. 8.ed. Porto Alegre: Bookman, 2010. • Cap. 19 - Pesquisa, classificação e Big O. Na Próxima Aula 29-Aug-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 55 •Algoritmos de pesquisa •Pesquisa Sequêncial e Binária Prof. Me. Odair Moreira de Souza
Compartilhar