Ordenação ??Cap.4Ordenação 1 Ordenação Introdução - Conceitos Básicos Ordenação Interna –…

  • Published on
    16-Dec-2018

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>Ordenao</p> <p>ltima alterao: 26 de Maro de 2004</p> <p>Transparncias elaboradas por Fabiano C. Botelho e Nivio Ziviani</p> <p>Projeto de Algoritmos Cap.4 Ordenao 1</p> <p>Ordenao</p> <p> Introduo - Conceitos Bsicos</p> <p> Ordenao Interna</p> <p> Ordenao por Seleo</p> <p> Ordenao por Insero</p> <p> Shellsort</p> <p> Quicksort</p> <p> Heapsort</p> <p> Ordenao Parcial</p> <p> Seleo Parcial Insero Parcial Heapsort Parcial Quicksort Parcial</p> <p> Ordenao Externa</p> <p> Intercalao Balanceada de VriosCaminhos</p> <p> Implementao por meio de Seleo porSubstituio</p> <p> Consideraes Prticas</p> <p> Intercalao Polifsica</p> <p> Quicksort Externo</p> <p>Projeto de Algoritmos Cap.4 Ordenao 2</p> <p>Introduo - Conceitos Bsicos</p> <p> Ordenar: processo de rearranjar um conjuntode objetos em uma ordem ascendente oudescendente.</p> <p> A ordenao visa facilitar a recuperaoposterior de itens do conjunto ordenado.</p> <p> Dificuldade de se utilizar um catlogotelefnico se os nomes das pessoas noestivessem listados em ordem alfabtica.</p> <p> Notao utilizada nos algoritmos:</p> <p> Os algoritmos trabalham sobre osregistros de um arquivo.</p> <p> Cada registro possui uma chave utilizadapara controlar a ordenao.</p> <p> Podem existir outros componentes em umregistro.</p> <p>Projeto de Algoritmos Cap.4 Ordenao 3</p> <p>Introduo - Conceitos Bsicos</p> <p> Estrutura de um registro:</p> <p>type Item = record</p> <p>Chave: ChaveTipo;</p> <p>{ outros componentes }</p> <p>end;</p> <p> Qualquer tipo de chave sobre o qual existauma regra de ordenao bem-definida podeser utilizado.</p> <p> Um mtodo de ordenao estvel se aordem relativa dos itens com chaves iguaisno se altera durante a ordenao.</p> <p> Alguns dos mtodos de ordenao maiseficientes no so estveis.</p> <p> A estabilidade pode ser forada quando omtodo no-estvel.</p> <p> Sedgewick (1988) sugere agregar umpequeno ndice a cada chave antes deordenar, ou ento aumentar a chave dealguma outra forma.</p> <p>Projeto de Algoritmos Cap.4 Ordenao 4</p> <p>Introduo - Conceitos Bsicos</p> <p> Classificao dos mtodos de ordenao:</p> <p> Ordenao interna: arquivo a serordenado cabe todo na memria principal.</p> <p> Ordenao externa: arquivo a serordenado no cabe na memria principal.</p> <p> Diferenas entre os mtodos:</p> <p> Em um mtodo de ordenao interna,qualquer registro pode ser imediatamenteacessado.</p> <p> Em um mtodo de ordenao externa, osregistros so acessados seqencialmenteou em grandes blocos.</p> <p> A maioria dos mtodos de ordenao baseada em comparaes das chaves.</p> <p> Existem mtodos de ordenao que utilizamo princpio da distribuio.</p> <p>Projeto de Algoritmos Cap.4 Ordenao 5</p> <p>Introduo - Conceitos Bsicos</p> <p> Exemplo de ordenaGCo por distribuio:considere o problema de ordenar um baralhocom 52 cartas na ordem:</p> <p>A &lt; 2 &lt; 3 &lt; &lt; 10 &lt; J &lt; Q &lt; K</p> <p>e</p> <p> &lt; &lt; &lt; .</p> <p> Algoritmo:</p> <p>1. Distribuir as cartas abertas em trezemontes: ases, dois, trs, . . ., reis.</p> <p>2. Colete os montes na ordem especificada.</p> <p>3. Distribua novamente as cartas abertas emquatro montes: paus, ouros, copas eespadas.</p> <p>4. Colete os montes na ordem especificada.</p> <p>Projeto de Algoritmos Cap.4 Ordenao 6</p> <p>Introduo - Conceitos Bsicos</p> <p> Mtodos como o ilustrado so tambmconhecidos como ordenao digital,radixsort ou bucketsort.</p> <p> O mtodo no utiliza comparao entrechaves.</p> <p> Uma das dificuldades de implementar estemtodo est relacionada com o problema delidar com cada monte.</p> <p> Se para cada monte ns reservarmos umarea, ento a demanda por memria extrapode tornar-se proibitiva.</p> <p> O custo para ordenar um arquivo com nelementos da ordem de O(n).</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1 7</p> <p>Ordenao Interna</p> <p> Na escolha de um algoritmo de ordenaointerna deve ser considerado o tempo gastopela ordenao.</p> <p> Sendo n o nmero registros no arquivo, asmedidas de complexidade relevantes sCo:</p> <p> Nmero de comparaes C(n) entrechaves.</p> <p> Nmero de movimentaes M(n) de itensdo arquivo.</p> <p> O uso econmico da memria disponvel um requisito primordial na ordenao interna.</p> <p> Mtodos de ordenao in situ so ospreferidos.</p> <p> Mtodos que utilizam listas encadeadas noso muito utilizados.</p> <p> Mtodos que fazem cpias dos itens a seremordenados possuem menor importncia.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1 8</p> <p>Ordenao Interna</p> <p> Classificao dos mtodos de ordenaointerna:</p> <p> Mtodos simples:</p> <p> Adequados para pequenos arquivos. Requerem O(n2) comparaes. Produzem programas pequenos.</p> <p> Mtodos eficientes:</p> <p> Adequados para arquivos maiores. Requerem O(n log n) comparaes. Usam menos comparaes. As comparaes so mais complexas</p> <p>nos detalhes. Mtodos simples so mais eficientes</p> <p>para pequenos arquivos.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1 9</p> <p>Ordenao Interna</p> <p> Tipos de dados e variveis utilizados nosalgoritmos de ordenao interna:</p> <p>type Indice = 0..MaxTam;</p> <p>Vetor = array [ Indice ] of Item;</p> <p>var A: Vetor ;</p> <p> O ndice do vetor vai de 0 at MaxTam,devido s chaves sentinelas.</p> <p> O vetor a ser ordenado contm chaves nasposies de 1 at n.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.1 10</p> <p>Ordenao por Seleo</p> <p> Um dos algoritmos mais simples deordenao.</p> <p> Algoritmo:</p> <p> Selecione o menor item do vetor.</p> <p> Troque-o com o item da primeira posiodo vetor.</p> <p> Repita essas duas operaes com osn 1 itens restantes, depois com os n 2itens, at que reste apenas um elemento.</p> <p> O mtodo ilustrado abaixo:</p> <p>1 2 3 4 5 6</p> <p>Chaves iniciais: O R D E N A</p> <p>i = 1 A R D E N O</p> <p>i = 2 A D R E N O</p> <p>i = 3 A D E R N O</p> <p>i = 4 A D E N R O</p> <p>i = 5 A D E N O R</p> <p> As chaves em negrito sofreram uma trocaentre si.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.1 11</p> <p>Ordenao por Seleo</p> <p>procedure Selecao (var A: Vetor ; var n: Indice ) ;</p> <p>var i , j , Min: Indice ;</p> <p>x : Item;</p> <p>begin</p> <p>for i := 1 to n 1 do</p> <p>begin</p> <p>Min := i ;</p> <p>for j := i + 1 to n do</p> <p>i f A[ j ] .Chave &lt; A[Min] .Chave</p> <p>then Min := j ;</p> <p>x := A[Min ] ; A[Min] := A[ i ] ; A[ i ] := x;</p> <p>end;</p> <p>end;</p> <p>Anlise</p> <p> Comparaes entre chaves e movimentaesde registros:</p> <p>C(n) = n2</p> <p>2 n</p> <p>2</p> <p>M(n) = 3(n 1)</p> <p> A atribuio Min := j executada em mdian log n vezes, Knuth (1973).</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.1 12</p> <p>Ordenao por Seleo</p> <p>Vantagens:</p> <p> Custo linar no tamanho da entrada para onmero de movimentos de registros.</p> <p> o algoritmo a ser utilizado para arquivoscom registros muito grandes.</p> <p> muito interessante para arquivos pequenos.</p> <p>Desvantagens:</p> <p> O fato de o arquivo j estar ordenado noajuda em nada, pois o custo continuaquadrtico.</p> <p> O algoritmo no estvel.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.2 13</p> <p>Ordenao por Insero</p> <p> Mtodo preferido dos jogadores de cartas.</p> <p> Algoritmo:</p> <p> Em cada passo a partir de i=2 faa:</p> <p> Selecione o i-simo item da seqnciafonte.</p> <p> Coloque-o no lugar apropriado naseqncia destino de acordo com ocritrio de ordenao.</p> <p> O mtodo ilustrado abaixo:</p> <p>1 2 3 4 5 6</p> <p>Chaves iniciais: O R D E N A</p> <p>i = 2 O R D E N A</p> <p>i = 3 D O R E N A</p> <p>i = 4 D E O R N A</p> <p>i = 5 D E N O R A</p> <p>i = 6 A D E N O R</p> <p> As chaves em negrito representam aseqncia destino.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.2 14</p> <p>Ordenao por Insero</p> <p>procedure Insercao (var A: Vetor ; var n: Indice ) ;</p> <p>var i , j : Indice ;</p> <p>x : Item;</p> <p>begin</p> <p>for i := 2 to n do</p> <p>begin</p> <p>x := A[ i ] ;</p> <p>j := i 1;</p> <p>A[0] := x ; { sentinela }</p> <p>while x.Chave &lt; A[ j ] .Chave do</p> <p>begin</p> <p>A[ j + 1] := A[ j ] ;</p> <p>j := j 1;</p> <p>end;</p> <p>A[ j + 1] := x;</p> <p>end;</p> <p>end;</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.2 15</p> <p>Ordenao por Insero</p> <p>Consideraes sobre o algoritmo:</p> <p> O processo de ordenao pode ser terminadopelas condies:</p> <p> Um item com chave menor que o item emconsiderao encontrado.</p> <p> O final da seqncia destino atingido esquerda.</p> <p> Soluo:</p> <p> Utilizar um registro sentinela na posiozero do vetor.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.2 16</p> <p>Ordenao por Insero</p> <p>Anlise</p> <p> Seja C(n) a funo que conta o nmero decomparaes.</p> <p> No anel mais interno, na i-sima iterao, ovalor de Ci :</p> <p>melhor caso : Ci(n) = 1</p> <p>pior caso : Ci(n) = i</p> <p>caso medio : Ci(n) =1i(1 + 2 + + i) = i+1</p> <p>2</p> <p> Assumindo que todas as permutaes de nso igualmente provveis no caso mdio,temos:</p> <p>melhor caso : C(n) = (1 + 1 + + 1) = n 1</p> <p>pior caso : C(n) = (2 + 3 + + n) = n2</p> <p>2+</p> <p>n2 1</p> <p>caso medio : C(n) = 12(3 + 4 + + n + 1) =</p> <p>n2</p> <p>4+ 3n</p> <p>4 1</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.2 17</p> <p>Ordenao por Insero</p> <p>Anlise</p> <p> Seja M(n) a funo que conta o nmero demovimentaes de registros.</p> <p> O nmero de movimentaes na i-simaiterao :</p> <p>Mi(n) = Ci(n) 1 + 3 = Ci(n) + 2</p> <p> Logo, o nmero de movimentos :</p> <p>melhor caso : M(n) = (3 + 3 + + 3) =</p> <p>3(n 1)</p> <p>pior caso : M(n) = (4 + 5 + + n + 2) =</p> <p>n2</p> <p>2+ 5n</p> <p>2 3</p> <p>caso medio : M(n) = 12(5 + 6 + + n + 3) =</p> <p>n2</p> <p>4+ 11n</p> <p>4 3</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.2 18</p> <p>Ordenao por Insero</p> <p> O nmero mnimo de comparaes emovimentos ocorre quando os itens estooriginalmente em ordem.</p> <p> O nmero mximo ocorre quando os itensesto originalmente na ordem reversa.</p> <p> o mtodo a ser utilizado quando o arquivoest quase ordenado.</p> <p> um bom mtodo quando se desejaadicionar uns poucos itens a um arquivoordenado, pois o custo linear.</p> <p> O algoritmo de ordenao por insero estvel.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 19</p> <p>Shellsort</p> <p> Proposto por Shell em 1959.</p> <p> uma extenso do algoritmo de ordenaopor insero.</p> <p> Problema com o algoritmo de ordenao porinsero:</p> <p> Troca itens adjacentes para determinar oponto de insero.</p> <p> So efetuadas n 1 comparaes emovimentaes quando o menor item estna posio mais direita no vetor.</p> <p> O mtodo de Shell contorna este problemapermitindo trocas de registros distantes umdo outro.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 20</p> <p>Shellsort</p> <p> Os itens separados de h posies sorearranjados.</p> <p> Todo h-simo item leva a uma seqnciaordenada.</p> <p> Tal seqncia dita estar h-ordenada.</p> <p> Exemplo de utilizao:</p> <p>1 2 3 4 5 6</p> <p>Chaves iniciais: O R D E N A</p> <p>h = 4 N A D E O R</p> <p>h = 2 D A N E O R</p> <p>h = 1 A D E N O R</p> <p> Quando h = 1 Shellsort corresponde aoalgoritmo de insero.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 21</p> <p>Shellsort</p> <p> Como escolher o valor de h:</p> <p> Seqncia para h:</p> <p>h(s) = 3h(s 1) + 1, para s &gt; 1</p> <p>h(s) = 1, para s = 1.</p> <p> Knuth (1973, p. 95) mostrouexperimentalmente que esta seqncia difcil de ser batida por mais de 20% emeficincia.</p> <p> A seqncia para h corresponde a 1, 4,13, 40, 121, 364, 1.093, 3.280, . . .</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 22</p> <p>Shellsort</p> <p>procedure Shellsort (var A: Vetor ; var n: Indice ) ;</p> <p>label 999;</p> <p>var i , j , h : integer ;</p> <p>x : Item;</p> <p>begin</p> <p>h := 1;</p> <p>repeat h := 3 h + 1 until h &gt;= n;</p> <p>repeat</p> <p>h := h div 3;</p> <p>for i := h + 1 to n do</p> <p>begin</p> <p>x := A[ i ] ;</p> <p>j := i ;</p> <p>while A[ j h] .Chave &gt; x.Chave do</p> <p>begin</p> <p>A[ j ] := A[ j h] ;</p> <p>j := j h;</p> <p>i f j </p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 23</p> <p>Shellsort</p> <p> A implementao do Shellsort no utilizaregistros sentinelas.</p> <p> Seriam necessrios h registros sentinelas,uma para cada h-ordenao.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 24</p> <p>Shellsort</p> <p>Anlise</p> <p> A razo da eficincia do algoritmo ainda no conhecida.</p> <p> Ningum ainda foi capaz de analisar oalgoritmo.</p> <p> A sua anlise contm alguns problemasmatemticos muito difceis.</p> <p> A comear pela prpria seqncia deincrementos.</p> <p> O que se sabe que cada incremento nodeve ser mltiplo do anterior.</p> <p> Conjecturas referente ao nmero decomparaes para a seqncia de Knuth:</p> <p>Conjetura 1 : C(n) = O(n1,25)</p> <p>Conjetura 2 : C(n) = O(n(ln n)2)</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.3 25</p> <p>Shellsort</p> <p> Vantagens:</p> <p> Shellsort uma tima opo para arquivosde tamanho moderado.</p> <p> Sua implementao simples e requeruma quantidade de cdigo pequena.</p> <p> Desvantagens:</p> <p> O tempo de execuo do algoritmo sensvel ordem inicial do arquivo.</p> <p> O mtodo no estvel,</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 26</p> <p>Quicksort</p> <p> Proposto por Hoare em 1960 e publiccado em1962.</p> <p> o algoritmo de ordenao interna maisrpido que se conhece para uma amplavariedade de situaes.</p> <p> Provavelmente o mais utilizado.</p> <p> A idia bsica dividir o problema de ordenarum conjunto com n itens em dois problemasmenores.</p> <p> Os problemas menores so ordenadosindependentemente.</p> <p> Os resultados so combinados para produzira soluo final.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 27</p> <p>Quicksort</p> <p> A parte mais delicada do mtodo oprocesso de partio.</p> <p> O vetor A[Esq..Dir] rearranjado por meio daescolha arbitrria de um piv x.</p> <p> O vetor A particionado em duas partes:</p> <p> A parte esquerda com chaves menores ouiguais a x.</p> <p> A parte direita com chaves maiores ouiguais a x.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 28</p> <p>Quicksort</p> <p> Algoritmo para o particionamento:</p> <p>1. Escolha arbitrariamente um piv x.</p> <p>2. Percorra o vetor a partir da esquerda atque A[i] x.</p> <p>3. Percorra o vetor a partir da direita at queA[j] x.</p> <p>4. Troque A[i] com A[j].</p> <p>5. Continue este processo at osapontadores i e j se cruzarem.</p> <p> Ao final, o vetor A[Esq..Dir] est particionadode tal forma que:</p> <p> Os itens em A[Esq], A[Esq + 1], . . . , A[j]so menores ou iguais a x.</p> <p> Os itens em A[i], A[i + 1], . . . , A[Dir] somaiores ou iguais a x.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 29</p> <p>Quicksort</p> <p> Ilustrao do processo de partio:</p> <p>1 2 3 4 5 6</p> <p>O R D E N A</p> <p>A R D E N O</p> <p>A D R E N O</p> <p> O piv x escolhido como sendoA[(i + j) div 2].</p> <p> Como inicialmente i = 1 e j = 6, entox = A[3] = D.</p> <p> Ao final do processo de partio i e j secruzam em i = 3 e j = 2.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 30</p> <p>Quicksort</p> <p>Procedimento Particao:</p> <p>procedure Particao (Esq, Dir : Indice ;var i , j : Indice ) ;</p> <p>var x , w: Item;</p> <p>begin</p> <p>i := Esq; j := Dir ;</p> <p>x := A[ ( i + j ) div 2 ] ; { obtem o pivo x }</p> <p>repeat</p> <p>while x.Chave &gt; A[ i ] .Chave do i := i + 1;</p> <p>while x.Chave &lt; A[ j ] .Chave do j := j 1;</p> <p>i f i j ;</p> <p>end;</p> <p> O anel interno do procedimento Particao extremamente simples.</p> <p> Razo pela qual o algoritmo Quicksort torpido.</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 31</p> <p>Quicksort</p> <p>Procedimento Quicksort:</p> <p>procedure QuickSort (var A: Vetor ; var n: Indice ) ;</p> <p>{Entra aqui o procedimento Particao}</p> <p>procedure Ordena (Esq, Dir : Indice ) ;</p> <p>var i , j : Indice ;</p> <p>begin</p> <p>particao (Esq, Dir , i , j ) ;</p> <p>i f Esq &lt; j then Ordena (Esq, j ) ;</p> <p>i f i &lt; Dir then Ordena ( i , Dir ) ;</p> <p>end;</p> <p>begin</p> <p>Ordena (1 , n) ;</p> <p>end;</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 32</p> <p>Quicksort</p> <p> Exemplo do estado do vetor em cadachamada recursiva do procedimento Ordena:</p> <p>Chaves iniciais: O R D E N A</p> <p>1 A D R E N O</p> <p>2 A D</p> <p>3 E R N O</p> <p>4 N R O</p> <p>5 O R</p> <p>A D E N O R</p> <p>Projeto de Algoritmos Cap.4 Ordenao Seo 4.1.4 33</p> <p>Quicksort</p> <p>Anlise</p> <p> Seja C(n) a funo que conta o nmero decomparaes.</p> <p> Pior caso:</p> <p>C(n) = O(n2)</p> <p> O pior caso ocorre quando, sistematicamente,o piv escolh...</p>

Recommended

View more >