Métodos de Ordenação Parte 3 - ?· Método Heapsort - Descrição do Algoritmo O processo de troca…

  • Published on
    26-Jan-2019

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>Estrutura de Dados II</p> <p>Mtodos de OrdenaoParte 3</p> <p>Profa Mrcio Bueno</p> <p>ed2tarde@marciobueno.com / ed2noite@marciobueno.com</p> <p>Material baseado nos materiais do Prof. Robson Lins</p> <p>Estrutura de Dados II - Mrcio Bueno 2</p> <p> Mtodos Eficientes (Sofisticados)Classificao por Troca</p> <p> Mtodo de Partio e Troca - Quicksort</p> <p>Classificao por Seleo</p> <p> Mtodo de Seleo em rvore - Heapsort</p> <p>Classificao em Memria Primria</p> <p>Estrutura de Dados II - Mrcio Bueno 3</p> <p>Classificao por Troca - Quicksort Proposto por Hoare e tem como base dois </p> <p>princpios:RecursividadeAbordagem dividir para conquistar</p> <p> Consiste em:Dado um conjunto C de elementos a ser ordenadoEscolher qualquer elemento k do conjunto C para </p> <p>dividir o conjunto em elementos pequenos e grandes. Este elemento chamado de piv.</p> <p>Dividir C em dois sub-conjuntos C1 e C2, onde os elementos de C1 so menores que o piv e os elementos de C2 so maiores que o piv.</p> <p>Repete-se o processo em C1 e C2</p> <p>Estrutura de Dados II - Mrcio Bueno 4</p> <p>Classificao por Troca - Quicksort Diagrama:</p> <p> Idealmente, o piv deveria ser selecionado de modo que aproximadamente metade dos elementos ficassem a esquerda do piv e a outra metade do lado direito do piv.</p> <p> Considere o caso onde o menor ou o maior elemento escolhido como piv. Nesse caso um conjunto (C1) ficaria vazio e o outro (C2) com n-1 elementos.</p> <p>p</p> <p>in[p]</p> <p>0 1 2 p-1</p> <p>&lt; in[p]</p> <p>N-2 N-1p+1</p> <p>&gt; in[p]</p> <p>Estrutura de Dados II - Mrcio Bueno 5</p> <p>Classificao por Troca - Quicksort Escolha do Piv Depende da implementaoUsar o primeiro elemento</p> <p> Aceitvel se a entrada aleatria</p> <p> Se a entrada for pr-ordenada ou estiver na ordem inversa uma pssima escolha</p> <p>Escolha aleatria Estratgia segura de um modo geral</p> <p> A gerao de nmeros aleatrios no implica em um desempenho melhor no restante do algoritmo</p> <p>Mdia das entradas Difcil de calcular</p> <p> Prejudicaria o desempenho</p> <p> Pegar 3 elementos e calcular a mdia</p> <p>Estrutura de Dados II - Mrcio Bueno 6</p> <p>Classificao por Troca - Quicksort Escolha do Piv </p> <p>Por questes de simplicidade, vamos escolher a chave que se encontra na posio inicial do vetor para ser a particionadora.</p> <p>Estrutura de Dados II - Mrcio Bueno 7</p> <p>Classificao por Troca - Quicksort</p> <p>elementos &lt; pivelementos &gt; piv</p> <p>esquerdapiv</p> <p>direitaiptr</p> <p>Elementos no examinadoselementos &lt; pivelementos &gt; piv</p> <p>esquerdapiv</p> <p>direitaiptr</p> <p>Elementos no examinados</p> <p>Estrutura de Dados II - Mrcio Bueno 8</p> <p>Classificao por Troca - Quicksortint particiona( int A[ ], int esquerda, int direita ){ int i, temp;int ptr = esquerda;int pivo = A[esquerda]; /* piv primeiro elemento */</p> <p>/* Separa o vetor em elementos pequenos e grandes em relao ao piv */</p> <p>for (i = esquerda+1; i</p> <p>Estrutura de Dados II - Mrcio Bueno 9</p> <p>Classificao por Troca - Quicksortvoid troca(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;</p> <p>}</p> <p>Estrutura de Dados II - Mrcio Bueno 10</p> <p>Classificao por Troca - Quicksort</p> <p>26 33 35 29 12 1922</p> <p>ptr i</p> <p>i=1</p> <p>26 33 35 29 12 1922</p> <p>ptr i</p> <p>i=2</p> <p>26 33 35 29 12 1922</p> <p>ptr i</p> <p>i=3</p> <p>26 12 35 29 33 1922</p> <p>ptr i</p> <p>i=4</p> <p>26 12 22 29 33 1935</p> <p>ptr i</p> <p>i=5</p> <p>26 12 22 19 33 2935</p> <p>ptr i</p> <p>i=6</p> <p>26 33 35 29 12 1922</p> <p>ptr</p> <p>Particiona( A,0,6 )</p> <p>19 12 22 26 33 2935</p> <p>return ptr</p> <p>26 33 35 29 12 1922</p> <p>ptr i</p> <p>i=1</p> <p>26 33 35 29 12 1922</p> <p>ptr i</p> <p>i=2</p> <p>26 33 35 29 12 1922</p> <p>ptr i</p> <p>i=3</p> <p>26 12 35 29 33 1922</p> <p>ptr i</p> <p>i=4</p> <p>26 12 22 29 33 1935</p> <p>ptr i</p> <p>i=5</p> <p>26 12 22 19 33 2935</p> <p>ptr i</p> <p>i=6</p> <p>26 33 35 29 12 1922</p> <p>ptr</p> <p>Particiona( A,0,6 )</p> <p>19 12 22 26 33 2935</p> <p>return ptr</p> <p>11</p> <p> Seleciona 26 como piv</p> <p> Mistura</p> <p> Piv no [3]</p> <p>26 33 35 29 12 1922</p> <p>0 1 2 3 4 65</p> <p>19 12 22 26 33 2935</p> <p> Seleciona 19 como piv Mistura Piv no [1]</p> <p>12</p> <p>0</p> <p>19</p> <p>1</p> <p>22</p> <p>2</p> <p>Fim</p> <p> Seleciona 33 como piv Mistura Piv no[5]</p> <p>29</p> <p>4</p> <p>33</p> <p>5</p> <p>35</p> <p>6</p> <p>QS(A,0,2) QS(A,4,6)</p> <p>Fim Fim</p> <p>QS(A,0,6)</p> <p>QS(A,2,2)QS(A,0,0) QS(A,4,4) QS(A,6,6)</p> <p>0 1 2 3 4 65</p> <p>Lista inicial A:</p> <p>FimEstrutura de Dados II - Mrcio Bueno</p> <p>Estrutura de Dados II - Mrcio Bueno 12</p> <p>Classificao por Troca - Quicksortvoid quickSort( int A[ ], int esquerda, int direita )</p> <p>{</p> <p>int pivo = particiona (A, esquerda, direita);</p> <p>if ( pivo &gt; esquerda)</p> <p>quickSort( A, esquerda, pivo - 1 );</p> <p>if ( pivo &lt; direita)</p> <p>quickSort( A, pivo + 1, direita );</p> <p>}</p> <p>Estrutura de Dados II - Mrcio Bueno 13</p> <p>Classificao por Troca - Quicksort Comparado com os demais mtodos o que apresenta, em </p> <p>mdia, o menor tempo de classificao. Tem um desempenho logartmico - O(n log2n) o que apresenta o menor nmero de operaes </p> <p>elementares. As razes porque quicksort mais eficiente que o problema de diviso executado no mesmo </p> <p>vetor e muito eficientementeNo precisa copiar o vetor ordenado</p> <p> Para vetores muito pequenos (N</p> <p>Estrutura de Dados II - Mrcio Bueno 14</p> <p>Classificao por Troca - QuickSort</p> <p> ExercciosMostre o passo a passo de executar quicksort </p> <p>para o seguinte conjunto de dados {9, 25, 10, 18, 5, 7, 15, 3}, usando o primeiro elemento como piv.</p> <p>Faa o mesmo para esse conjunto de dados {8, 5, 4, 7, 6, 1, 6, 3, 8, 12, 10}.</p> <p>Estrutura de Dados II - Mrcio Bueno 15</p> <p> O Mtodo da Seleo em rvore Heapsort Inventado por John Williams (1964) e usa a </p> <p>abordagem inerente ordenao por seleo.</p> <p> O mtodo utiliza a seleo em rvore para a obtenodos elementos do vetor na ordem desejada.</p> <p> Ele consiste em duas fases distintas:</p> <p>1) Primeiro montada uma rvore binria (heap)contendo todos os elementos do vetor, de talforma que o valor contido em qualquer n sejamaior do que os valores de seus filhos;</p> <p>2) Em seguida, o heap usado para a seleo doselementos na ordem desejada.</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 16</p> <p> Mtodo Heapsort - Descrio do Algoritmo</p> <p>Dado um vetor de chaves C1, C2, ..., CN,consideramos este vetor como sendo arepresentao de uma rvore binria, usandoa seguinte interpretao dos ndices daschaves:C1 a raiz da rvore;</p> <p>C2i = subrvore da esquerda de CiC2i+1 = subrvore da direita de Ci</p> <p>Para i = 1, ..., N div 2</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 17</p> <p> Mtodo Heapsort - Descrio do Algoritmo</p> <p>Exemplificando: dado um vetor V1..7, eutilizando a interpretao dada, podemosv-lo como sendo a representao daseguinte rvore binria:</p> <p>C1</p> <p>C2 C3</p> <p>C4 C5 C6 C7</p> <p>Para i = 1 at 7 div 2 = 1 .. 3</p> <p>i = 1 -&gt; Pai C1 e Filhos: C2 e C3</p> <p>i = 2 -&gt; Pai C2 e Filhos: C4 e C5</p> <p>i = 3 -&gt; Pai C3 e Filhos: C6 e C7</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 18</p> <p> Mtodo Heapsort - Descrio do AlgoritmoO passo seguinte consiste em trocar as chaves de</p> <p>posio dentro do vetor, de tal forma que estas passema formar uma hierarquia, na qual todas as razes dassubrvores sejam maiores ou iguais a qualquer uma dassuas sucessoras, ou seja, cada raiz deve satisfazer asseguintes condies:</p> <p> Ci C2i Ci C2i + 1 Para i = 1, ..., N div 2.</p> <p>Quando todas as razes das subrvores satisfazem essas condies, dizemos que a rvore forma um heap.</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 19</p> <p> Mtodo Heapsort - Descrio do Algoritmo</p> <p>O processo de troca de posies daschaves no vetor, de forma que a rvorerepresentada passe a ser um heap, podeser feito testando-se cada uma dassubrvores para verificar se elas,separadamente, satisfazem a condio deheap.</p> <p>Apenas as rvores que possuem pelo menosum sucessor devem ser testada.</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 20</p> <p> Mtodo Heapsort - Descrio do Algoritmo</p> <p>A maneira mais simples de realizar o teste iniciando pela ltima subrvore, ou seja,aquela cuja raiz est na posio N div 2 dovetor de chaves, prosseguindo, a partirda, para as subrvores que a antecedem,at chegar raiz da rvore.</p> <p>No exemplo, a primeira subrvore a sertestada aquela cuja raiz C3, depois a deraiz C2 e finalizando com a de raiz C1.</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 21</p> <p> Mtodo Heapsort - Descrio do AlgoritmoSempre que for encontrada uma subrvore que no</p> <p>forme um heap, seus componentes devem serrearranjados de modo a formar o heap.</p> <p>10</p> <p>05 12</p> <p>12</p> <p>05 10</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 22</p> <p> Mtodo Heapsort - Descrio do AlgoritmoPode ocorrer tambm que, ao rearranjarmos uma</p> <p>subrvore, isto venha a afetar outra, do nvelimediatamente inferior, fazendo que esta deixede formar um heap.</p> <p>Esta possibilidade obriga a verificar, sempre quefor rearranjada uma subrvore, se a sucessora donvel abaixo no teve a sua condio de heapdesfeita.</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 23</p> <p> Mtodo Heapsort - Exemplo</p> <p>Objetivo: Seleo da maior chave</p> <p>Vetor inicial: 12 09 13 25 18 10 22</p> <p>Representao em rvore:12</p> <p>09 13</p> <p>25 18 10 22</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 24</p> <p> Mtodo Heapsort - Exemplo</p> <p>A transformao dessa rvore em heap iniciapela subrvore cuja raiz 13, j que seundice, no vetor, 7 div 2 = 3.</p> <p>12</p> <p>09 13</p> <p>25 18 10 22</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 25</p> <p> Mtodo Heapsort - Exemplo</p> <p>Vetor e rvore resultantes: 12 09 22 25 18 10 13</p> <p>12</p> <p>09 22</p> <p>25 18 10 13</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 26</p> <p> Mtodo Heapsort - Exemplo</p> <p>Vetor e rvore resultantes: 12 25 22 09 18 10 13</p> <p>12</p> <p>25 22</p> <p>09 18 10 13</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 27</p> <p> Mtodo Heapsort - ExemploVetor e rvore resultantes: 25 12 22 09 18 10 13</p> <p>Neste caso ocorreu que a transformao dasubrvore afetou outra de um nvel mais abaixo. Asubrvore afetada deve ser rearranjada.</p> <p>25</p> <p>12 22</p> <p>09 18 10 13</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 28</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 25 18 22 09 12 10 13</p> <p> Se a chave que est na raiz a maior chave de todas, entosua posio definitiva correta na ordem crescente na ltimaposio do vetor, onde ela colocada, por troca com a chaveque ocupa aquela posio.</p> <p>25</p> <p>18 22</p> <p>09 12 10 13</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 29</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 13 18 22 09 12 10 | 25</p> <p>Com a maior chave j ocupando a sua posiodefinitiva podemos, a partir de agora, consideraro vetor como tendo um elemento a menos.</p> <p>13</p> <p>18 22</p> <p>09 12 10</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 30</p> <p> Mtodo Heapsort - Exemplo</p> <p>Seleo das chaves: 13 18 22 09 12 10 | 25</p> <p>Para selecionar a prxima chave, deve-se fazercom que a rvore volte a ser um heap.</p> <p>13</p> <p>18 22</p> <p>09 12 10</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 31</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 22 18 13 09 12 10 | 25</p> <p>Novamente a maior chave dentre as restantesaparece na raiz.</p> <p>22</p> <p>18 13</p> <p>09 12 10</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 32</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 22 18 13 09 12 10 | 25</p> <p>Vetor e rvore resultantes:10 18 13 09 12 | 22 25</p> <p>A seguir a rvore novamente rearranjada paraformar um heap, o que permitir selecionar aprxima chave.</p> <p>10</p> <p>18 13</p> <p>09 12</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 33</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 10 18 13 09 12 | 22 25</p> <p>Vetor intermedirio: 18 10 13 09 12 | 22 25</p> <p>Vetor resultante: 18 12 13 09 10 | 22 25</p> <p>18</p> <p>10 13</p> <p>09 12</p> <p>18</p> <p>12 13</p> <p>09 10</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 34</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 18 12 13 09 10 | 22 25</p> <p>Vetor intermedirio: 10 12 13 09 | 18 22 25</p> <p>Vetor resultante: 13 12 10 09 | 18 22 25</p> <p>10</p> <p>12 13</p> <p>09</p> <p>13</p> <p>12 10</p> <p>09</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 35</p> <p>Classificao por Seleo - Heapsort</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 13 12 10 09 | 18 22 25</p> <p>Vetor intermedirio: 09 12 10 | 13 18 22 25</p> <p>Vetor resultante: 12 09 10 | 13 18 22 25</p> <p>09</p> <p>12 10</p> <p>12</p> <p>09 10</p> <p>Estrutura de Dados II - Mrcio Bueno 36</p> <p> Mtodo Heapsort - ExemploSeleo das chaves: 10 09 | 12 13 18 22 25</p> <p>Vetor resultante: 09 | 10 12 13 18 22 25</p> <p>Vetor final: 09 10 12 13 18 22 25</p> <p>10</p> <p>0909</p> <p>Classificao por Seleo - Heapsort</p> <p>Estrutura de Dados II - Mrcio Bueno 37</p> <p>Classificao por Seleo - Heapsortvoid heapsort( int a[], int n){int i = n/2, pai, filho, t;for (;;) {if (i &gt; 0) {</p> <p>i--;t = a[i];</p> <p>}else{n--;if (n == 0)return;</p> <p>t = a[n];a[n] = a[0];</p> <p>}pai = i;filho = i*2 + 1;</p> <p>/* continua */}}</p> <p>Estrutura de Dados II - Mrcio Bueno 38</p> <p>Classificao por Seleo - Heapsortvoid heapsort( int a[], int n){</p> <p>/* Continuando ...*/while (filho &lt; n) {if ((filho + 1 &lt; n) &amp;&amp; (a[filho + 1] &gt; a[filho]))</p> <p>filho++;if (a[filho] &gt; t) {</p> <p>a[pai] = a[filho];pai = filho;filho = pai*2 + 1;</p> <p>} elsebreak;</p> <p>}a[pai] = t;</p> <p>}/* fim for*/}</p> <p>39</p> <p>Classificao por Seleo - Heapsort Tem um bom desempenho em tempo de execuo para </p> <p>conjuntos ordenados aleatoriamente. Tem um bom uso de memria e o seu desempenho no pior caso praticamente igual ao desempenho no caso mdio.</p> <p> Alguns algoritmos de ordenao rpidos tm desempenhos espetacularmente ruins no pior cenrio para tempo de execuo e uso da memria. </p> <p> O tempo de execuo no pior caso para ordenar nelementos de O (n log n). Para valores de n, razoavelmente grande, o tempo log n quase constante, de modo que o tempo de ordenao quase linear com o nmero de itens a ordenar.</p> <p> Caractersticas: Comparaes no pior caso: 2n log2n + O(n) Trocas no pior caso: n log2n + O(n) Melhor e pior caso: O(n log2n) </p> <p>Estrutura de Dados II - Mrcio Bueno</p> <p>Estrutura de Dados II - Mrcio Bueno 40</p> <p> Mtodo Heapsort Exerccio:</p> <p>Utilizando o heapsort ordene o seguinte conjunto de elementos {85,99,98,97,96,95,94,93,92,91,90, 89,87,86}.</p> <p>Classificao por Seleo - Heapsort</p>

Recommended

View more >