Algoritmo QuickSort para Classificação de Dados

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