Apresentação Power Point - Algoritmos de Ordenação Interna e Externa

Ordenação Última alteração 31 de Agosto de 2010 Transparências elaboradas por Charles Ornelas Almeida Israel Guerra e Nivio Ziviani Projeto de Algoritmos Cap4 Ordenação 1 Conteúdo do Capítulo 41 Ordenação Interna 411 Seleção 412 Inserção 413 Shellsort 414 Quicksort 415 Heapsort Filas de Prioridades Heaps 416 Ordenação Parcial Seleção Parcial Inserção Parcial Heapsort Parcial Quicksort Parcial 417 Ordenação em Tempo Linear Ordenação por Contagem Radixsort para Inteiros Radixsort para Cadeias de Caracteres 42 Ordenação Externa 421 Intercalação Balanceada de Vários Caminhos 422 Implementação por meio de Seleção por Substituição 423 Considerações Práticas 424 Intercalação Polifásica 425 Quicksort Externo Projeto de Algoritmos Cap4 Ordenação 2 Introdução Conceitos Básicos Ordenar processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente A ordenação visa facilitar a recuperação posterior de itens do conjunto ordenado Dificuldade de se utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética Notação utilizada nos algoritmos Os algoritmos trabalham sobre os registros de um arquivo Cada registro possui uma chave utilizada para controlar a ordenação Podem existir outros componentes em um registro Projeto de Algoritmos Cap4 Ordenação 3 Introdução Conceitos Básicos Estrutura de um registro typedef long TipoChave typedef struct TipoItem TipoChave Chave outros componentes TipoItem Qualquer tipo de chave sobre o qual exista uma regra de ordenação bemdefinida pode ser utilizado Um método de ordenação é estável se a ordem relativa dos itens com chaves iguais não se altera durante a ordenação Alguns dos métodos de ordenação mais eficientes não são estáveis A estabilidade pode ser forçada quando o método é nãoestável Sedgewick 1988 sugere agregar um pequeno índice a cada chave antes de ordenar ou então aumentar a chave de alguma outra forma Projeto de Algoritmos Cap4 Ordenação 4 Introdução Conceitos Básicos Classificação dos métodos de ordenação Interna arquivo a ser ordenado cabe todo na memória principal Externa arquivo a ser ordenado não cabe na memória principal Diferenças entre os métodos Em um método de ordenação interna qualquer registro pode ser imediatamente acessado Em um método de ordenação externa os registros são acessados seqüencialmente ou em grandes blocos A maioria dos métodos de ordenação é baseada em comparações das chaves Existem métodos de ordenação que utilizam o princípio da distribuição Projeto de Algoritmos Cap4 Ordenação 5 Introdução Conceitos Básicos Exemplo de ordenação por distribuição considere o problema de ordenar um baralho com 52 cartas na ordem A 2 3 10 J Q K e Algoritmo 1 Distribuir as cartas em treze montes ases dois três reis 2 Colete os montes na ordem especificada 3 Distribua novamente as cartas em quatro montes paus ouros copas e espadas 4 Colete os montes na ordem especificada Projeto de Algoritmos Cap4 Ordenação 6 Introdução Conceitos Básicos Métodos como o ilustrado são também conhecidos como ordenação digital radixsort ou bucketsort O método não utiliza comparação entre chaves Uma das dificuldades de implementar este método está relacionada com o problema de lidar com cada monte Se para cada monte nós reservarmos uma área então a demanda por memória extra pode tornarse proibitiva O custo para ordenar um arquivo com n elementos é da ordem de On Projeto de Algoritmos Cap4 Ordenação Seção 41 7 Ordenação Interna Na escolha de um algoritmo de ordenação interna deve ser considerado o tempo gasto pela ordenação Sendo n o número registros no arquivo as medidas de complexidade relevantes são Número de comparações Cn entre chaves Número de movimentações Mn de itens do arquivo O uso econômico da memória disponível é um requisito primordial na ordenação interna Métodos de ordenação in situ são os preferidos Métodos que utilizam listas encadeadas não são muito utilizados Métodos que fazem cópias dos itens a serem ordenados possuem menor importância Projeto de Algoritmos Cap4 Ordenação Seção 41 8 Ordenação Interna Classificação dos métodos de ordenação interna Métodos simples Adequados para pequenos arquivos Requerem On2 comparações Produzem programas pequenos Métodos eficientes Adequados para arquivos maiores Requerem On log n comparações Usam menos comparações As comparações são mais complexas nos detalhes Métodos simples são mais eficientes para pequenos arquivos Projeto de Algoritmos Cap4 Ordenação Seção 41 9 Ordenação Interna Tipos de dados e variáveis utilizados nos algoritmos de ordenação interna typedef int TipoIndice typedef TipoItem TipoVetorMAXTAM 1 MAXTAM 1 por causa da sentinela em Insercao TipoVetor A O índice do vetor vai de 0 até MaxTam devido às chaves sentinelas O vetor a ser ordenado contém chaves nas posições de 1 até n Projeto de Algoritmos Cap4 Ordenação Seção 411 10 Ordenação por Seleção 1 Um dos algoritmos mais simples de ordenação Algoritmo Selecione o menor item do vetor Troqueo com o item da primeira posição do vetor Repita essas duas operações com os n 1 itens restantes depois com os n 2 itens até que reste apenas um elemento Projeto de Algoritmos Cap4 Ordenação Seção 411 11 Ordenação por Seleção 2 O método é ilustrado abaixo 1 2 3 4 5 6 Chaves iniciais O R D E N A i 1 A R D E N O i 2 A D R E N O i 3 A D E R N O i 4 A D E N R O i 5 A D E N O R As chaves em negrito sofreram uma troca entre si Projeto de Algoritmos Cap4 Ordenação Seção 411 12 Ordenação por Seleção void SelecaoTipoItem A TipoIndice n TipoIndice i j Min TipoItem x for i 1 i n 1 i Min i for j i 1 j n j if A j Chave AMinChave Min j x AMin AMin A i A i x Comparações entre chaves e movimentações de registros Cn n2 2 n 2 Mn 3n 1 A atribuição Min j é executada em média n log n vezes Knuth 1973 Projeto de Algoritmos Cap4 Ordenação Seção 411 13 Ordenação por Seleção Vantagens Custo linar para o número de movimentos de registros É o algoritmo a ser utilizado para arquivos com registros muito grandes É muito interessante para arquivos pequenos Desvantagens O fato de o arquivo já estar ordenado não ajuda em nada pois o custo continua quadrático O algoritmo não é estável Projeto de Algoritmos Cap4 Ordenação Seção 412 14 Ordenação por Inserção Método preferido dos jogadores de cartas Algoritmo Em cada passo a partir de i2 faça Selecione o iésimo item da seqüência fonte Coloqueo no lugar apropriado na seqüência destino de acordo com o critério de ordenação Projeto de Algoritmos Cap4 Ordenação Seção 412 15 Ordenação por Inserção O método é ilustrado abaixo 1 2 3 4 5 6 Chaves iniciais O R D E N A i 2 O R D E N A i 3 D O R E N A i 4 D E O R N A i 5 D E N O R A i 6 A D E N O R As chaves em negrito representam a seqüência destino Projeto de Algoritmos Cap4 Ordenação Seção 412 16 Ordenação por Inserção void InsercaoTipoItem A TipoIndice n TipoIndice i j TipoItem x for i 2 i n i x A i j i 1 A0 x sentinela while xChave A j Chave A j 1 A j j A j 1 x Projeto de Algoritmos Cap4 Ordenação Seção 412 17 Ordenação por Inserção Considerações sobre o algoritmo O processo de ordenação pode ser terminado pelas condições Um item com chave menor que o item em consideração é encontrado O final da seqüência destino é atingido à esquerda Solução Utilizar um registro sentinela na posição zero do vetor Projeto de Algoritmos Cap4 Ordenação Seção 412 18 Ordenação por Inserção Seja Cn a função que conta o número de comparações No anel mais interno na iésima iteração o valor de Ci é Melhor caso Cin 1 Pior caso Cin i Caso medio Cin 1 i 1 2 i i1 2 Assumindo que todas as permutações de n são igualmente prováveis no caso médio temos Melhor caso Cn 1 1 1 n 1 Pior caso Cn 2 3 n n2 2 n 2 1 Caso medio Cn 1 23 4 n 1 n2 4 3n 4 1 Projeto de Algoritmos Cap4 Ordenação Seção 412 19 Ordenação por Inserção Seja Mn a função que conta o número de movimentações de registros O número de movimentações na iésima iteração é Min Cin 1 3 Cin 2 Logo o número de movimentos é Melhor caso Mn 3 3 3 3n 1 Pior caso Mn 4 5 n 2 n2 2 5n 2 3 Caso medio Mn 1 25 6 n 3 n2 4 11n 4 3 Projeto de Algoritmos Cap4 Ordenação Seção 412 20 Ordenação por Inserção O número mínimo de comparações e movimentos ocorre quando os itens estão originalmente em ordem O número máximo ocorre quando os itens estão originalmente na ordem reversa É o método a ser utilizado quando o arquivo está quase ordenado É um bom método quando se deseja adicionar uns poucos itens a um arquivo ordenado pois o custo é linear O algoritmo de ordenação por inserção é estável Projeto de Algoritmos Cap4 Ordenação Seção 413 21 Shellsort Proposto por Shell em 1959 É uma extensão do algoritmo de ordenação por inserção Problema com o algoritmo de ordenação por inserção Troca itens adjacentes para determinar o ponto de inserção São efetuadas n 1 comparações e movimentações quando o menor item está na posição mais à direita no vetor O método de Shell contorna este problema permitindo trocas de registros distantes um do outro Projeto de Algoritmos Cap4 Ordenação Seção 413 22 Shellsort Os itens separados de h posições são rearranjados Todo hésimo item leva a uma seqüência ordenada Tal seqüência é dita estar hordenada Exemplo de utilização 1 2 3 4 5 6 Chaves iniciais O R D E N A h 4 N A D E O R h 2 D A N E O R h 1 A D E N O R Quando h 1 Shellsort corresponde ao algoritmo de inserção Projeto de Algoritmos Cap4 Ordenação Seção 413 23 Shellsort Como escolher o valor de h Seqüência para h hs 3hs 1 1 para s 1 hs 1 para s 1 Knuth 1973 p 95 mostrou experimentalmente que esta seqüência é difícil de ser batida por mais de 20 em eficiência A seqüência para h corresponde a 1 4 13 40 121 364 1093 3280 Projeto de Algoritmos Cap4 Ordenação Seção 413 24 Shellsort void ShellsortTipoItem A TipoIndice n int i j int h 1 TipoItem x do h h 3 1 while h n do h 3 for i h 1 i n i x A i j i while A j hChave xChave A j A j h j h if j h goto L999 L999 A j x while h 1 Projeto de Algoritmos Cap4 Ordenação Seção 413 25 Shellsort A implementação do Shellsort não utiliza registros sentinelas Seriam necessários h registros sentinelas uma para cada hordenação Projeto de Algoritmos Cap4 Ordenação Seção 413 26 Shellsort Análise A razão da eficiência do algoritmo ainda não é conhecida Ninguém ainda foi capaz de analisar o algoritmo A sua análise contém alguns problemas matemáticos muito difíceis A começar pela própria seqüência de incrementos O que se sabe é que cada incremento não deve ser múltiplo do anterior Conjecturas referente ao número de comparações para a seqüência de Knuth Conjetura 1 Cn On125 Conjetura 2 Cn Onln n2 Projeto de Algoritmos Cap4 Ordenação Seção 413 27 Shellsort Vantagens Shellsort é uma ótima opção para arquivos de tamanho moderado Sua implementação é simples e requer uma quantidade de código pequena Desvantagens O tempo de execução do algoritmo é sensível à ordem inicial do arquivo O método não é estável Projeto de Algoritmos Cap4 Ordenação Seção 414 28 Quicksort Proposto por Hoare em 1960 e publiccado em 1962 É o algoritmo de ordenação interna mais rápido que se conhece para uma ampla variedade de situações Provavelmente é o mais utilizado A idéia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores Os problemas menores são ordenados independentemente Os resultados são combinados para produzir a solução final Projeto de Algoritmos Cap4 Ordenação Seção 414 29 Quicksort A parte mais delicada do método é o processo de partição O vetor AEsqDir é rearranjado por meio da escolha arbitrária de um pivô x O vetor A é particionado em duas partes A parte esquerda com chaves menores ou iguais a x A parte direita com chaves maiores ou iguais a x Projeto de Algoritmos Cap4 Ordenação Seção 414 30 Quicksort Algoritmo para o particionamento 1 Escolha arbitrariamente um pivô x 2 Percorra o vetor a partir da esquerda até que Ai x 3 Percorra o vetor a partir da direita até que Aj x 4 Troque Ai com Aj 5 Continue este processo até os apontadores i e j se cruzarem Ao final o vetor AEsqDir está particionado de tal forma que Os itens em AEsq AEsq 1 Aj são menores ou iguais a x Os itens em Ai Ai 1 ADir são maiores ou iguais a x Projeto de Algoritmos Cap4 Ordenação Seção 414 31 Quicksort Ilustração do processo de partição 1 2 3 4 5 6 O R D E N A A R D E N O A D R E N O O pivô x é escolhido como sendo Ai j div 2 Como inicialmente i 1 e j 6 então x A3 D Ao final do processo de partição i e j se cruzam em i 3 e j 2 Projeto de Algoritmos Cap4 Ordenação Seção 414 32 Quicksort Procedimento Particao void ParticaoTipoIndice Esq TipoIndice Dir TipoIndice i TipoIndice j TipoItem A TipoItem x w i Esq j Dir x A i j 2 obtem o pivo x do while xChave A i Chave i while xChave A j Chave j if i j w A i A i A j A j w i j while i j O anel interno do procedimento Particao é extremamente simples Razão pela qual o algoritmo Quicksort é tão rápido Projeto de Algoritmos Cap4 Ordenação Seção 414 33 Quicksort Procedimento Quicksort Entra aqui o procedimento Particao da transparencia 32 void OrdenaTipoIndice Esq TipoIndice Dir TipoItem A TipoIndice i j ParticaoEsq Dir i j A if Esq j OrdenaEsq j A if i Dir Ordena i Dir A void QuickSortTipoItem A TipoIndice n Ordena1 n A Projeto de Algoritmos Cap4 Ordenação Seção 414 34 Quicksort Exemplo do estado do vetor em cada chamada recursiva do procedimento Ordena 1 2 3 4 5 6 Chaves iniciais O R D E N A 1 A D R E N O 2 A D 3 E R N O 4 N R O 5 O R A D E N O R Projeto de Algoritmos Cap4 Ordenação Seção 414 35 Quicksort Análise Seja Cn a função que conta o número de comparações Pior caso Cn On2 O pior caso ocorre quando sistematicamente o pivô é escolhido como sendo um dos extremos de um arquivo já ordenado Isto faz com que o procedimento Ordena seja chamado recursivamente n vezes eliminando apenas um item em cada chamada O pior caso pode ser evitado empregando pequenas modificações no algoritmo Para isso basta escolher três itens quaisquer do vetor e usar a mediana dos três como pivô Projeto de Algoritmos Cap4 Ordenação Seção 414 36 Quicksort Análise Melhor caso Cn 2Cn2 n n log n n 1 Esta situação ocorre quando cada partição divide o arquivo em duas partes iguais Caso médio de acordo com Sedgewick e Flajolet 1996 p 17 Cn 1 386n log n 0 846n Isso significa que em média o tempo de execução do Quicksort é On log n Projeto de Algoritmos Cap4 Ordenação Seção 414 37 Quicksort Vantagens É extremamente eficiente para ordenar arquivos de dados Necessita de apenas uma pequena pilha como memória auxiliar Requer cerca de n log n comparações em média para ordenar n itens Desvantagens Tem um pior caso On2 comparações Sua implementação é muito delicada e difícil Um pequeno engano pode levar a efeitos inesperados para algumas entradas de dados O método não é estável Projeto de Algoritmos Cap4 Ordenação Seção 415 38 Heapsort Possui o mesmo princípio de funcionamento da ordenação por seleção Algoritmo 1 Selecione o menor item do vetor 2 Troqueo com o item da primeira posição do vetor 3 Repita estas operações com os n 1 itens restantes depois com os n 2 itens e assim sucessivamente O custo para encontrar o menor ou o maior item entre n itens é n 1 comparações Isso pode ser reduzido utilizando uma fila de prioridades Projeto de Algoritmos Cap4 Ordenação Seção 415 39 Heapsort Filas de Prioridades É uma estrutura de dados onde a chave de cada item reflete sua habilidade relativa de abandonar o conjunto de itens rapidamente Aplicações SOs usam filas de prioridades nas quais as chaves representam o tempo em que eventos devem ocorrer Métodos numéricos iterativos são baseados na seleção repetida de um item com maior menor valor Sistemas de gerência de memória usam a técnica de substituir a página menos utilizada na memória principal por uma nova página Projeto de Algoritmos Cap4 Ordenação Seção 415 40 Heapsort Filas de Prioridades Tipo Abstrato de Dados Operações 1 Constrói uma fila de prioridades a partir de um conjunto com n itens 2 Informa qual é o maior item do conjunto 3 Retira o item com maior chave 4 Insere um novo item 5 Aumenta o valor da chave do item i para um novo valor que é maior que o valor atual da chave 6 Substitui o maior item por um novo item a não ser que o novo item seja maior 7 Altera a prioridade de um item 8 Remove um item qualquer 9 Ajunta duas filas de prioridades em uma única Projeto de Algoritmos Cap4 Ordenação Seção 415 41 Heapsort Filas de Prioridades Representação Representação através de uma lista linear ordenada Neste caso Constrói leva tempo On log n Insere é On Retira é O1 Ajunta é On Representação é através de uma lista linear não ordenada Neste caso Constrói tem custo linear Insere é O1 Retira é On Ajunta é O1 para apontadores e On para arranjos Projeto de Algoritmos Cap4 Ordenação Seção 415 42 Heapsort Filas de Prioridades Representação A melhor representação é através de uma estruturas de dados chamada heap Neste caso Constrói é On Insere Retira Substitui e Altera são Olog n Observação Para implementar a operação Ajunta de forma eficiente e ainda preservar um custo logarítmico para as operações Insere Retira Substitui e Altera é necessário utilizar estruturas de dados mais sofisticadas tais como árvores binomiais Vuillemin 1978 Projeto de Algoritmos Cap4 Ordenação Seção 415 43 Heapsort Filas de Prioridades Algoritmos de Ordenação As operações das filas de prioridades podem ser utilizadas para implementar algoritmos de ordenação Basta utilizar repetidamente a operação Insere para construir a fila de prioridades Em seguida utilizar repetidamente a operação Retira para receber os itens na ordem reversa O uso de listas lineares não ordenadas corresponde ao método da seleção O uso de listas lineares ordenadas corresponde ao método da inserção O uso de heaps corresponde ao método Heapsort Projeto de Algoritmos Cap4 Ordenação Seção 415 44 Heap É uma seqüência de itens com chaves c1 c2 cn tal que ci c2i ci c2i 1 para todo i 1 2 n2 A definição pode ser facilmente visualizada em uma árvore binária completa 1 2 3 7 5 6 4 E N R S O A D Projeto de Algoritmos Cap4 Ordenação Seção 415 45 Heap Árvore binária completa Os nós são numerados de 1 a n O primeiro nó é chamado raiz O nó k2 é o pai do nó k para 1 k n Os nós 2k e 2k 1 são os filhos à esquerda e à direita do nó k para 1 k k2 Projeto de Algoritmos Cap4 Ordenação Seção 415 46 Heap As chaves na árvore satisfazem a condição do heap A chave em cada nó é maior do que as chaves em seus filhos A chave no nó raiz é a maior chave do conjunto Uma árvore binária completa pode ser representada por um array 1 2 3 4 5 6 7 S R O E N A D A representação é extremamente compacta Permite caminhar pelos nós da árvore facilmente Os filhos de um nó i estão nas posições 2i e 2i 1 O pai de um nó i está na posição i div 2 Projeto de Algoritmos Cap4 Ordenação Seção 415 47 Heap Na representação do heap em um arranjo a maior chave está sempre na posição 1 do vetor Os algoritmos para implementar as operações sobre o heap operam ao longo de um dos caminhos da árvore Um algoritmo elegante para construir o heap foi proposto por Floyd em 1964 O algoritmo não necessita de nenhuma memória auxiliar Dado um vetor A1 A2 An Os itens An2 1 An2 2 An formam um heap Neste intervalo não existem dois índices i e j tais que j 2i ou j 2i 1 Projeto de Algoritmos Cap4 Ordenação Seção 415 48 Heap 1 2 3 4 5 6 7 Chaves iniciais O R D E N A S Esq 3 O R S E N A D Esq 2 O R S E N A D Esq 1 S R O E N A D Os itens de A4 a A7 formam um heap O heap é estendido para a esquerda Esq 3 englobando o item A3 pai dos itens A6 e A7 Projeto de Algoritmos Cap4 Ordenação Seção 415 49 Heap A condição de heap é violada O heap é refeito trocando os itens D e S O item R é incluindo no heap Esq 2 o que não viola a condição de heap O item O é incluindo no heap Esq 1 A Condição de heap violada O heap é refeito trocando os itens O e S encerrando o processo O Programa que implementa a operação que informa o item com maior chave TipoItem MaxTipoItem A return A1 Projeto de Algoritmos Cap4 Ordenação Seção 415 50 Heap Programa para refazer a condição de heap void RefazTipoIndice Esq TipoIndice Dir TipoItem A TipoIndice i Esq int j TipoItem x j i 2 x A i while j Dir if j Dir if A j Chave A j 1Chave j if xChave A j Chave goto L999 A i A j i j j i 2 L999 A i x Projeto de Algoritmos Cap4 Ordenação Seção 415 51 Heap Programa para construir o heap void ConstroiTipoItem A TipoIndice n TipoIndice Esq Esq n 2 1 while Esq 1 Esq RefazEsq n A Projeto de Algoritmos Cap4 Ordenação Seção 415 52 Heap Programa que implementa a operação de retirar o item com maior chave TipoItem RetiraMaxTipoItem A TipoIndice n TipoItem Maximo if n 1 printf Erro heap vazio else Maximo A1 A1 An n Refaz1 n A return Maximo Projeto de Algoritmos Cap4 Ordenação Seção 415 53 Heap Programa que implementa a operação de aumentar o valor da chave do item i void AumentaChaveTipoIndice i TipoChave ChaveNova TipoItem A TipoItem x if ChaveNova A i Chave printf Erro ChaveNova menor que a chave atual return A i Chave ChaveNova while i 1 A i 2Chave A i Chave x A i 2 A i 2 A i A i x i 2 Projeto de Algoritmos Cap4 Ordenação Seção 415 54 Heap Exemplo da operação de aumentar o valor da chave do item na posição i c a b d i i i i O E N S U D E E D A N E R S O R S O D U N U S R N O D R O tempo de execução do procedimento AumentaChave em um item do heap é Olog n Projeto de Algoritmos Cap4 Ordenação Seção 415 55 Heap Programa que implementa a operação de inserir um novo item no heap void InsereTipoItem x TipoItem A TipoIndice n n An x AnChave INTMIN AumentaChaven xChave A Projeto de Algoritmos Cap4 Ordenação Seção 415 56 Heapsort Algoritmo 1 Construir o heap 2 Troque o item na posição 1 do vetor raiz do heap com o item da posição n 3 Use o procedimento Refaz para reconstituir o heap para os itens A1 A2 An 1 4 Repita os passos 2 e 3 com os n 1 itens restantes depois com os n 2 até que reste apenas um item Projeto de Algoritmos Cap4 Ordenação Seção 415 57 Heapsort Exemplo de aplicação do Heapsort 1 2 3 4 5 6 7 S R O E N A D R N O E D A S O N A E D R N E A D O E D A N D A E A D O caminho seguido pelo procedimento Refaz para reconstituir a condição do heap está em negrito Por exemplo após a troca dos itens S e D na segunda linha da Figura o item D volta para a posição 5 após passar pelas posições 1 e 2 Projeto de Algoritmos Cap4 Ordenação Seção 415 58 Heapsort Programa que mostra a implementação do Heapsort void HeapsortTipoItem A TipoIndice n TipoIndice Esq Dir TipoItem x ConstroiA n constroi o heap Esq 1 Dir n while Dir 1 ordena o vetor x A1 A1 A Dir A Dir x Dir RefazEsq Dir A Análise O procedimento Refaz gasta cerca de log n opera ções no pior caso Logo Heapsort gasta um tempo de execução proporcional a n log n no pior caso Projeto de Algoritmos Cap4 Ordenação Seção 415 59 Heapsort Vantagens O comportamento do Heapsort é sempre On log n qualquer que seja a entrada Desvantagens O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort O Heapsort não é estável Recomendado Para aplicações que não podem tolerar eventualmente um caso desfavorável Não é recomendado para arquivos com poucos registros por causa do tempo necessário para construir o heap Projeto de Algoritmos Cap4 Ordenação Seção 415 60 Comparação entre os Métodos Complexidade Complexidade Inserção On2 Seleção On2 Shellsort On log n Quicksort On log n Heapsort On log n Apesar de não se conhecer analiticamente o comportamento do Shellsort ele é considerado um método eficiente Projeto de Algoritmos Cap4 Ordenação Seção 415 61 Comparação entre os Métodos Tempo de execução Oservação O método que levou menos tempo real para executar recebeu o valor 1 e os outros receberam valores relativos a ele Registros na ordem aleatória 500 5000 10000 30000 Inserção 113 87 161 Seleção 162 124 228 Shellsort 12 16 17 2 Quicksort 1 1 1 1 Heapsort 15 16 16 16 Projeto de Algoritmos Cap4 Ordenação Seção 415 62 Comparação entre os Métodos Registros na ordem ascendente 500 5000 10000 30000 Inserção 1 1 1 1 Seleção 128 1524 3066 Shellsort 39 68 73 81 Quicksort 41 63 68 71 Heapsort 122 208 224 246 Projeto de Algoritmos Cap4 Ordenação Seção 415 63 Comparação entre os Métodos Tempo de execução Registros na ordem descendente 500 5000 10000 30000 Inserção 403 305 575 Seleção 293 221 417 Shellsort 15 15 16 16 Quicksort 1 1 1 1 Heapsort 25 27 27 29 Projeto de Algoritmos Cap4 Ordenação Seção 415 64 Comparação entre os Métodos Observações sobre os métodos 1 Shellsort Quicksort e Heapsort têm a mesma ordem de grandeza 2 O Quicksort é o mais rápido para todos os tamanhos aleatórios experimentados 3 A relação HeapsortQuicksort é constante para todos os tamanhos 4 A relação ShellsortQuicksort aumenta se o número de elementos aumenta 5 Para arquivos pequenos 500 elementos o Shellsort é mais rápido que o Heapsort 6 Se a entrada aumenta o Heapsort é mais rápido que o Shellsort 7 O Inserção é o mais rápido se os elementos estão ordenados 8 O Inserção é o mais lento para qualquer tamanho se os elementos estão em ordem descendente 9 Entre os algoritmos de custo On2 o Inserção é melhor para todos os tamanhos aleatórios experimentados Projeto de Algoritmos Cap4 Ordenação Seção 415 65 Comparação entre os Métodos Influência da ordem inicial dos registros Shellsort Quicksort Heapsort 5000 10000 30000 5000 10000 30000 5000 10000 30000 Asc 1 1 1 1 1 1 11 11 11 Des 15 16 15 11 11 11 1 1 1 Ale 29 31 37 19 20 20 11 1 1 1 Shellsort é bastante sensível à ordenação ascendente ou descendente da entrada 2 Em arquivos do mesmo tamanho o Shellsort executa mais rápido para arquivos ordenados 3 Quicksort é sensível à ordenação ascendente ou descendente da entrada 4 Em arquivos do mesmo tamanho o Quicksort executa mais rápido para arquivos ordenados 5 O Quicksort é o mais rápido para qualquer tamanho para arquivos na ordem ascendente 6 O Heapsort praticamente não é sensível à ordenação da entrada Projeto de Algoritmos Cap4 Ordenação Seção 415 66 Comparação entre os Métodos Método da Inserção É o mais interessante para arquivos com menos do que 20 elementos O método é estável Possui comportamento melhor do que o método da bolha Bubblesort que também é estável Sua implementação é tão simples quanto as implementações do Bubblesort e Seleção Para arquivos já ordenados o método é On O custo é linear para adicionar alguns elementos a um arquivo já ordenado Projeto de Algoritmos Cap4 Ordenação Seção 415 67 Comparação entre os Métodos Método da Seleção É vantajoso quanto ao número de movimentos de registros que é On Deve ser usado para arquivos com registros muito grandes desde que o tamanho do arquivo não exceda 1000 elementos Projeto de Algoritmos Cap4 Ordenação Seção 415 68 Comparação entre os Métodos Shellsort É o método a ser escolhido para a maioria das aplicações por ser muito eficiente para arquivos de tamanho moderado Mesmo para arquivos grandes o método é cerca de apenas duas vezes mais lento do que o Quicksort Sua implementação é simples e geralmente resulta em um programa pequeno Não possui um pior caso ruim e quando encontra um arquivo parcialmente ordenado trabalha menos Projeto de Algoritmos Cap4 Ordenação Seção 415 69 Comparação entre os Métodos Quicksort É o algoritmo mais eficiente que existe para uma grande variedade de situações É um método bastante frágil no sentido de que qualquer erro de implementação pode ser difícil de ser detectado O algoritmo é recursivo o que demanda uma pequena quantidade de memória adicional Seu desempenho é da ordem de On2 operações no pior caso O principal cuidado a ser tomado é com relação à escolha do pivô A escolha do elemento do meio do arranjo melhora muito o desempenho quando o arquivo está total ou parcialmente ordenado O pior caso tem uma probabilidade muito remota de ocorrer quando os elementos forem aleatórios Projeto de Algoritmos Cap4 Ordenação Seção 415 70 Comparação entre os Métodos Quicksort Geralmente se usa a mediana de uma amostra de três elementos para evitar o pior caso Esta solução melhora o caso médio ligeiramente Outra importante melhoria para o desempenho do Quicksort é evitar chamadas recursivas para pequenos subarquivos Para isto basta chamar um método de ordenação simples nos arquivos pequenos A melhoria no desempenho é significativa podendo chegar a 20 para a maioria das aplicações Sedgewick 1988 Projeto de Algoritmos Cap4 Ordenação Seção 415 71 Comparação entre os Métodos Heapsort É um método de ordenação elegante e eficiente Apesar de ser cerca de duas vezes mais lento do que o Quicksort não necessita de nenhuma memória adicional Executa sempre em tempo proporcional a n log n Aplicações que não podem tolerar eventuais variações no tempo esperado de execução devem usar o Heapsort Projeto de Algoritmos Cap4 Ordenação Seção 415 72 Comparação entre os Métodos Considerações finais Para registros muito grandes é desejável que o método de ordenação realize apenas n movimentos dos registros Com o uso de uma ordenação indireta é possível se conseguir isso Suponha que o arquivo A contenha os seguintes registros A1 A2 An Seja P um arranjo P1 P2 Pn de apontadores Os registros somente são acessados para fins de comparações e toda movimentação é realizada sobre os apontadores Ao final P1 contém o índice do menor elemento de A P2 o índice do segundo menor e assim sucessivamente Essa estratégia pode ser utilizada para qualquer dos métodos de ordenação interna Projeto de Algoritmos Cap4 Ordenação Seção 416 73 Ordenação Parcial Consiste em obter os k primeiros elementos de um arranjo ordenado com n elementos Quando k 1 o problema se reduz a encontrar o mínimo ou o máximo de um conjunto de elementos Quando k n caímos no problema clássico de ordenação Projeto de Algoritmos Cap4 Ordenação Seção 416 74 Ordenação Parcial Aplicações Facilitar a busca de informação na Web com as máquinas de busca É comum uma consulta na Web retornar centenas de milhares de documentos relacionados com a consulta O usuário está interessado apenas nos k documentos mais relevantes Em geral k é menor do que 200 documentos Normalmente são consultados apenas os dez primeiros Assim são necessários algoritmos eficientes de ordenação parcial Projeto de Algoritmos Cap4 Ordenação Seção 416 75 Ordenação Parcial Algoritmos considerados Seleção parcial Inserção parcial Heapsort parcial Quicksort parcial Projeto de Algoritmos Cap4 Ordenação Seção 416 76 Seleção Parcial Um dos algoritmos mais simples Princípio de funcionamento Selecione o menor item do vetor Troqueo com o item que está na primeira posição do vetor Repita estas duas operações com os itens n 1 n 2 n k Projeto de Algoritmos Cap4 Ordenação Seção 416 77 Seleção Parcial void SelecaoParcialTipoVetor A TipoIndice n TipoIndice k TipoIndice i j Min TipoItem x for i 1 i k i Min i for j i 1 j n j if A j Chave AMinChave Min j x AMin AMin A i A i x Análise Comparações entre cha ves e movimentações de registros Cn kn k2 2 k 2 Mn 3k Projeto de Algoritmos Cap4 Ordenação Seção 416 78 Seleção Parcial É muito simples de ser obtido a partir da implementação do algoritmo de ordenação por seleção Possui um comportamento espetacular quanto ao número de movimentos de registros Tempo de execução é linear no tamanho de k Projeto de Algoritmos Cap4 Ordenação Seção 416 79 Inserção Parcial Pode ser obtido a partir do algoritmo de ordenação por Inserção por meio de uma modificação simples Tendo sido ordenados os primeiros k itens o item da késima posição funciona como um pivô Quando um item entre os restantes é menor do que o pivô ele é inserido na posição correta entre os k itens de acordo com o algoritmo original Projeto de Algoritmos Cap4 Ordenação Seção 416 80 Inserção Parcial void InsercaoParcialTipoVetor A TipoIndice n TipoIndice k Nao preserva o restante do vetor TipoIndice i j TipoItem x for i 2 i n i x A i if i k j k else j i 1 A0 x sentinela while xChave A j Chave A j 1 A j j A j 1 x A modificação realizada verifica o momento em que i se torna maior do que k e então passa a considerar o valor de j igual a k a partir deste ponto Projeto de Algoritmos Cap4 Ordenação Seção 416 81 Inserção Parcial Preserva Restante do Vetor void InsercaoParcial2TipoVetor A TipoIndice n TipoIndice k Preserva o restante do vetor TipoIndice i j TipoItem x for i 2 i n i x A i if i k j k if xChave AkChave A i Ak else j i 1 A0 x sentinela while xChave A j Chave if j k A j 1 A j j if j k A j 1 x Projeto de Algoritmos Cap4 Ordenação Seção 416 82 Inserção Parcial Análise No anel mais interno na iésima iteração o valor de Ci é Melhor caso Cin 1 Pior caso Cin i Caso medio Cin 1 i 1 2 i i1 2 Assumindo que todas as permutações de n são igualmente prováveis o número de comparações é Melhor caso Cn 1 1 1 n 1 Pior caso Cn 2 3 k k 1n k kn n k2 2 k 2 1 Caso medio Cn 1 23 4 k 1 k 1n k kn 2 n 2 k2 4 k 4 1 Projeto de Algoritmos Cap4 Ordenação Seção 416 83 Inserção Parcial Análise O número de movimentações na iésima iteração é Min Cin 1 3 Cin 2 Logo o número de movimentos é Melhor caso Mn 3 3 3 3n 1 Pior caso Mn 4 5 k 2 k 1n k kn n k2 2 3k 2 3 Caso medio Mn 1 25 6 k 3 k 1n k kn 2 n 2 k2 4 5k 4 2 O número mínimo de comparações e movimentos ocorre quando os itens estão originalmente em ordem O número máximo ocorre quando os itens estão originalmente na ordem reversa Projeto de Algoritmos Cap4 Ordenação Seção 416 84 Heapsort Parcial Utiliza um tipo abstrato de dados heap para informar o menor item do conjunto Na primeira iteração o menor item que está em a1 raiz do heap é trocado com o item que está em An Em seguida o heap é refeito Novamente o menor está em A1 troqueo com An1 Repita as duas últimas operações até que o késimo menor seja trocado com An k Ao final os k menores estão nas k últimas posições do vetor A Projeto de Algoritmos Cap4 Ordenação Seção 416 85 Heapsort Parcial Entram aqui os procedimentos Refaz e Constroi das transparencias 50 e 51 Coloca menor em An segundo menor em An1 késimo em Ank void HeapsortParcialTipoItem A TipoIndice n TipoIndice k TipoIndice Esq 1 TipoIndice Dir TipoItem x long Aux 0 ConstroiA n constroi o heap Dir n while Aux k ordena o vetor x A1 A1 An Aux An Aux x Dir Aux RefazEsq Dir A Projeto de Algoritmos Cap4 Ordenação Seção 416 86 Heapsort Parcial Análise O HeapsortParcial deve construir um heap a um custo On O procedimento Refaz tem custo Olog n O procedimento HeapsortParcial chama o procedimento Refaz k vezes Logo o algoritmo apresenta a complexidade On k log n On se k n log n Ok log n se k n log n Projeto de Algoritmos Cap4 Ordenação Seção 416 87 Quicksort Parcial Assim como o Quicksort o Quicksort Parcial é o algoritmo de ordenação parcial mais rápido em várias situações A alteração no algoritmo para que ele ordene apenas os k primeiros itens dentre n itens é muito simples Basta abandonar a partição à direita toda vez que a partição à esquerda contiver k ou mais itens Assim a única alteração necessária no Quicksort é evitar a chamada recursiva OrdenaiDir Projeto de Algoritmos Cap4 Ordenação Seção 416 88 Quicksort Parcial 1 2 3 4 5 6 Chaves iniciais O R D E N A 1 A D R E N O 2 A D 3 E R N O 4 N R O 5 O R A D E N O R Considere k 3 e D o pivô para gerar as linhas 2 e 3 A partição à esquerda contém dois itens e a partição à direita quatro itens A partição à esquerda contém menos do que k itens Logo a partição direita não pode ser abandonada Considere E o pivô na linha 3 A partição à esquerda contém três itens e a partição à direita também Assim a partição à direita pode ser abandonada Projeto de Algoritmos Cap4 Ordenação Seção 416 89 Quicksort Parcial void OrdenaTipoVetor A TipoIndice Esq TipoIndice Dir TipoIndice k TipoIndice i j ParticaoA Esq Dir i j if j Esq k 1 if Esq j OrdenaA Esq j k return if Esq j OrdenaA Esq j k if i Dir OrdenaA i Dir k void QuickSortParcialTipoVetor A TipoIndice n TipoIndice k OrdenaA 1 n k Projeto de Algoritmos Cap4 Ordenação Seção 416 90 Quicksort Parcial Análise A análise do Quicksort é difícil O comportamento é muito sensível à escolha do pivô Podendo cair no melhor caso Ok log k Ou em algum valor entre o melhor caso e On log n Projeto de Algoritmos Cap4 Ordenação Seção 416 91 Comparação entre os Métodos de Ordenação Parcial 1 n k Seleção Quicksort Inserção Inserção2 Heapsort n 101 k 100 1 25 1 12 17 n 101 k 101 12 28 1 11 28 n 102 k 100 1 3 11 14 45 n 102 k 101 19 24 1 12 3 n 102 k 102 3 17 1 11 23 n 103 k 100 1 37 14 16 91 n 103 k 101 46 29 1 12 64 n 103 k 102 112 13 1 14 19 n 103 k 103 151 1 39 42 16 n 105 k 100 1 24 11 11 53 n 105 k 101 59 22 1 1 49 n 105 k 102 67 21 1 11 48 n 105 k 103 304 1 11 13 23 n 105 k 104 1445 1 331 433 17 n 105 k 105 1 19 Projeto de Algoritmos Cap4 Ordenação Seção 416 92 Comparação entre os Métodos de Ordenação Parcial 2 n k Seleção Quicksort Inserção Inserção2 Heapsort n 106 k 100 1 39 12 13 81 n 106 k 101 66 27 1 1 73 n 106 k 102 831 32 1 11 66 n 106 k 103 690 22 1 11 57 n 106 k 104 1 5 64 19 n 106 k 105 1 17 n 106 k 106 1 18 n 107 k 100 1 34 11 11 74 n 107 k 101 86 26 1 11 67 n 107 k 102 821 26 1 11 68 n 107 k 103 31 1 11 66 n 107 k 104 11 1 12 26 n 107 k 105 1 22 n 107 k 106 1 12 n 107 k 107 1 17 Projeto de Algoritmos Cap4 Ordenação Seção 416 93 Comparação entre os Métodos de Ordenação Parcial 1 Para valores de k até 1000 o método da InserçãoParcial é imbatível 2 O QuicksortParcial nunca ficar muito longe da InserçãoParcial 3 Na medida em que o k cresceo QuicksortParcial é a melhor opção 4 Para valores grandes de k o método da InserçãoParcial se torna ruim 5 Um método indicado para qualquer situação é o QuicksortParcial 6 O HeapsortParcial tem comportamento parecido com o do QuicksortParcial 7 No entano o HeapsortParcial é mais lento Projeto de Algoritmos Cap4 Ordenação Seção 417 94 Ordenação em Tempo Linear Nos algoritmos apresentados a seguir não existe comparação entre chaves Eles têm complexidade de tempo linear na prática Necessitam manter uma cópia em memória dos itens a serem ordenados e uma área temporária de trabalho Projeto de Algoritmos Cap4 Ordenação Seção 417 95 Ordenação por Contagem Este método assume que cada item do vetor A é um número inteiro entre 0 e k O algoritmo conta para cada item x o número de itens antes de x A seguir cada item é colocado no vetor de saída na sua posição definitiva Projeto de Algoritmos Cap4 Ordenação Seção 417 96 Ordenação por Contagem 1 1 1 3 4 8 4 3 4 5 6 7 0 2 0 1 1 1 A b c a d e 2 3 4 5 6 7 8 0 1 2 3 4 C B C 1 2 3 4 5 6 7 8 0 1 2 3 4 4 0 3 0 1 4 1 2 3 0 1 2 4 1 2 4 5 6 7 0 1 2 3 4 2 5 5 6 8 1 1 4 1 2 3 4 5 6 7 8 1 0 2 3 4 2 3 5 6 7 B C 1 1 4 B C 2 3 4 5 6 7 8 0 2 3 4 1 2 5 6 8 B f A contém oito chaves de inteiros entre 0 e 4 Cada etapa mostra a o vetor de entrada A e o vetor auxiliar C contendo o número de itens iguais a i 0 i 4 b o vetor C contendo o número de itens i 0 i 4 c d e os vetores auxiliares B e C após uma duas e três iterações considerando os itens em A da direita para a esquerda f o vetor auxiliar B ordenado Projeto de Algoritmos Cap4 Ordenação Seção 417 97 Ordenação por Contagem void ContagemTipoItem A TipoIndice n int k int i for i 0 i k i C i 0 for i 1 i n i CA i Chave CA i Chave 1 for i 1 i k i C i C i C i 1 for i n i 0 i BCA i Chave A i CA i Chave CA i Chave 1 for i 1 i n i A i B i Projeto de Algoritmos Cap4 Ordenação Seção 417 98 Ordenação por Contagem Os arranjos auxiliares B e C devem ser declarados fora do procedimento Contagem para evitar que sejam criados a cada chamada do procedimento No quarto for como podem haver itens iguais no vetor A então o valor de CAj é decrementado de 1 toda vez que um item Aj é colocado no vetor B Isso garante que o próximo item com valor igual a Aj se existir vai ser colocado na posição imediatamente antes de Aj no vetor B O último for copia para A o vetor B ordenado Essa cópia pode ser evitada colocando o vetor B como parâmetro de retorno no procedimento Contagem como mostrado no Exercício 424 A ordenação por contagem é um método estável Projeto de Algoritmos Cap4 Ordenação Seção 417 99 Ordenação por Contagem Análise O primeiro for tem custo Ok O segundo for tem custo On O terceiro for tem custo Ok O quarto for tem custo On k Na prática o algoritmo deve ser usado quando k On o que leva o algoritmo a ter custo On De outra maneira as complexidades de espaço e de tempo ficam proibitivas Na seção seguinte vamos apresentar um algoritmo prático e eficiente para qualquer valor de k Projeto de Algoritmos Cap4 Ordenação Seção 417 100 Radixsort para Inteiros Utiliza o princípio da distribuição das antigas classificadoras de cartões perfurados Os cartões eram organizados em 80 colunas e cada coluna permitia uma perfuração em 1 de 12 lugares Para números inteiros positivos apenas 10 posições da coluna eram usadas para os valores entre 0 e 9 A classificadora examinava uma coluna de cada cartão e distribuia mecanicamente o cartão em um dos 12 escaninhos dependendo do lugar onde fora perfurado Um operador então recolhia os 12 conjuntos de cartões na ordem desejada ascendente ou descendente Projeto de Algoritmos Cap4 Ordenação Seção 417 101 Radixsort para Inteiros Radixsort considera o dígito menos significativo primeiro e ordena os itens para aquele dígito Depois repete o processo para o segundo dígito menos significativo e assim sucessivamente 07 01 01 33 22 07 18 33 07 22 07 18 01 07 22 07 18 33 Projeto de Algoritmos Cap4 Ordenação Seção 417 102 Radixsort para Inteiros Primeiro refinamento define BASE 256 define M 8 define NBITS 32 RadixsortIntTipoItem A TipoIndice n for i 0 i NBITS M i Ordena A sobre o dígito i menos significativo usando um algoritmo estável O programa recebe o vetor A e o tamanho n do vetor O número de bits da chave NBits e o número de bits a considerar em cada passada m determinam o número de passadas que é igual a NBits div m Projeto de Algoritmos Cap4 Ordenação Seção 417 103 Radixsort para Inteiros O algoritmo de ordenação por contagem é uma excelente opção para ordenar o vetor A sobre o dígito i por ser estável e de custo On O vetor auxiliar C ocupa um espaço constante que depende apenas da base utilizada Por exemplo para a base 10 o vetor C armazena valores de k entre 0 e 9 isto é 10 posições A implementação a seguir utiliza Base 256 e o vetor C armazena valores de k entre 0 e 255 para representar os caracteres ASCII Nesse caso podemos ordenar inteiros de 32 bits 4 bytes com valores entre 0 e 232 em apenas d 4 chamadas do algoritmo de ordenação por contagem Projeto de Algoritmos Cap4 Ordenação Seção 417 104 Radixsort para Inteiros O algoritmo de ordenação por contagem precisa ser alterado para ordenar sobre m bits de cada chave do vetor A A função GetBits extrai um conjunto contíguo de m bits do número inteiro Em linguagem de máquina os bits são extraídos de números binários usando operações and shl shift left shr shift right e not complementa todos os bits Por exemplo os 2 bits menos significativos de um número x de 10 bits são extraídos movendo os bits para a direita com x shr 2 e uma operação and com a máscara 0000000011 Projeto de Algoritmos Cap4 Ordenação Seção 417 105 Ordenação por Contagem Alterado define GetBitsxk j x k 0 j void ContagemIntTipoItem A TipoIndice n int Pass int i j for i 0 i BASE 1 i C i 0 for i 1 i n i j GetBitsA i Chave Pass M M C j C j 1 if C0 n return for i 1 i BASE 1 i C i C i C i 1 for i n i 0 i j GetBitsA i Chave Pass M M BC j A i C j C j 1 for i 1 i n i A i B i Projeto de Algoritmos Cap4 Ordenação Seção 417 106 Radixsort para Inteiros No Programa quando qualquer posição i do vetor C contém um valor igual a n significa que todos os n números do vetor de entrada A são iguais a i Isso é verificado no comando if logo após o segundo for para C0 Nesse caso todos os valores de A são iguais a zero no byte considerado como chave de ordenação e o restante do anel não precisa ser executado Essa situação ocorre com frequência nos bytes mais significativos de um número inteiro Por exemplo para ordenar números de 32 bits que tenham valores entre 0 e 255 os três bytes mais significativos são iguais a zero Projeto de Algoritmos Cap4 Ordenação Seção 417 107 Radixsort para Inteiros void RadixsortIntTipoItem A TipoIndice n int i for i 0 i NBITS M i ContagemIntA n i Projeto de Algoritmos Cap4 Ordenação Seção 417 108 Radixsort para Inteiros Análise Cada passada sobre n inteiros em ContagemInt custa On Base Como são necessárias d passadas o custo total é Odn dBase Radixsort tem custo On quando d é constante e Base On Se cada número cabe em uma palavra de computador então ele pode ser tratado como um número de d dígitos na notação base n Para A contendo 1 bilhão de números de 32 bits 4 dígitos na base 28 256 apenas 4 chamadas de Contagem são necessárias Se considerarmos um algoritmo que utiliza o princípio da comparação de chaves como o Quicksort então são necessárias log n 30 operações por número considerando que uma palavra de computador ocupa Olog n bits Isso significa que o Radixsort é mais rápido para ordenar inteiros O aspecto negativo é o espaço adicional para B e C Projeto de Algoritmos Cap4 Ordenação Seção 417 109 Radixsort para Cadeias de Caracteres O algoritmo de ordenação por contagem precisa ser alterado para ordenar sobre o caractere k da chave de cada item x do vetor A void ContagemCarTipoItem A TipoIndice n int k int i j for i 0 i BASE 1 i C i 0 for i 1 i n i j int A i Chavek C j C j 1 if C0 n return for i 1 i BASE 1 i C i C i C i 1 for i n i 0 i j int A i Chavek BC j A i C j C j 1 for i 1 i n i A i B i Projeto de Algoritmos Cap4 Ordenação Seção 417 110 Radixsort para Cadeias de Caracteres void RadixsortCarTipoItem A TipoIndice n int i for i TAMCHAVE 1 i 0 iContagemCar A n i Projeto de Algoritmos Cap4 Ordenação Seção 42 111 Ordenação Externa A ordenação externa consiste em ordenar arquivos de tamanho maior que a memória interna disponível Os métodos de ordenação externa são muito diferentes dos de ordenação interna Na ordenação externa os algoritmos devem diminuir o número de acesso as unidades de memória externa Nas memórias externas os dados ficam em um arquivo seqüencial Apenas um registro pode ser acessado em um dado momento Essa é uma restrição forte se comparada com as possibilidades de acesso em um vetor Logo os métodos de ordenação interna são inadequados para ordenação externa Técnicas de ordenação diferentes devem ser utilizadas Projeto de Algoritmos Cap4 Ordenação Seção 42 112 Ordenação Externa Fatores que determinam as diferenças das técnicas de ordenação externa 1 Custo para acessar um item é algumas ordens de grandeza maior 2 O custo principal na ordenação externa é relacionado a transferência de dados entre a memória interna e externa 3 Existem restrições severas de acesso aos dados 4 O desenvolvimento de métodos de ordenação externa é muito dependente do estado atual da tecnologia 5 A variedade de tipos de unidades de memória externa torna os métodos dependentes de vários parâmetros 6 Assim apenas métodos gerais serão apresentados Projeto de Algoritmos Cap4 Ordenação Seção 42 113 Ordenação Externa O método mais importante é o de ordenação por intercalação Intercalar significa combinar dois ou mais blocos ordenados em um único bloco ordenado A intercalação é utilizada como uma operação auxiliar na ordenação Estratégia geral dos métodos de ordenação externa 1 Quebre o arquivo em blocos do tamanho da memória interna disponível 2 Ordene cada bloco na memória interna 3 Intercale os blocos ordenados fazendo várias passadas sobre o arquivo 4 A cada passada são criados blocos ordenados cada vez maiores até que todo o arquivo esteja ordenado Projeto de Algoritmos Cap4 Ordenação Seção 42 114 Ordenação Externa Os algoritmos para ordenação externa devem reduzir o número de passadas sobre o arquivo Uma boa medida de complexidade de um algoritmo de ordenação por intercalação é o número de vezes que um item é lido ou escrito na memória auxiliar Os bons métodos de ordenação geralmente envolvem no total menos do que dez passadas sobre o arquivo Projeto de Algoritmos Cap4 Ordenação Seção 421 115 Intercalação Balanceada de Vários Caminhos Considere um arquivo armazenado em uma fita de entrada I N T E R C A L A C A O B A L A N C E A D A Objetivo Ordenar os 22 registros e colocálos em uma fita de saída Os registros são lidos um após o outro Considere uma memória interna com capacidade para para três registros Considere que esteja disponível seis unidades de fita magnética Projeto de Algoritmos Cap4 Ordenação Seção 421 116 Intercalação Balanceada de Vários Caminhos Fase de criação dos blocos ordenados fita 1 I N T A C O A D E fita 2 C E R A B L A fita 3 A A L A C N Projeto de Algoritmos Cap4 Ordenação Seção 421 117 Intercalação Balanceada de Vários Caminhos Fase de intercalação Primeira passada 1 O primeiro registro de cada fita é lido 2 Retire o registro contendo a menor chave 3 Armazeneo em uma fita de saída 4 Leia um novo registro da fita de onde o registro retirado é proveniente 5 Ao ler o terceiro registro de um dos blocos sua fita fica inativa 6 A fita é reativada quando o terceiro registro das outras fitas forem lidos Projeto de Algoritmos Cap4 Ordenação Seção 421 118 Intercalação Balanceada de Vários Caminhos Fase de intercalação Primeira passada 7 Neste instante um bloco de nove registros ordenados foi formado na fita de saída 8 Repita o processo para os blocos restantes Resultado da primeira passada da segunda etapa fita 4 A A C E I L N R T fita 5 A A A B C C L N O fita 6 A A D E Projeto de Algoritmos Cap4 Ordenação Seção 421 119 Intercalação Balanceada de Vários Caminhos Quantas passadas são necessárias para ordenar um arquivo de tamanho arbitrário Seja n o número de registros do arquivo Suponha que cada registro ocupa m palavras na memória interna A primeira etapa produz nm blocos ordenados Seja Pn o número de passadas para a fase de intercalação Seja f o número de fitas utilizadas em cada passada Assim Pn logf n m No exemplo acima n22 m3 e f3 temos Pn log3 22 3 2 Projeto de Algoritmos Cap4 Ordenação Seção 421 120 Intercalação Balanceada de Vários Caminhos No exemplo foram utilizadas 2f fitas para uma intercalaçãodefcaminhos É possível usar apenas f 1 fitas Encaminhe todos os blocos para uma única fita Redistribuia estes blocos entre as fitas de onde eles foram lidos O custo envolvido é uma passada a mais em cada intercalação No caso do exemplo de 22 registros apenas quatro fitas seriam suficientes A intercalação dos blocos a partir das fitas 1 2 e 3 seria toda dirigida para a fita 4 Ao final o segundo e o terceiro blocos ordenados de nove registros seriam transferidos de volta para as fitas 1 e 2 Projeto de Algoritmos Cap4 Ordenação Seção 422 121 Implementação por meio de Seleção por Substituição A implementação do método de intercalação balanceada pode ser realizada utilizando filas de prioridades As duas fases do método podem ser implementadas de forma eficiente e elegante Operações básicas para formar blocos ordenados Obter o menor dentre os registros presentes na memória interna Substituílo pelo próximo registro da fita de entrada Estrutura ideal para implementar as operações heap Operação de substituição Retirar o menor item da fila de prioridades Colocar um novo item no seu lugar Reconstituir a propriedade do heap Projeto de Algoritmos Cap4 Ordenação Seção 422 122 Implementação por meio de Seleção por Substituição Algoritmo 1 Inserir m elementos do arquivo na fila de prioridades 2 Substituir o menor item da fila de prioridades pelo próximo item do arquivo 3 Se o próximo item é menor do que o que saiu então Considereo membro do próximo bloco Trateo como sendo maior do que todos os itens do bloco corrente 4 Se um item marcado vai para o topo da fila de prioridades então O bloco corrente é encerrado Um novo bloco ordenado é iniciado Projeto de Algoritmos Cap4 Ordenação Seção 422 123 Implementação por meio de Seleção por Substituição Entra 1 2 3 E I N T R N E T C R E T A T E C L A E C A C E L C E A L A L A C O A A C B A O C A B O C Entra 1 2 3 L C O A A L O A N O A A C A N A E A N C A C N E D E N A A N D A A D A A D D Primeira passada sobre o arquivo exemplo Os asteriscos indicam quais chaves pertencem a blocos diferentes Projeto de Algoritmos Cap4 Ordenação Seção 422 124 Implementação por meio de Seleção por Substituição Fase de intercalação dos blocos ordenados obtidos na primeira fase Operação básica obter o menor item dentre os ainda não retirados dos f blocos a serem intercalados Algoritmo Monte uma fila de prioridades de tamanho f A partir de cada uma das f entradas Substitua o item no topo da fila de prioridades pelo próximo item do mesmo bloco do item que está sendo substituído Imprima em outra fita o elemento substituído Projeto de Algoritmos Cap4 Ordenação Seção 422 125 Implementação por meio de Seleção por Substituição Exemplo Entra 1 2 3 A A C I L A C I E C L I R E L I N I L R L N R T N R R T T Para f pequeno não é vantajoso utilizar seleção por substituição para intercalar blocos Obtémse o menor item fa zendo f 1 comparações Quando f é 8 ou mais o método é adequado Obtémse o menor item fa zendo log2 f comparações Projeto de Algoritmos Cap4 Ordenação Seção 423 126 Considerações Práticas As operações de entrada e saída de dados devem ser implementadas eficientemente Devese procurar realizar a leitura a escrita e o processamento interno dos dados de forma simultânea Os computadores de maior porte possuem uma ou mais unidades independentes para processamento de entrada e saída Assim podese realizar processamento e operações de ES simultaneamente Projeto de Algoritmos Cap4 Ordenação Seção 423 127 Considerações Práticas Técnica para obter superposição de ES e processamento interno Utilize 2f áreas de entrada e 2f de saída Para cada unidade de entrada ou saída utilizase duas áreas de armazenamento 1 Uma para uso do processador central 2 Outra para uso do processador de entrada ou saída Para entrada o processador central usa uma das duas áreas enquanto a unidade de entrada está preenchendo a outra área Depois a utilização das áreas é invertida entre o processador de entrada e o processador central Para saída a mesma técnica é utilizada Projeto de Algoritmos Cap4 Ordenação Seção 423 128 Considerações Práticas Problemas com a técnica Apenas metade da memória disponível é utilizada Isso pode levar a uma ineficiência se o número de áreas for grande Ex Intercalaçãodefcaminhos para f grande Todas as f áreas de entrada em uma intercalaçãodefcaminhos se esvaziando aproximadamente ao mesmo tempo Projeto de Algoritmos Cap4 Ordenação Seção 423 129 Considerações Práticas Solução para os problemas Técnica de previsão Requer a utilização de uma única área extra de armazenamento durante a intercalação Superpõe a entrada da próxima área que precisa ser preenchida com a parte de processamento interno do algoritmo É fácil saber qual área ficará vazia primeiro Basta olhar para o último registro de cada área A área cujo último registro é o menor será a primeira a se esvaziar Projeto de Algoritmos Cap4 Ordenação Seção 423 130 Considerações Práticas Escolha da ordem de intercalação f Para fitas magnéticas f deve ser igual ao número de unidades de fita disponíveis menos um A fase de intercalação usa f fitas de entrada e uma fita de saída O número de fitas de entrada deve ser no mínimo dois Para discos magnéticos O mesmo raciocínio acima é válido O acesso seqüencial é mais eficiente Sedegwick 1988 sugere considerar f grande o suficiente para completar a ordenação em poucos passos Porém a melhor escolha para f depende de vários parâmetros relacionados com o sistema de computação disponível Projeto de Algoritmos Cap4 Ordenação Seção 424 131 Intercalação Polifásica Problema com a intercalação balanceada de vários caminhos Necessita de um grande número de fitas Faz várias leituras e escritas entre as fitas envolvidas Para uma intercalação balanceada de f caminhos são necessárias 2f fitas Alternativamente podese copiar o arquivo quase todo de uma única fita de saída para f fitas de entrada Isso reduz o número de fitas para f 1 Porém há um custo de uma cópia adicional do arquivo Solução Intercalação polifásica Projeto de Algoritmos Cap4 Ordenação Seção 424 132 Intercalação Polifásica Os blocos ordenados são distribuídos de forma desigual entre as fitas disponíveis Uma fita é deixada livre Em seguida a intercalação de blocos ordenados é executada até que uma das fitas esvazie Neste ponto uma das fitas de saída troca de papel com a fita de entrada Projeto de Algoritmos Cap4 Ordenação Seção 424 133 Intercalação Polifásica Exemplo Blocos ordenados obtidos por meio de seleção por substituição fita 1 I N R T A C E L A A B C L O fita 2 A A C E N A A D fita 3 Configuração após uma intercalaçãode2caminhos das fitas 1 e 2 para a fita 3 fita 1 A A B C L O fita 2 fita 3 A A C E I N N R T A A A C D E L Projeto de Algoritmos Cap4 Ordenação Seção 424 134 Intercalação Polifásica Exemplo Depois da intercalaçãode2caminhos das fitas 1 e 3 para a fita 2 fita 1 fita 2 A A A A B C C E I L N N O R T fita 3 A A A C D E L Finalmente fita 1 A A A A A A A B C C C D E E I L L N N O R T fita 2 fita 3 A intercalação é realizada em muitas fases As fases não envolvem todos os blocos Nenhuma cópia direta entre fitas é realizada Projeto de Algoritmos Cap4 Ordenação Seção 424 135 Intercalação Polifásica A implementação da intercalação polifásica é simples A parte mais delicada está na distribuição inicial dos blocos ordenados entre as fitas Distribuição dos blocos nas diversas etapas do exemplo fita 1 fita 2 fita 3 Total 3 2 0 5 1 0 2 3 0 1 1 2 1 0 0 1 Projeto de Algoritmos Cap4 Ordenação Seção 424 136 Intercalação Polifásica Análise A análise da intercalação polifásica é complicada O que se sabe é que ela é ligeiramente melhor do que a intercalação balanceada para valores pequenos de f Para valores de f 8 a intercalação balanceada pode ser mais rápida Projeto de Algoritmos Cap4 Ordenação Seção 425 137 Quicksort Externo Foi proposto por Monard em 1980 Utiliza o paradigma de divisão e conquista O algoritmo ordena in situ um arquivo A R1 Rn de n registros Os registros estão armazenados consecutivamente em memória secundária de acesso randômico O algoritmo utiliza somente Olog n unidades de memória interna e não é necessária nenhuma memória externa adicional Projeto de Algoritmos Cap4 Ordenação Seção 425 138 Quicksort Externo Seja Ri 1 i n o registro que se encontra na iésima posição de A Algoritmo 1 Particionar A da seguinte forma R1 Ri Ri1 Ri2 Rj2 Rj1 Rj Rn 2 chamar recursivamente o algoritmo em cada um dos subarquivos A1 R1 Ri e A2 Rj Rn Projeto de Algoritmos Cap4 Ordenação Seção 425 139 Quicksort Externo Para o partionamento é utilizanda uma área de armazenamento na memória interna Tamanho da área TamArea j i 1 com TamArea 3 Nas chamadas recusivas devese considerar que Primeiro deve ser ordenado o subarquivo de menor tamanho Condição para que na média Olog n subarquivos tenham o processamento adiado Subarquivos vazios ou com um único registro são ignorados Caso o arquivo de entrada A possua no máximo TamArea registros ele é ordenado em um único passo Projeto de Algoritmos Cap4 Ordenação Seção 425 140 Quicksort Externo 5 3 10 6 1 7 4 5 3 10 6 1 7 4 3 10 6 1 7 7 5 3 10 6 1 7 7 3 10 6 1 7 7 3 1 10 6 1 7 3 1 10 10 7 3 1 10 6 6 i Li j Es Ei Ls i j Es Ei Ls Li i j Ei Li Ls Es i j Ls Es Li Ei j Es Li Ls i Ei i Ei Ls j Es Li i Ei j Ls Li Es 4 5 3 7 4 5 3 7 7 4 5 3 7 3 4 5 7 4 5 4 5 5 3 10 6 1 7 4 5 3 10 6 1 7 4 3 10 6 1 7 7 5 3 10 6 1 7 7 3 10 6 1 7 7 3 1 10 6 1 7 3 1 10 1 4 5 6 10 7 3 i j Es Ei Li Ls i j Ei Ls Es Li i j Es Li Ei Ls j Es i Ei Ls Li i Ei j Es Ls Li i j Ls Li Es Ei j i Li Ls Ei Es 4 5 6 4 5 4 5 3 7 3 7 3 7 3 7 3 4 5 7 4 5 7 4 área Linf Lsup a c e g i k m n l j h f d b Linf Lsup área Projeto de Algoritmos Cap4 Ordenação Seção 425 141 Quicksort Externo void QuicksortExternoFILE ArqLi FILE ArqEi FILE ArqLEs int Esq int Dir int i j TipoArea Area Area de armazenamento interna if Dir Esq 1 return FAVaziaArea ParticaoArqLi ArqEi ArqLEs Area Esq Dir i j if i Esq Dir j ordene primeiro o subarquivo menor QuicksortExternoArqLi ArqEi ArqLEs Esq i QuicksortExternoArqLi ArqEi ArqLEs j Dir else QuicksortExternoArqLi ArqEi ArqLEs j Dir QuicksortExternoArqLi ArqEi ArqLEs Esq i Projeto de Algoritmos Cap4 Ordenação Seção 425 142 Quicksort Externo Procedimentos Auxiliares void LeSupFILE ArqLEsTipoRegistro UltLido int Lsshort OndeLer fseekArqLEs Ls 1 sizeofTipoRegistro SEEKSET freadUltLido sizeofTipoRegistro 1 ArqLEs Ls OndeLer FALSE void LeInfFILE ArqLiTipoRegistro UltLido int Li short OndeLer freadUltLido sizeofTipoRegistro 1 ArqLi Li OndeLer TRUE void InserirAreaTipoArea Area TipoRegistro UltLido int NRArea Insere UltLido de forma ordenada na Area InsereItemUltLido Area NRArea ObterNumCelOcupadasArea Projeto de Algoritmos Cap4 Ordenação Seção 425 143 Quicksort Externo Procedimentos Auxiliares void EscreveMaxFILE ArqLEs TipoRegistro R int Es fseekArqLEs Es 1 sizeofTipoRegistro SEEKSET fwriteR sizeofTipoRegistro 1 ArqLEs Es void EscreveMinFILE ArqEi TipoRegistro R int Ei fwriteR sizeofTipoRegistro 1 ArqEi Ei void RetiraMaxTipoArea Area TipoRegistro R int NRArea RetiraUltimoArea R NRArea ObterNumCelOcupadasArea void RetiraMinTipoArea Area TipoRegistro R int NRArea RetiraPrimeiroArea R NRArea ObterNumCelOcupadasArea Projeto de Algoritmos Cap4 Ordenação Seção 425 144 Quicksort Externo Procedimento Particao void ParticaoFILE ArqLi FILE ArqEi FILE ArqLEs TipoArea Area int Esq int Dir int i int j int Ls Dir Es Dir Li Esq Ei Esq NRArea 0 Linf INTMIN Lsup INTMAX short OndeLer TRUE TipoRegistro UltLido R fseek ArqLi Li 1 sizeofTipoRegistro SEEKSET fseek ArqEi Ei 1 sizeofTipoRegistro SEEKSET i Esq 1 j Dir 1 while Ls Li if NRArea TAMAREA 1 if OndeLer LeSupArqLEs UltLido Ls OndeLer else LeInfArqLi UltLido Li OndeLer InserirAreaArea UltLido NRArea continue if Ls Es LeSupArqLEs UltLido Ls OndeLer else if Li Ei LeInfArqLi UltLido Li OndeLer else if OndeLer LeSupArqLEs UltLido Ls OndeLer else LeInfArqLi UltLido Li OndeLer Projeto de Algoritmos Cap4 Ordenação Seção 425 145 Quicksort Externo Procedimento Particao if UltLidoChave Lsup j Es EscreveMaxArqLEs UltLido Es continue if UltLidoChave Linf i Ei EscreveMinArqEi UltLido Ei continue InserirAreaArea UltLido NRArea if Ei Esq Dir Es RetiraMinArea R NRArea EscreveMinArqEi R Ei Linf RChave else RetiraMaxArea R NRArea EscreveMaxArqLEs R Es Lsup RChave while Ei Es RetiraMinArea R NRArea EscreveMinArqEi R Ei Projeto de Algoritmos Cap4 Ordenação Seção 425 146 Quicksort Externo Programa Teste typedef int TipoApontador Entra aqui o Programa C23 typedef TipoItem TipoRegistro Declaracao dos tipos utilizados pelo quicksort externo FILE ArqLEs Gerencia o Ls e o Es FILE ArqLi Gerencia o Li FILE ArqEi Gerencia o Ei TipoItem R Entram aqui os Programas J4 D26 D27 e D28 int mainint argc char argv ArqLi fopen teste dat wb if ArqLi NULL printf Arquivo nao pode ser aberto exit 1 RChave 5 fwriteR sizeofTipoRegistro 1 ArqLi RChave 3 fwriteR sizeofTipoRegistro 1 ArqLi RChave 10 fwriteR sizeofTipoRegistro 1 ArqLi RChave 6 fwriteR sizeofTipoRegistro 1 ArqLi RChave 1 fwriteR sizeofTipoRegistro 1 ArqLi RChave 7 fwriteR sizeofTipoRegistro 1 ArqLi RChave 4 fwriteR sizeofTipoRegistro 1 ArqLi fcloseArqLi Projeto de Algoritmos Cap4 Ordenação Seção 425 147 Quicksort Externo Programa Teste ArqLi fopen teste dat rb if ArqLi NULL printf Arquivo nao pode ser aberto exit 1 ArqEi fopen teste dat rb if ArqEi NULL printf Arquivo nao pode ser aberto exit 1 ArqLEs fopen teste dat rb if ArqLEs NULL printf Arquivo nao pode ser aberto exit 1 QuicksortExternoArqLi ArqEi ArqLEs 1 7 fflush ArqLi fcloseArqEi fcloseArqLEs fseekArqLi0 SEEKSET whilefreadR sizeofTipoRegistro 1 ArqLi printf Registrod RChave fcloseArqLi return 0 Projeto de Algoritmos Cap4 Ordenação Seção 425 148 Quicksort Externo Análise Seja n o número de registros a serem ordenados Seja e b o tamanho do bloco de leitura ou gravação do Sistema operacional Melhor caso O n b Por exemplo ocorre quando o arquivo de entrada já está ordenado Pior caso O n2 TamArea ocorre quando um dos arquivos retornados pelo procedimento Particao tem o maior tamanho possível e o outro é vazio A medida que n cresce a probabilidade de ocorrência do pior caso tende a zero Caso Médio O n b log n TamArea É o que tem amaior probabilidade de ocorrer