UPE – Caruaru – Sistemas de Informação Disciplina: Estrutura de Dados e Arquivo Prof.: Paulemir G. Campos Classificação de Dados 11/5/2015 EDA - Prof. Paulemir Campos 1 Conteúdo Classificação de Dados: Bubble-sort Quick-sort Heap-sort Merge-sort Aplicações 11/5/2015 EDA - Prof. Paulemir Campos 2 Classificação de Dados: Introdução Conjunto Ordenado: Elementos dispostos sob uma determinada ordem. Objetivos da Classificação: Facilitar a recuperação; Tornar mais eficiente o acesso aos dados. Tipos de Classificação: 11/5/2015 Interna: Todos os registros estão na memória principal; Externa: Alguns registros podem estar em dispositivos auxiliares de armazenamento. EDA - Prof. Paulemir Campos 3 Classificação de Dados: Introdução Veremos quatro algoritmos de classificação interna de dados: Classificação por Troca Classificação por Seleção Algoritmo Heap-sort Classificação por Intercalação 11/5/2015 Algoritmo Bubble-sort Algoritmo Quick-sort Algoritmo Merge-sort EDA - Prof. Paulemir Campos 4 Classificação por Troca Método Bubble-Sort 11/5/2015 A cada passo, cada elemento de um vetor C (vetor de chaves) é comparado com o seu sucessor, sendo os dois trocados de posição caso estejam fora de ordem; São executados passos sucessivos, até que não ocorram trocas, estando assim o vetor classificado. EDA - Prof. Paulemir Campos 5 Classificação por Troca Método Bubble-Sort (Algoritmo) BubbleSort(inteiro V[N], N){ /* FALSE -> 0 e TRUE -> 1 */ inteiro ordenado, j, temp ordenado = FALSE enquanto NÃO(ordenado) { ordenado = TRUE para j = 1 até (N-1) incremento 1 { se V[j] > V[j+1] { temp = V[j] V[j] = V[j+1] V[j+1] = temp ordenado = FALSE} } } } 11/5/2015 EDA - Prof. Paulemir Campos 6 Classificação por Troca Método Bubble-Sort (Exemplo) Seja o conjunto X={14,21,30,7,56,28,24,33,47,50,32}. Ordená-lo segundo o método Bubble-Sort. Etapa 14 21 30 7 56 28 24 33 47 50 32 1 14 21 7 30 28 24 33 47 50 32 56 2 14 7 21 28 24 30 33 47 32 50 56 3 7 14 21 24 28 30 33 32 47 50 56 4 7 14 21 24 28 30 32 33 47 50 56 5 7 14 21 24 28 30 32 33 47 50 56 11/5/2015 EDA - Prof. Paulemir Campos 7 Classificação por Troca Método Bubble-Sort (Observações) 11/5/2015 O seu princípio básico de funcionamento é conduzir os maiores elementos para o fim do vetor; É um algoritmo de ordenação bastante simples; Complexidade de Tempo: O(n2). EDA - Prof. Paulemir Campos 8 Classificação por Troca Método Quick-Sort Sejam X um conjunto com n elementos e p um elemento qualquer de X, denominado pivot. O método consiste em: 1) particionar x em dois subconjuntos X1 e X2 de modo que: • todo elemento de X1 seja menor ou igual a p • todo elemento de X2 seja maior que p Obs. p particiona o conjunto x de tal modo que todos os elementos de x1 são menores que qualquer elemento de x2 Exemplo. x={14,21,30,7,56,28,24,33,47,50,32} para p = 30 x1={14, 21, 7, 28, 24, 30} e x2={56, 33, 47, 50, 32} para p = 21 x1={14, 7, 21} e x2={30, 28, 24,56, 33, 47, 50, 32} 11/5/2015 EDA - Prof. Paulemir Campos 9 Classificação por Troca Método Quick-Sort 2) classificar x1 e x2 3) realizar a união de x1 e x2, nessa ordem Obs.: O passo 2 sugere que este método pode ser definido de modo recursivo. Na prática, os subconjuntos x1 e x2 podem permanecer fisicamente dentro de x. Assim, após a classificação recursiva desses, o conjunto x estará classificado. Neste caso a união dos subconjuntos não é necessária. 11/5/2015 EDA - Prof. Paulemir Campos 10 Classificação por Troca Método Quick-Sort (Algoritmo) QuickSort(inteiro x[N], min, max) início /* particionar o conjunto x da posição min até max sendo que */ /* o pivot ficará na posição j, min j max */ se (min max) então j = Particionar(x[N], min, max); QuickSort(x[N], min, j-1); QuickSort(x[N], j+1, max); fim-se fim 11/5/2015 EDA - Prof. Paulemir Campos 11 Classificação por Troca Método Quick-Sort (Função Particionar) inteiro Particionar(inteiro x[N], min, max) início inteiro pivot, down, up, temp; pivot = x[min]; down = min; up = max; enquanto (down < up) faça enquanto ((x[down] <= pivot) E (down<up)) faça down += 1; // sobe no vetor fim-enquanto enquanto (x[up] > pivot) faça up -=1; // desce no vetor fim-enquanto 11/5/2015 EDA - Prof. Paulemir Campos 12 Classificação por Troca Método Quick-Sort (Função Particionar) se (down < up) então // troca elementos do vetor x[N] temp = x[down]; x[down] = x[up]; x[up] = temp; fim-se fim-enquanto x[min]=x[up]; x[up]=pivot; j = up; retorne j; fim 11/5/2015 EDA - Prof. Paulemir Campos 13 Classificação por Troca Método Quick-Sort (Exemplo) Seja x={14,21,30,7,56,28,24,33,47,50,32}. Classificá-lo usando o método Quick-Sort. Pivot 14 21 30 7 56 28 24 33 47 50 32 30 14 21 7 28 24 30 56 33 47 50 32 21 e 47 14 7 21 28 24 30 33 32 47 56 50 7, 24, 32 e 50 7 14 21 24 28 30 32 33 47 50 56 14, 28 e 33 7 14 21 24 28 30 32 33 47 50 56 11/5/2015 EDA - Prof. Paulemir Campos 14 Classificação por Troca Método Quick-Sort (Observações) É o mais rápido e simples algoritmo de ordenação; Usa o princípio de divide-e-conquista; Complexidades de Tempo 11/5/2015 Caso Médio: O(n . log n); Pior Caso (muito raro): O(n2). EDA - Prof. Paulemir Campos 15 Classificação por Seleção Método Heap-Sort Utiliza a seleção em árvore binária para a obtenção dos elementos do vetor C na ordem desejada. Possui duas fases distintas: 11/5/2015 Construção da árvore binária heap com os elementos do vetor C; Usa-se este heap construído para a seleção dos elementos na ordem desejada. EDA - Prof. Paulemir Campos 16 Classificação por Seleção Método Heap-Sort Árvore Binária heap é um tipo de árvore binária em que todos os descendentes de cada nó são menores que seus nós ascendentes. 11/5/2015 EDA - Prof. Paulemir Campos 17 Classificação por Seleção Método Heap-Sort Exemplo de uma Árvore Binária Heap 1 2 17 11/5/2015 23 3 15 4 25 8 5 19 12 6 EDA - Prof. Paulemir Campos 7 18 Classificação por Seleção Método Heap-Sort (Exemplo) Dado o V={15,17,12,25,8,19,23} obter usando uma árvore binária tipo heap esses elementos em ordem crescente. 1. Obter a árvore binária heap equivalente ao vetor V. 1 2 1 17 12 3 25 4 15 8 5 11/5/2015 19 6 25 2 23 8 4 EDA - Prof. Paulemir Campos 23 3 17 7 15 5 19 12 7 6 19 Classificação por Seleção Método Heap-Sort (Exemplo) Dado o V={15,17,12,25,8,19,23} obter usando uma árvore binária tipo heap esses elementos em ordem crescente. 1. Obter a árvore binária heap equivalente ao vetor V. (Continuação) 1 2 1 15 23 3 17 4 25 8 5 11/5/2015 19 6 17 2 12 8 4 EDA - Prof. Paulemir Campos 23 3 15 7 25 5 19 12 7 6 20 Classificação por Seleção Método Heap-Sort (Exemplo) Dado o V={15,17,12,25,8,19,23} obter usando uma árvore binária tipo heap esses elementos em ordem crescente. 2. Ordenar em ordem crescente o vetor V usando a árvore binária heap obtida no passo 1 1 2 1 17 23 3 15 4 25 8 5 11/5/2015 19 6 17 2 12 8 4 EDA - Prof. Paulemir Campos 19 3 15 7 23 5 12 25 7 6 21 Classificação por Seleção Método Heap-Sort (Exemplo) Dado o V={15,17,12,25,8,19,23} obter usando uma árvore binária tipo heap esses elementos em ordem crescente. 2. Ordenar em ordem crescente o vetor V usando a árvore binária heap obtida no passo 1 (continuação do passo 2) 1 2 1 17 12 3 15 4 19 8 5 11/5/2015 23 6 15 2 25 19 4 EDA - Prof. Paulemir Campos 12 3 8 7 17 5 23 25 7 6 22 Classificação por Seleção Método Heap-Sort (Exemplo) Dado o V={15,17,12,25,8,19,23} obter usando uma árvore binária tipo heap esses elementos em ordem crescente. 2. Ordenar em ordem crescente o vetor V usando a árvore binária heap obtida no passo 1 (continuação do passo 2) 1 2 1 8 12 3 17 4 15 19 5 11/5/2015 23 6 8 2 25 19 4 EDA - Prof. Paulemir Campos 15 3 17 7 12 5 23 25 7 6 23 Classificação por Seleção Método Heap-Sort (Exemplo) Dado o V={15,17,12,25,8,19,23} obter usando uma árvore binária tipo heap esses elementos em ordem crescente. 2. Ordenar em ordem crescente o vetor V usando a árvore binária heap obtida no passo 1 (continuação do passo 2) 1 8 12 2 3 17 19 4 5 11/5/2015 V = {8, 12, 15, 17, 19, 23, 25} 15 23 25 6 7 EDA - Prof. Paulemir Campos 24 Classificação por Seleção Método Heap-Sort (Observações) 11/5/2015 É um algoritmo ótimo; Complexidade de Tempo: O(n . log n); Não requer espaço extra de memória; Na prática é um pouco mais lento do que o Quick-Sort. EDA - Prof. Paulemir Campos 25 Classificação por Intercalação Método Merge-Sort O princípio de funcionamento deste algoritmo é o seguinte: - dividir o vetor original em n sub-partes de tamanho 1; - intercalar os pares de sub-partes adjacentes, da esquerda para a direita em ordem crescente; - repetir o passo anterior até obter um único vetor de tamanho n, que evidentemente estará ordenado. 11/5/2015 EDA - Prof. Paulemir Campos 26 Classificação por Intercalação 11/5/2015 Método Merge-Sort (Exemplo) EDA - Prof. Paulemir Campos 27 Classificação por Intercalação Método Merge-Sort (Observações) Usa o princípio de divide-e-conquista; É um algoritmo ótimo; Complexidades de Tempo: O(n . log n); Desvantagem 11/5/2015 Requer espaço extra de memória do tamanho do vetor original para uso temporário. Na prática é um pouco mais lento do que o Quick-Sort. EDA - Prof. Paulemir Campos 28 Classificação de Dados: Aplicações Os métodos de classificação interna vistos nesta aula podem ser aplicados para se obter uma ordenação de um vetor de chave de uma determinada tabela, desde de que essas chaves sejam números inteiros. 11/5/2015 EDA - Prof. Paulemir Campos 29 Referências Veloso, P. et al. Estrutura de Dados. Rio de Janeiro: Editora Campus, 1996. 11/5/2015 EDA - Prof. Paulemir Campos 30 Links Interessantes Bubble-Sort: Quick-Sort: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm Heap-Sort: http://www.iti.fhflensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm#section3 http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm Merge-Sort: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm 11/5/2015 EDA - Prof. Paulemir Campos 31