AED ordenação

  • Published on
    22-Oct-2015

  • View
    32

  • Download
    1

Embed Size (px)

Transcript

<ul><li><p>OrdenaoOrdenao</p><p>Livro Projeto de Algoritmos Nvio ZivianiCaptulo 4http://www2.dcc.ufmg.br/livros/algoritmos/</p></li><li><p>Ordenao</p><p> Introduo Conceitos Bsicos Introduo Conceitos Bsicos Ordenao Interna</p><p> Ordenao por Seleo p Ordenao por Insero ShellSort QuickSort HeapSort MergeSort MergeSort Ordenao Digital Ordenao Parcial</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao</p><p> Ordenao Externa Intercalao Balanceada de Vrios Caminhos Implementao por meio de Seleo por Substituio Consideraes Prticas Intercalao Polifsica</p><p>Q i k t E t Quicksort Externo</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente oude objetos em uma ordem ascendente ou descendente.</p><p> A ordenao visa facilitar a recuperao A ordenao visa facilitar a recuperao posterior de itens do conjunto ordenado. Dificuldade de se utilizar um catlogo telefnico Dificuldade de se utilizar um catlogo telefnico </p><p>se os nomes das pessoas no estivessem listados em ordem alfabtica.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Notao utilizada nos algoritmos:O l it t b lh b i t d Os algoritmos trabalham sobre os registros de um arquivo.</p><p> Cada registro possui uma chave utilizada para Cada registro possui uma chave utilizada para controlar a ordenao.</p><p> Podem existir outros componentes em um registro.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Estrutura de um registro:typedef int ChaveTipo;typedef struct Item {</p><p>Ch Ti ChChaveTipo Chave;/* outros componentes */</p><p>} Item;} Item;</p><p> Qualquer tipo de chave sobre o qual exista Qualquer tipo de chave sobre o qual exista uma regra de ordenao bem-definida pode ser utilizado.ser utilizado.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Um mtodo de ordenao estvel se a ordem relativa dos itens com chaves iguaisordem relativa dos itens com chaves iguais no se altera durante a ordenao. </p><p> Alguns dos mtodos de ordenao mais Alguns dos mtodos de ordenao mais eficientes no so estveis.</p><p> A estabilidade pode ser forada quando o A estabilidade pode ser forada quando o mtodo no-estvel.</p><p> Sedgewick (1988) sugere agregar um Sedgewick (1988) sugere agregar um pequeno ndice a cada chave antes de ordenar, ou ento aumentar a chave de alguma outra forma.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Classificao dos mtodos de ordenao:O d i t i d d b Ordenao interna: arquivo a ser ordenado cabe todo na memria principal.</p><p> Ordenao externa: arquivo a ser ordenado no Ordenao externa: arquivo a ser ordenado no cabe na memria principal.</p><p> Diferenas entre os mtodos: Em um mtodo de ordenao interna, qualquer </p><p>registro pode ser imediatamente acessadoregistro pode ser imediatamente acessado. Em um mtodo de ordenao externa, os </p><p>registros so acessados seqencialmente ou emregistros so acessados seqencialmente ou em grandes blocos.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p>A i i d t d d d A maioria dos mtodos de ordenao baseada em comparaes das chaves.</p><p> Existem mtodos de ordenao que utilizam o princpio da distribuioo princpio da distribuio.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Exemplo de ordenao por distribuio: considere o problema de ordenar um baralhoconsidere o problema de ordenar um baralho com 52 cartas na ordem:</p><p>A &lt; 2 &lt; 3 &lt; ... &lt; 10 &lt; J &lt; Q &lt; Kee</p><p> &lt; &lt; &lt; </p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Algoritmo:1 Di t ib i t b t t t1. Distribuir as cartas abertas em treze montes: </p><p>ases, dois, trs, : : :, reis.2 Colete os montes na ordem especificada2. Colete os montes na ordem especificada.3. Distribua novamente as cartas abertas em quatro </p><p>montes: paus, ouros, copas e espadas.4. Colete os montes na ordem especificada.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Introduo Conceitos Bsicos</p><p> Mtodos como o ilustrado so tambm conhecidos como ordenao digital radixsortconhecidos como ordenao digital, radixsort ou bucketsort.</p><p> O mtodo no utiliza comparao entre chaves.O mtodo no utiliza comparao entre chaves. Uma das dificuldades de implementar este </p><p>mtodo est relacionada com o problema de lidar com cada monte.</p><p> Se para cada monte ns reservarmos uma rea, t d d i t dento a demanda por memria extra pode </p><p>tornar-se proibitiva.O custo para ordenar um arquivo com n O custo para ordenar um arquivo com n elementos da ordem de O(n).</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao Interna</p><p> Na escolha de um algoritmo de ordenao interna deve ser considerado o tempo gastointerna deve ser considerado o tempo gasto pela ordenao.</p><p> Sendo n o nmero registros no arquivo, as g qmedidas de complexidade relevantes so: Nmero de comparaes C(n) entre chaves.</p><p>N d i t M( ) d it d Nmero de movimentaes M(n) de itens do arquivo.</p><p> O uso econmico da memria disponvel pum requisito primordial na ordenao interna.</p><p> Mtodos de ordenao in situ so osf idpreferidos.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao Interna</p><p>Mt d tili li t d d Mtodos que utilizam listas encadeadas no so muito utilizados.</p><p> Mtodos que fazem cpias dos itens a serem ordenados possuem menorserem ordenados possuem menor importncia.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao Interna</p><p> Classificao dos mtodos de ordenao interna:interna: Mtodos simples: Adequados para pequenos arquivos Adequados para pequenos arquivos. Requerem O(n2) comparaes. Produzem programas pequenos.</p><p> Mtodos eficientes: Adequados para arquivos maiores. Requerem O(n log n) comparaes Requerem O(n log n) comparaes. Usam menos comparaes. As comparaes so mais complexas nos detalhes. Mtodos simples so mais eficientes para pequenos </p><p>arquivos.Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao Interna</p><p> Tipos de dados e variveis utilizados nos algoritmos de ordenao interna:algoritmos de ordenao interna:</p><p>typedef int Indice;typedef Item Vetor[MaxTam + 1];typedef Item Vetor[MaxTam + 1];Vetor A;</p><p> O ndice do vetor vai de 0 at MaxTam, devido s chaves sentinelas.devido s chaves sentinelas.</p><p> O vetor a ser ordenado contm chaves nas posies de 1 at n.p </p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Seleo</p><p> Um dos algoritmos mais simples de ordenaoordenao.</p><p>Al it Algoritmo: Selecione o menor item do vetor.</p><p>Troque o com o item da primeira posio do vetor Troque-o com o item da primeira posio do vetor. Repita essas duas operaes com os n - 1 itens </p><p>restantes, depois com os n - 2 itens, at que resterestantes, depois com os n 2 itens, at que reste apenas um elemento.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Seleo</p><p> O mtodo ilustrado abaixo:</p><p>As chaves em negrito sofreram uma troca As chaves em negrito sofreram uma troca entre si.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Seleo</p><p>void Selecao (Item *A, Indice *n){ Indice i, j, Min;{ Indice i, j, Min;</p><p>Item x;for (i = 1; i </p></li><li><p>Ordenao por Seleo</p><p> AnliseC t h i t d Comparaes entre chaves e movimentaes de registros:</p><p>C(n) = n2/2 n/2C(n) = n /2 n/2M(n) = 3(n - 1)</p><p> A atribuio Min = j executada em mdia n log nvezes, Knuth (1973).vezes, Knuth (1973).</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Seleo</p><p> Vantagens:C t li t h d t d Custo linear no tamanho da entrada para o nmero de movimentos de registros.</p><p> o algoritmo a ser utilizado para arquivos com o algoritmo a ser utilizado para arquivos com registros muito grandes.</p><p> muito interessante para arquivos pequenos. Desvantagens: O fato de o arquivo j estar ordenado no ajuda </p><p>em nada, pois o custo continua quadrtico. O algoritmo no estvel.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p>Mt d f id d j d d t Mtodo preferido dos jogadores de cartas.</p><p> Algoritmo: Em cada passo a partir de i=2 faa: Selecione o i-simo item da seqncia fonte. Coloque-o no lugar apropriado na seqncia destino de </p><p>acordo com o critrio de ordenao.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p> O mtodo ilustrado abaixo:</p><p> As chaves em negrito representam a As chaves em negrito representam a seqncia destino.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p>void Insercao(Item *A, Indice *n){ Indice i j;{ Indice i, j;Item x;for (i = 2; i </p></li><li><p>Ordenao por Insero</p><p> Consideraes sobre o algoritmo:</p><p> O processo de ordenao pode ser terminado pelas condies:pelas condies: Um item com chave menor que o item em considerao </p><p> encontrado.O fi l d i d ti ti id d O final da seqncia destino atingido esquerda.</p><p>Soluo: Soluo: Utilizar um registro sentinela na posio zero do vetor.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p> Anlise</p><p> Seja C(n) a funo que conta o nmero de comparaescomparaes.</p><p> No anel mais interno na i-sima iterao o valor No anel mais interno, na i sima iterao, o valor de Ci :</p><p> melhor caso : Ci (n) = 1 pior caso : Ci (n) = i caso medio : Ci(n) = 1/i (1 + 2 + ... + i) = (i+1)/2( ) ( ) ( )</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p> Assumindo que todas as permutaes de n so igualmente provveis no caso mdioso igualmente provveis no caso mdio, temos:</p><p> melhor caso : C(n) = (1 + 1 + ... + 1) = n - 1 pior caso : C(n) = (2 + 3 + + n) = pior caso : C(n) (2 + 3 + ... + n) </p><p>n2/2 + n/2 + 1 caso medio : C(n) = (3 + 4 + ... + n + 1) =</p><p>n2/4 + 3n/4 - 1</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p> AnliseS j M( ) f t d Seja M(n) a funo que conta o nmero de movimentaes de registros.</p><p> O nmero de movimentaes na i-sima iterao O nmero de movimentaes na i sima iterao :</p><p>Mi(n) = Ci (n) - 1 + 3 = Ci (n) + 2 Logo, o nmero de movimentos : melhor caso : M(n) = (3 + 3 + ... + 3) = 3(n-1) pior caso : M(n) = (4 + 5 + + n + 2) = pior caso : M(n) = (4 + 5 + ... + n + 2) =</p><p>n2/2 + 5n/2 - 3 caso medio : M(n) = (5 + 6 + + n + 3) =</p><p>n2/4 + 11n/4 3n2/4 + 11n/4 - 3</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Ordenao por Insero</p><p> O nmero mnimo de comparaes e movimentos ocorre quando os itens estomovimentos ocorre quando os itens esto originalmente em ordem.</p><p> O nmero mximo ocorre quando os itens qesto originalmente na ordem reversa.</p><p> o mtodo a ser utilizado quando o arquivo est q ase ordenadoest quase ordenado.</p><p> um bom mtodo quando se deseja adicionar uns poucos itens a um arquivoadicionar uns poucos itens a um arquivo ordenado, pois o custo linear.</p><p> O algoritmo de ordenao por insero g p estvel.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p> Proposto por Shell em 1959. uma extenso do algoritmo de ordenao por uma extenso do algoritmo de ordenao por </p><p>insero. Problema com o algoritmo de ordenao por g p</p><p>insero: Troca itens adjacentes para determinar o ponto de </p><p>insero.insero. So efetuadas n - 1 comparaes e movimentaes </p><p>quando o menor item est na posio mais direita no vetorvetor.</p><p> O mtodo de Shell contorna este problema permitindo trocas de registros distantes um do outro.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p>O it d d h i Os itens separados de h posies so rearranjados.</p><p> Todo h-simo item leva a uma seqncia ordenadaordenada.</p><p>T l i di h d d Tal seqncia dita estar h-ordenada.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p> Exemplo de utilizao:</p><p> Quando h = 1, Shellsort corresponde ao Quando h 1, Shellsort corresponde ao algoritmo de insero.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p> Como escolher o valor de h:S i h Seqncia para h:</p><p>h(s) = 3h(s - 1) + 1, para s &gt; 1h( ) 1 1h(s) = 1, para s = 1.</p><p> Knuth (1973, p. 95) mostrou experimentalmente que esta seqncia difcil de ser batida por mais de 20% em eficincia.de 20% em eficincia.</p><p> A seqncia para h corresponde a 1, 4, 13, 40, 121, 364, 1.093, 3.280, ...</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p>void Shellsort (Item *A, Indice *n){ int i, j; int h = 1;Item x;do h = h * 3 + 1; while (h &lt; *n);do{ h /= 3;</p><p>for (i = h + 1; i x.Chave){ A[j] = A[j h]; j -= h;</p><p>if (j </p></li><li><p>ShellSort</p><p>A i l t d Sh ll t tili A implementao do Shellsort no utiliza registros sentinelas.</p><p> Seriam necessrios h registros sentinelas, uma para cada h ordenaouma para cada h-ordenao.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p> AnliseA razo da eficincia do algoritmo ainda no A razo da eficincia do algoritmo ainda no conhecida.</p><p> Ningum ainda foi capaz de analisar o algoritmo. A sua anlise contm alguns problemas matemticos </p><p>muito difceis.A comear pela prpria seqncia de incrementos A comear pela prpria seqncia de incrementos.</p><p> O que se sabe que cada incremento no deve ser mltiplo do anterior.p</p><p> Conjecturas referente ao nmero de comparaes para a seqncia de Knuth:</p><p>Conjetura 1 : C(n) = O(n )Conjetura 1 : C(n) = O(n1,25)Conjetura 2 : C(n) = O(n(ln n)2)</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>ShellSort</p><p> Vantagens:Sh ll t ti i d Shellsort uma tima opo para arquivos de tamanho moderado.</p><p> Sua implementao simples e requer uma Sua implementao simples e requer uma quantidade de cdigo pequena.</p><p> Desvantagens: O tempo de execuo do algoritmo sensvel </p><p>ordem inicial do arquivo. O mtodo no estvel,</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Quicksort</p><p> Proposto por Hoare em 1960 e publicado em 1962.1962.</p><p> o algoritmo de ordenao interna mais rpido que se conhece para uma ampla variedade de it situaes.</p><p> Provavelmente o mais utilizado. A idia bsica dividir o problema de ordenar A idia bsica dividir o problema de ordenar </p><p>um conjunto com n itens em dois problemas menores.</p><p> Os problemas menores so ordenados independentemente.</p><p> Os resultados so combinados para produzir a Os resultados so combinados para produzir a soluo final.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Quicksort</p><p> A parte mais delicada do mtodo o processo de partioprocesso de partio.</p><p> O vetor A[Esq..Dir] rearranjado por meio da escolha arbitrria de um piv xescolha arbitrria de um piv x.</p><p> O vetor A particionado em duas partes: A parte esquerda com chaves menores ou iguais A parte esquerda com chaves menores ou iguais </p><p>a x. A parte direita com chaves maiores ou iguais a x.p g</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Quicksort</p><p> Algoritmo para o particionamento:1 Escolha arbitrariamente um piv x1. 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 </p><p>cruzarem. Ao final, o vetor A[Esq..Dir] est particionado de </p><p>tal forma que:O it A[E ] A[E 1] A[j] 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] so maiores ou iguais a x.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Quicksort</p><p> Ilustrao do processo de partio:</p><p> O piv x escolhido como sendo A[(i + j) / 2]. Como inicialmente i = 1 e j = 6,</p><p>ento x = A[3] = D. Ao final do processo de partio i e j se cruzam Ao final do processo de partio i e j se cruzam </p><p>em i = 3 e j = 2.Algoritmos e Estrutura de Dados II</p></li><li><p>Quicksort</p><p> Funo Partio:void Particao(Indice Esq Indice Dirvoid Particao(Indice Esq, Indice Dir,</p><p>Indice *i, Indice *j, Item *A){ Item x, w;</p><p>*i Esq; *j Dir;*i = Esq; *j = Dir;x = A[(*i + *j)/2]; /* obtem o pivo x */do</p><p>hil i i{ while (x.Chave &gt; A[*i].Chave) (*i)++;while (x.Chave &lt; A[*j].Chave) (*j)--;if ((*i) (*j)){ w = A[*i]; A[*i] = A[*j]; A[*j] = w;</p><p>(*i)++; (*j)--;}</p><p>} while (*i </p></li><li><p>Quicksort</p><p>O l i t d di t P ti O anel interno do procedimento Particao extremamente simples.</p><p> Razo pela qual o algoritmo Quicksort to rpidorpido.</p><p>Algoritmos e Estrutura de Dados II</p></li><li><p>Qui...</p></li></ul>