Ordenação de vetores

  • Published on
    16-Jun-2015

  • View
    1.363

  • Download
    2

Embed Size (px)

Transcript

  • 1. OrdenaoOrdenao Livro Projeto de Algoritmos Nvio Ziviani Captulo 4 http://www2.dcc.ufmg.br/livros/algoritmos/

2. Ordenao Introduo Conceitos BsicosIntroduo Conceitos Bsicos Ordenao Interna Ordenao por Seleo p Ordenao por Insero ShellSort QuickSort HeapSort MergeSortMergeSort Ordenao Digital Ordenao Parcial Algoritmos e Estrutura de Dados II 3. Ordenao Ordenao Externa Intercalao Balanceada de Vrios Caminhos Implementao por meio de Seleo por Substituio Consideraes Prticas Intercalao Polifsica Q i k t E tQuicksort Externo Algoritmos e Estrutura de Dados II 4. Introduo Conceitos Bsicos Ordenar: processo de rearranjar um conjunto de objetos em uma ordem ascendente oude objetos em uma ordem ascendente ou descendente. A ordenao visa facilitar a recuperaoA ordenao visa facilitar a recuperao posterior de itens do conjunto ordenado. Dificuldade de se utilizar um catlogo telefnicoDificuldade de se utilizar um catlogo telefnico se os nomes das pessoas no estivessem listados em ordem alfabtica. Algoritmos e Estrutura de Dados II 5. Introduo Conceitos Bsicos Notao utilizada nos algoritmos: O l it t b lh b i t dOs algoritmos trabalham sobre os registros de um arquivo. Cada registro possui uma chave utilizada paraCada registro possui uma chave utilizada para controlar a ordenao. Podem existir outros componentes em um registro. Algoritmos e Estrutura de Dados II 6. Introduo Conceitos Bsicos Estrutura de um registro: typedef int ChaveTipo; typedef struct Item { Ch Ti ChChaveTipo Chave; /* outros componentes */ } Item;} Item; Qualquer tipo de chave sobre o qual existaQualquer tipo de chave sobre o qual exista uma regra de ordenao bem-definida pode ser utilizado.ser utilizado. Algoritmos e Estrutura de Dados II 7. Introduo Conceitos Bsicos 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. Alguns dos mtodos de ordenao maisAlguns dos mtodos de ordenao mais eficientes no so estveis. A estabilidade pode ser forada quando oA estabilidade pode ser forada quando o mtodo no-estvel. Sedgewick (1988) sugere agregar umSedgewick (1988) sugere agregar um pequeno ndice a cada chave antes de ordenar, ou ento aumentar a chave de alguma outra forma. Algoritmos e Estrutura de Dados II 8. Introduo Conceitos Bsicos Classificao dos mtodos de ordenao: O d i t i d d bOrdenao interna: arquivo a ser ordenado cabe todo na memria principal. Ordenao externa: arquivo a ser ordenado noOrdenao externa: arquivo a ser ordenado no cabe na memria principal. Diferenas entre os mtodos: Em um mtodo de ordenao interna, qualquer registro pode ser imediatamente acessadoregistro pode ser imediatamente acessado. Em um mtodo de ordenao externa, os registros so acessados seqencialmente ou emregistros so acessados seqencialmente ou em grandes blocos. Algoritmos e Estrutura de Dados II 9. Introduo Conceitos Bsicos A i i d t d d d A maioria dos mtodos de ordenao baseada em comparaes das chaves. Existem mtodos de ordenao que utilizam o princpio da distribuioo princpio da distribuio. Algoritmos e Estrutura de Dados II 10. Introduo Conceitos Bsicos Exemplo de ordenao por distribuio: considere o problema de ordenar um baralhoconsidere o problema de ordenar um baralho com 52 cartas na ordem: A < 2 < 3 < ... < 10 < J < Q < K ee < < < Algoritmos e Estrutura de Dados II 11. Introduo Conceitos Bsicos Algoritmo: 1 Di t ib i t b t t t1. Distribuir as cartas abertas em treze montes: 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 montes: paus, ouros, copas e espadas. 4. Colete os montes na ordem especificada. Algoritmos e Estrutura de Dados II 12. Introduo Conceitos Bsicos Mtodos como o ilustrado so tambm conhecidos como ordenao digital radixsortconhecidos como ordenao digital, radixsort ou bucketsort. O mtodo no utiliza comparao entre chaves.O mtodo no utiliza comparao entre chaves. Uma das dificuldades de implementar este mtodo est relacionada com o problema de lidar com cada monte. Se para cada monte ns reservarmos uma rea, t d d i t dento a demanda por memria extra pode tornar-se proibitiva. O custo para ordenar um arquivo com nO custo para ordenar um arquivo com n elementos da ordem de O(n). Algoritmos e Estrutura de Dados II 13. Ordenao Interna Na escolha de um algoritmo de ordenao interna deve ser considerado o tempo gastointerna deve ser considerado o tempo gasto pela ordenao. Sendo n o nmero registros no arquivo, asg q medidas de complexidade relevantes so: Nmero de comparaes C(n) entre chaves. N d i t M( ) d it dNmero de movimentaes M(n) de itens do arquivo. O uso econmico da memria disponvel p um requisito primordial na ordenao interna. Mtodos de ordenao in situ so os f idpreferidos. Algoritmos e Estrutura de Dados II 14. Ordenao Interna Mt d tili li t d d Mtodos que utilizam listas encadeadas no so muito utilizados. Mtodos que fazem cpias dos itens a serem ordenados possuem menorserem ordenados possuem menor importncia. Algoritmos e Estrutura de Dados II 15. Ordenao Interna Classificao dos mtodos de ordenao interna:interna: Mtodos simples: Adequados para pequenos arquivosAdequados para pequenos arquivos. Requerem O(n2) comparaes. Produzem programas pequenos. Mtodos eficientes: Adequados para arquivos maiores. Requerem O(n log n) comparaesRequerem O(n log n) comparaes. Usam menos comparaes. As comparaes so mais complexas nos detalhes. Mtodos simples so mais eficientes para pequenos arquivos. Algoritmos e Estrutura de Dados II 16. Ordenao Interna Tipos de dados e variveis utilizados nos algoritmos de ordenao interna:algoritmos de ordenao interna: typedef int Indice; typedef Item Vetor[MaxTam + 1];typedef Item Vetor[MaxTam + 1]; Vetor A; O ndice do vetor vai de 0 at MaxTam, devido s chaves sentinelas.devido s chaves sentinelas. O vetor a ser ordenado contm chaves nas posies de 1 at n.p Algoritmos e Estrutura de Dados II 17. Ordenao por Seleo Um dos algoritmos mais simples de ordenaoordenao. Al itAlgoritmo: Selecione o menor item do vetor. Troque o com o item da primeira posio do vetorTroque-o com o item da primeira posio do vetor. Repita essas duas operaes com os n - 1 itens restantes, depois com os n - 2 itens, at que resterestantes, depois com os n 2 itens, at que reste apenas um elemento. Algoritmos e Estrutura de Dados II 18. Ordenao por Seleo O mtodo ilustrado abaixo: As chaves em negrito sofreram uma trocaAs chaves em negrito sofreram uma troca entre si. Algoritmos e Estrutura de Dados II 19. Ordenao por Seleo void Selecao (Item *A, Indice *n) { Indice i, j, Min;{ Indice i, j, Min; Item x; for (i = 1; i = c[2i + 1], para todo i = 1, 2, ..., n/2 A definio pode ser facilmente visualizada em uma rvore binria completa: Algoritmos e Estrutura de Dados II 60. Heapsort Heaps bi i l trvore binria completa: Os ns so numerados de 1 a n. O primeiro n chamado raiz.O p e o c a ado a O n k/2 o pai do n k, para 1 < k = 0)) { i esq;j dir;i= esq;j= dir; do { while ((bits(A[i],b,1) == 0) && (i < j)) i++; while ((bits(A[j],b,1) == 1) && (i < j )) j--; t = A[i]; A[i] = A[j]; A[j] = t; } while (j != i);} while (j ! i); if (bits(A[dir],b,1)== 0) j++; radixexchange(esq, j-1, b-1,A); Algoritmos e Estrutura de Dados II radixexchange(j, dir, b-1,A); } } 110. Radix Sorting Se A[1..N] contm inteiros positivos menores que 232, ento eles podem ser representados como nmeros binrios de 31 bits. Solucao: for j:= 0 to M-1 do t[j] 0 Bit mais esquerda o bit 30, bit mais direita o bit 0. Para orden-los, basta chamar radixexchange(1,N,30) Note que somente os bits que diferem uma chave das demais socount[j] := 0; for i:=1 to N do count[A[i]] := count[A[i]] + 1; for j:=1 to M-1 do t[j] t[j] + t[j 1] Note que somente os bits que diferem uma chave das demais so investigados Uma vez que se atinge um prefixo que diferencia a chave das demais os demais bits (menos significativos) daquela chavecount[j] := count[j] + count[j-1]; for i:=N downto 1 do begin t[count[A[i]] := A[i]; t[A[i]] t[A[i]] 1 demais, os demais bits (menos significativos) daquela chave no so mais investigados. Em contrapartida, todos os bits de chaves iguais so investigados : no funciona bem se arquivo contm muitas chaves iguaiscount[A[i]] := count[A[i]] - 1; end; for i:= 1 to N do A[i]:= t[i]; Algoritmo eficiente se M nao for muito grande. Comple idade linear O(ma (N M)) no funciona bem se arquivo contm muitas chaves iguais Problema em potencial: parties degeneradas (todas chaves com o mesmo bit) R di h li i lh Q i k h Algoritmos e Estrutura de Dados II Complexidade linear O(max(N,M)) Base para algoritmos radix sortings 8 Radix exchange ligeiramente melhor que Quicksort se chaves verdadeiramente aleatrias, mas Quicksort se adapta melhor para situaes menos aleatrias. 111. Radix Sorting Straight Radix Sorting: Examina os bits da direita para a esquerda, m bits por vez. Solucao: for j:= 0 to M-1 do t[j] 0 Examina os bits da direita para a esquerda, m bits por vez. W = Nmero de bits de uma chave; mltiplo de m A cada passo reordene as chaves utilizando Distribution count[j] := 0; for i:=1 to N do count[A[i]] := count[A[i]] + 1; for j:=1 to M-1 do t[j] t[j] + t[j 1] Counting considerando os m bits. Neste caso, o vetor de contadores tem tamanho M = 2m Cada passo executa em tempo linearcount[j] := count[j] + count[j-1]; for i:=N downto 1 do begin t[count[A[i]] := A[i]; t[A[i]] t[A[i]] 1 Cada passo executa em tempo linear. Mask = mscara com m bits iguais a 1 (mask = 2m -1) Nmero de passos: W / m count[A[i]] := count[A[i]] - 1; end; for i:= 1 to N do A[i]:= t[i]; Algoritmo eficiente se M nao for muito grande. Comple idade linear O(ma (N M)) Tem-se um compromisso entre espao e tempo Quanto maior m, mais rpido o algoritmo roda, mas mais espao necessr