Ordenação Externa e Intercalação de Arquivos

PESQUISA ORDENACAO E TECNICAS DE ARMAZENAMENTO UNIDADE 3 ORDENACAO EXTERNA E PROCESSOS DE INTERCALACAO DOS ARQUIVOS Keila Barbosa Costa 21082023 1627 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 228 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento ee Introducgao trodug A classificagado é uma das operacées fundamentais para 0 processamento dos elementos em qualquer banco de dados Com o crescente aumento da quantidade de informacoes o problema de classificar ou ordenalas dentro de um prazo estipulado se tornou um dos principais problemas para quase todos os aplicativos Vamos comegar esta unidade compreendendo o que é ordenacao externa e intercalacado de arquivos Para isso é interessante refletirmos sobre alguns pontos Sera que é possivel colocar dois ou mais baralhos de taré em ordem com todas aquelas quantidades de cartas usando apenas as duas mdos Respeitando a ordem é provavel que ndo se consiga colocar os naipes depois os numeros e assim por diante normalmente acabamos fazendo motins separando por naipes ou numeros certo Porqué Talvez seja porque essa ordenaao ultrapassa nossa capacidade manual ou até cognitiva de fazer essa ordenacdo de uma s6 vez Qual método podemos usar para fazer esse tipo de classificagdo O que abordaremos neste capitulo é praticamente isso Mas quando a intercalacdo é util ou nao nesse processo de classificagdo A ordenado externa é usada quando o processo de ordenacaéo em memoria principal nado puder ser realizado e estoura a capacidade do nosso computador ou seja quando tivermos um volume de dados tao grande que ndo é possivel transportalo para memoria principal Para introduzir a area de algoritmos de classificacdo os mais apropriados sao os métodos elementares Eles fornecem uma maneira facil de aprender terminologia e mecanismos basicos para ordenar algoritmos fornecendo um background mais sofisticado e adequado para classificagées Vamos conhecer os principais t6picos da ordenaao externa Acompanhe esta unidade com atenao ww 31 Ordenacao externa A classificagao diz respeito a operado ou técnica de organizar e reorganizar um grupo de dados em alguma ordem especifica ou seja é a execucdo da operacdo que organiza os registros de um conjunto de dados em alguma ordem de acordo com algum critério de ordem especifico As técnicas de classificagdo podem ser divididas em duas categorias classificagdo interna ou classificagdo externa Se todos os dados a serem classificadosordenados puderem ser ajustados por vez na memoria principal o método de classificacao interna estara sendo executado VIANA 2015 Nesta unidade em especifico veremos detalhes do processo de ordenacdo externa ou também conhecida como classificagdo externa A Ordenaao externa é um termo para uma classe de algoritmos de classificacao que podem lidar com grandes quantidades de dados ela é necessaria quando os dados que estado sendo ordenados nao se encaixam na memoria principal de um dispositivo de computado geralmente RAM e em vez disso devem residir na memoria externa mais lenta geralmente em um disco rigido ou seja a ordenaao externa é o processo de ordenacao com algum tipo de dispositivo de memoria externa como HD Fitas Pen Drives etc que tenha uma capacidade de memoria grande com muitos gigabytes maior que a memoria principal AGUILAR 2008 Usamos a ordenacdo externa quando nado conseguimos transportar todos os nossos registos para a memoria principal do computador e roda um algoritmo basico como o Shellsort ou Mergesort por exemplo Este processo tem como objetivo ordenar os registros ou seja colocar todo mundo em uma ordem pré estabelecida assim como a palavra ja sugere httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 328 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento SSS VOCE QUER VER O método ShellSort criado por Donald Shell em 1959 é um algoritmo de classificagao complexo e rapido que divide varias vezes de forma repetida toda a colecdo em subcolecées levando cada elemento hésimo para um intervalo h fixo e executando uma inserdo de classificacdo a cada subcolecao ele uma extensdo do algoritmo de ordenacdo por insercdo O ShellSort permite a troca de registros distantes diferenciando do algoritmo de ordenacao por insercdo que possui a troca de itens adjacentes para determinar o ponto de insercdo Para compreender melhor o funcionamento do algoritmo assista a este video httpswwwyoutubecomwatch vCmPA7zE8mx0 httpswwwyoutubecomwatchvCmPA7zE8mx0 SSS O problema de como ordenar os dados com eficiéncia tem sido amplamente discutido Na maioria das vezes a classificacdo é realizada por ordenaao externa na qual o arquivo de dados é muito grande para caber na memoria principal e deve residir na memoria secundaria As ES EntradaSaida de disco sao as medidas mais apropriadas no desempenho da ordenado externa e outros problemas externos porque a velocidade de ES é muito mais lenta que a velocidade da CPU Os algoritmos de ordenacdo externa geralmente se enquadram em dois tipos ordenado de distribuido que se assemelha a ordenacdo rapida e ordenado externa de mesclagem A ordenaao por mesclagem usada na computacdo também conhecida como mesclagem comum trata de um algoritmo bem usual de ordenagao eficiente que se baseia em comparacdo AGUILAR 2008 A maioria das implementaées produz uma ordenacado estavel o que significa que a ordem dos elementos iguais é a mesma na entrada e na saida httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 428 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento ee VOCE O CONHECE e John von Neumann foi um matematico que fez grandes contribuic6es na definiado teorias como a ergédica e a dos jogos mecanica geometria continua economia ciéncia da computado analise numérica hidrodindmica e estatistica Além disso em 1945 criou a classificagdo por mesclagem um algoritmo de divisdo e conquista KADAM 2000 a A ordenacéo externa de distribuiao é bem semelhante a ordenacdo de mesclagem que veremos nos proximos tdpicos esta normalmente usa uma estratégia hibrida de ordenado e mesclagem Na fase de ordenacdo sdo lidos pedacos de dados pequenos o suficiente para caber na memoria principal ordenados e gravados em um arquivo temporario Na fase de mesclagem os subarquivos ordenados sdo combinados em um unico arquivo maior A ordenaao externa mais comumente usada ainda é a de mesclagem conforme descrito por Knuth 1973 e Singh 1985 A seguir veremos algumas formas eficientes de processar uma intercalacdo também conhecida como mesclagem oe e ww e 32 Definiao de mecanismos Neste t6pico estudaremos as formas eficientes e os mecanismos de se processar uma intercalacdo As técnicas abordadas objetivam reduzir a gravacao dos registros de cada parte guardada em disco magnético também conhecida como area de trabalho e o numero de leitura desses registros De acordo com Viana 2015 os fatores que tém relevancia na eficiéncia de um algoritmo de classificagdo em geral sao os que vocé podera ver clicando nos cones a seguir O tamanho e o numero de registros de cada um deles Usar ou nao a memoria auxiliar necessita ou nao da ordenaao externa httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 528 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento Meios e tipos de armazenamento usado Periodicidade de atualizacdao e nivel de ordenaao ja existente do arquivo Ainda conforme Viana 2015 os fatores que influem na eficiéncia de um algoritmo de ordenaao externa sdo os que vocé podera ver clicando nos cones a seguir Numero de séries produzidas O tamanho das séries e se sao do mesmo tamanho As caracteristicas dos blocos e das memorias intermediarias utilizadas na fase de classificacao e a forma da distribuicdo das séries pelos arquivos de trabalho Dessa forma conforme Ziviani 2004 podemos concluir que existem trés fatores importantes que diferenciam os algoritmos de ordenacdo externa dos algoritmos de ordenado interna sdo os que vocé podera ver clicando no recurso a seguir O valor de acesso do item E a ordem de grandeza maior do que os valores de processamento na memoria interna O valor principal na ordenacao externa esta relacionado com o valor de mudar dados entre a memoria externa e a memoria interna Existem regras graves de acesso aos dados Por exemplo os itens guardados em fita magnética sé podem ser localizados em sequéncias os itens guardados em disco podem ser acessados de forma direta mas a um valor maior do que o valor para acessar de forma sequencial 0 que contraindica o uso de acesso direto httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 628 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento A depender do estado atual da tecnologia podemos medir o desempenho do desenvolvimento de métodos de ordenacao externa Muitos tipos e variedades de unidades de memoria externa podem tornar os métodos de ordenacdo externa dependentes de varios pardametros que afetam sua performance ee CASO Muitas vezes em nosso diaadia precisamos consultar dados ordenados Como por exemplo varias listas de telefones ou até mesmo muitas listas de remédios em se tratando de uma farmacia O simples fato de ter que procurar um remédio ou um telefone de contato em uma lista telefénica daria muito trabalho no caso de nado estarem em ordem alfabética ou numérica O principal papel da ordenagao é facilitar a busca e recuperacao da informacao Dispor as coisas em ordem esta presente em boa parte das aplicacées principalmente quando temos informagées que precisamos recuperar no futuro como no caso da lista telefénica ou da lista de remédios Ja imaginou ter que procurar nome por nome de cada remédio em varias tabelas armazenadas nos inimeros dispositivos como o Pen drive enquanto um cliente espera na farmacia por sua reposta sobre a disponibilidade do mesmo As listas ordenadas ajudam muito em nosso cotidiano quando temos objetos que foram armazenados e precisam ser pesquisados e recuperados ee Medimos a eficiéncia de uma classificacdo externa a partir da quantidade total do tempo necessario para que os dados sejam lidos classificados e gravados na area de trabalho dando inicio a primeira fase do processo de ordenacdo ou seja basicamente os algoritmos vdo separar os dados em diversas fontes e ordenar essas fontes Na segunda fase as fontes classificadas sao lidas e intercaladas em uma sequéncia de duas a duas trés a trés etc O numero de fontes intercaladas em cada etapa corresponde ao numero de caminhos Quanto maior for o numero de caminhos mais complexo sera o algoritmo de intercalacdéo também chamado de Merge De um modo geral usamos dois ou trés caminhos ja que este processo é usado diversas vezes para alcanar o agrupamento de todas as fontes Na sessdo a seguir apresentaremos os algoritmos de intercalacdo de dois caminhos de trés caminhos e de k caminhos httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 728 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento 33 Intercalagao de arquivos intercalacao de dois a caminhos intercalacao de tres caminhos intercalagao de k caminhos A intercalacdo é 0 processo de misturar diferentes tpicos e habilidades em boa parte das vezes é a mistura de tdpicos ou de fontes realmente diferentes como HDs Pen Drives ou ainda a mistura de outras fontes com novas fontes No caso por exemplo de uma escola trabalhar misturando tdépicos realmente diferentes como matematica e quimica ou a mistura de material antigo e novo No segundo caso em vez de estudarrevisar as coisas em uma ordem cronoldgica é misturado os assuntos melhorando a retendo dos tépicos Intercalar é a maneira de combinar dois trés ou mais blocos agrupados em um Unico grupo ordenado A intercalacdo é utilizada para auxiliar na ordenacdo como se fosse uma operacdo Quando usamos o termo intercalar estamos realmente nos referindo ao ato de anexar um item em ordem classificada a uma estrutura temporaria da matriz que foi construida ao longo do tempo a medida que continuamos classificando e acrescentando mais itens Essa etapa envolve comparar as listas e em seguida anexar a maior ao final da menor Mas quando a intercalado é util e quando nado é Voltaremos a ideia do baralho de Taré descrito na introducdo quando pegamos um baralho completo para ordenar qual a primeira coisa a fazer E provavel que o baralho seja separado por naipes ordenando o préximo passo é que se junte todo baralho fazendo a intercalacdo Nesse exemplo talvez nado seja preciso fazer muitas intercalagées porém a ideia é dividir em grupos menores e depois reintegrar em algo maior e ordenado E o que iremos ver nesta sessdo porém utilizando uma quantidade de fontes que chamamos de caminhos as vezes esses algoritmos serdo identificados como intercalacdo balanceada de dois caminhos trés caminhos e k caminhos SSS VOCE QUER LER Atualmente com as facilidades presentes para manipulacdo de bases de dados e arquivos as técnicas de fusdo de arquivos para a intercalacdo ou ordenado acabam esquecidas Contudo essas técnicas sao facilmente implementadas em ambientes de computaado com poucos recursos Um estudo bem interessante de Arbex 2009 utiliza técnicas de fusdo de arquivos para a intercalacdo ou ordenado de arquivos sequenciais Veja 0 artigo completo clicando aqui httpsseercesjfbrindexphpcesRevistaarticleviewFile706559 httpsseercesjfbrindexphpcesRevistaarticleviewFile706559 Se httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 828 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento O que esses caminhos querem dizer Dizem respeito a quantidade de fontes que sera intercalada para se criar algo mais ordenado Sendo assim voltando ao exemplo do baralho de taré quando pegamos separamos 0 baralho em quatro naipes e juntamos tudo em algo unico dirfamos que sdo quatro fontes Outro exemplo concreto é utilizando um conjunto de HDs externos para fazer a ordenacdo dependendo das quantidades de HDs externos temos a quantidades de caminhos Assim poderiamos definir a intercalacdo de arquivos como sendo a combinagao de dois ou mais blocos ordenados em um unico bloco agrupado A intercalacdo é utilizada na ordenado como uma operaao auxiliar ZIVIANI 2012 Conforme Ziviani 2012 com as fontes ja formadas podemos entao fazer a intercalacdo entre elas Para isso precisamos de alguns métodos que sejam responsaveis por fazer esse trabalho Estes métodos chamaremos de Merge2 Merge3 e o Mergek responsaveis por fazer a intercalacdo de duas fontes trés fontes e k fontes respectivamente veremos detalhes deste processo a seguir na proxima subsecao 331 Intercalagao de dois caminhos A intercalagao de dois caminhos também conhecida como Merge2 é 0 método responsavel por mesclar duas fontes Para exemplificar tomemos um arquivo com dez registros ou seja de Aj a Ayo de acordo com a figuraa seguir levando em consideraao que esses dez registros ndo sdo suportados pela memoria RAM O processo de intercalagao externa utilizando o processo intercalacdo de dois caminhos se da da seguinte forma dividindo esse arquivo ao meio ou préximo do meio de forma que ele consiga utilizar nessa primeira parte do arquivo um dos métodos de ordenacao e na segunda parte do arquivo 0 mesmo método de ordenaao em seguida é realizado o processo de intercalacdo entre os dois arquivos Perceba que aquele tinico arquivo apresentado anteriormente foi dividido em dois arquivos o Arquivo1 que foi iniciado em A até A e o Arquivo2 que foi iniciado em A até Azg conforme ilustracao a seguir Temos ainda um terceiro arquivo com valores de B até Bzg onde foi armazenado todos os registros do arquivo original ja em ordem ou seja foi realizado uma intercalacdo entre 0 Arquivol e 0 Arquivo2 dando origem a uma unica série ordenada como mostra a figura abaixo A A A A A A A Ay A Axo 14 22 18 32 17 20 38 26 19 31 A A A A Arquivol 14 22 18 32 eee eee ee ee eee Arquvo2 17 20 38 26 19 31 B B B B B B B B B B 14 17 18 19 20 22 26 31 32 38 Figura 1 Processo de intercalado de dois caminhos httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 928 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento PraCegoVer A Figura mostra 4 tabelas A primeira tabela possui 2 linhas e 10 colunas Na primeira linha da esquerda para a direita tem os valores Al A2 A3 A4 A5 A6 A7 A8 A9 Na segunda linha da esquerda para a direita temos os valores 14 22 18 32 17 20 38 26 19 31 A segunda tabela possui 2 linhas e 4 colunas Na primeira linha da esquerda para a direita tem os valores A1 A2 A3 A4 Na segunda linha da esquerda para a direta tem os seguintes valores 14 22 18 32 Do lado esquerda dessa tabela tem uma seta apontando para ela com o texto Arquivo1 A terceira tabela possui 2 linhas e 6 colunas Na primeira linha da esquerda para a direita tem os valores A5 A6 A7 A8 A9 A10 Na segunda linha da esquerda para a direita tem os valores 17 20 38 26 19 31 Do lado esquerdo dessa tabela tem uma seta apontando para ela com 0 texto Arquivo2 A quarta tabela possui 2 linhas e 10 colunas Na primeira linha da esquerda para a direita tem os valores B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Na segunda linha da esquerda para a direita tem os valores 14 17 18 19 20 22 26 31 32 38 VAMOS PRATICAR e Imagine um banco de dados contendo dez milh6es de registros cada um bytes de comprimento Forneca uma estimativa de quanto tempo leva classificar o banco de dados em uma estacao de trabalho tipica eee eee e eee e eee e eee e ener ee eee eee eee Observe agora o pseudocddigo adaptado de Viana 2015 do método Merge2 descrito anteriormente PROCEDIMENTO DE 2 CAMINHOS A B c d ENTRADA INTEIROS x y Registro H com duas fontes a intercalar SAIDA Registro Z com uma unica série ordenada JA 1c Primeira fonte ordenada A c1d Segunda fonte ordenada J B 1d Fonte ordenadaintercalada Varidveis auxiliares J K 1d Vetor de inteiros httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1028 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento J ij k ini fim ponteiroscontadores i k1 jctl ENQUANTO ic AND jd SE Bi Bj Bk Ai itt SENAO Bk Aj jtt SE ic ini j fimd SENAO ini i fimc Copiar o restante da fonte para a fonte resultado PARA iini ATE fim BkAi k FIMPARA FIMENQUANTO Retorna Aprendemos nesta subsedo como se procede o funcionamento das fases de intercalacdo de dois caminhos também chamado de Merge2 na seguinte subseao abordaremos detalhes da intercalado de trés caminhos também conhecido como Merge3 332 Intercalado de trés caminhos A intercalacao de trés caminhos também conhecida como Merge3 é 0 método responsavel por intercalar trés fontes Bem semelhante ao método Merge2 0 Merge3 segue 0 mesmo principio e o mesmo raciocinio do processo de intercalagado de dois caminhos o que os diferencia é que um utiliza dois caminhos ou seja duas fontes e o outro trés arquivos para fazer a intercalagado Arquivol Arquivo2 e Arquivo3 e um arquivo para fazer a ordenacao desses trés arquivos Arquivok Uma outra caracteristica do processo de intercalacdo de trés caminhos é que ele comeca utilizando o procedimento de trés caminhos ou seja digamos que temos trés arquivos para serem comparados e ordenados pegamos o menor valor e armazenamos no valor resultado em determinado momento um desses trés arquivos finaliza seu processo de intercalacdo restando dois arquivos entéo o procedimento de ordenaao Merge2 se inicia até que um dos arquivos finalize e termine de ordenar 0 arquivo soluao deixando o arquivo solucdo todo ordenado Um exemplo de estrutura de algoritmo pseudocddigo de intercalacdo de trés caminhos pode ser observado a seguir adaptado do pseudocddigo de Viana 2015 PROCEDIMENTO DE 3 CAMINHOS A B c d E ENTRADA INTEIROS c d E Registro A com trés séries a intercalar httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1128 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento Alc primeira fonte ordenada Ap1d segunda fonte ordenada Ad1E terceira fonte ordenada SAIDA Registro B com uma tnica fonte ordenada B1E fonte ordenadaintercalada Varidveis auxiliares K vetor 1n de inteiros ij k m n ponteiroscontador FUNCAO MENOR X Y Z inteiro ENTRADA X Y Z inteiros SAIDA MENOR retorna 1 se o menor 6X retorna 2 se o menor é Y retorna 3 se o menor éZ Varidveis auxiliares v vetor 13 de inteiros w inteiro v1 X v2 Y v3 Z MENOR 1 w v1 PARA i 2 ATE 3 SE vi w w Vi MENOR i fim para DEVOLVA MENOR FIM MENOR i1k1Ljctil d1 ENQUANTO iscEjsdElsn CASO MENOR Ki Kj Kl 1 Bk Ai iil1 2 Bk Aj jjtl 3 BkAl l11 fim caso kk1 O trecho seguinte define os pardmetros dos dois ultimos arquivos para o MERGEZ2 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1228 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento SE ic mdji nE11 SENAO SE ic mcil1 nE11 SENAO mcil1 ndj1 MERGEZ A B mn fim enquanto RETORNA FIM MERGE3 O algoritmo que faz a intercalagdo de Merge3 identificado também como intercalado de trés caminhos utiliza respectivamente representantes das chaves dos seus registros Ai Bj Al e Bk A seguir daremos inicio a intercalacado de k caminhos 333 Intercalagdo de k caminhos Em computacao os algoritmos de intercalacao de k caminhos ou mesclagem de miltiplas vias séo um tipo especifico de algoritmos de mesclagem de sequéncia que se especializam em receber varias listas classificadas e fundilas em uma Unica lista ordenada Esses algoritmos de mesclagem geralmente se referem a aqueles que recebem um numero de listas classificadas maiores que duas ou trés Mesclagens bidirecionais também sao chamadas de mesclagens binarias Em ordenado externa uma mesclagem de varias vias ou seja k vias permite que os arquivos fora da memoria sejam intercalados em menos passagens do que em uma mesclagem binaria Se houver seis execucées que precisam ser mescladas uma mesclagem binaria precisaria receber trés passes de mesclagem diferente da mesclagem de seis vias Essa reducdo de passes de mesclagem é especialmente importante considerando a grande quantidade de informaées que geralmente estao sendo ordenadas em primeiro lugar permitindo maiores aceleraées e reduzindo a quantidade de acessos 4 memoria mais lenta No geral algoritmos que fazem intercalacdo Mergek também conhecido como intercalado de k caminhos sao implementados de forma bem similar ao Merge3 ou seja os registros sdo intercalados pegando o primeiro registro de cada série e transferindo para a proxima série assim o menor é excluido da série cedendo lugar ao proximo registro até que se tenha a fita ordenada Exemplo para o Merge3 k3 a fundo MENOR selecionaria 0 menor valor entre os trés nimeros e no momento em que é atingido o fim de um dos arquivos deveria ser chamado o procedimento Merge2 para finalizar o processo de intercalaao Aqui conhecemos como se da 0 método de ordenagao externa para k caminhos porém nado é comum a utilizagdo de uma intercalacdo com mais de trés caminhos devido a complexidade deste algoritmo mesmo sabendo que o numero de leituras e gravacées poderia ser reduzido O raciocinio da intercalagdo Mergek é 0 mesmo da intercalagdo Merge2 quebrando o arquivo unico em dois trés ou quatro arquivos quantos valores forem o k e o processo de intercalacdo entre esses arquivos é iniciado ao final temos um Unico arquivo ordenado A seguir conheceremos a comparaao entre distribui6es equilibradas httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1328 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento 34 Comparagao entre distribuicgoes equilibradas Para exemplificar a comparacdo entre distribuigdes equilibradas vamos adaptar o caso de Viana 2015 Suponhamos que desejamos classificar 9000 registros porém a memoria que temos disponivel para a ordenaao interna é pequena e nao suporta mais de 1000 registros a cada vez ou seja sera realizada a cada 1000 registros lidos uma classificagdo estes serdo ordenados de formas correspondentes e armazenados em uma fonte auxiliar de modo ordenado e em sequéncia arquivo todo sequencial de modo que os numeros de registros sejam multiplos de 1000 caso contrario a ultima série ficara incompleta 0 que nao é dificil para o processo de intercalacdo do tipo Mergek ja visto nas sec6es anteriores O numero de arquivos de trabalho assim como a distribuido das séries nestes arquivos depende do numero k de fontes a serem intercalados VIANA 2015 Podemos ver esse processo na figura a seguir na qual para k2 serao necessarios cinco arquivos de trabalho ou seja precisardo cinco arquivos para conseguir fazer esse processo de classificagdo e ordenacdo Poderemos observar na mesma figura um arquivo principal com 9000 registros classificados de 1 d 1000 e de 1001 a 2000 e assim sucessivamente até alcancar os 9000 registros Em um primeiro passo é realizado um processo de intercalacdo armazenado nos arquivos auxiliares Arquivol e Arquivo2 Pegase o primeiro valor na primeira classe de 1 até 1000 e armazenase no Arquivo1 pega o segundo intervalo ou segunda classe que é de 1001 até 2000 e armazena no Arquivo2 e o processo é feito até chegar ao final do arquivo principal por ultimo teremos A registros que vai de 8001 a 9000 que foi armazenado no Arquivo1 Notase também que é feita uma intercalado no Arquivol e no Arquivo2 Para concluirmos esse processo de ordenacdo é preciso mais trés arquivos que seguem como mostrado nas etapas do processo Dando continuidade as etapas descritas na figura comease o processo de classificacao dando inicio a partir da coluna ou seja pega o resultado da primeira coluna e armazena no primeiro intervalo do Arquivo3 pega a segunda coluna e armazena no Arquivo4 a terceira coluna no Arquivo3 a quarta coluna no Arquivo4 e assim por diante realizando o processo de intercalado e resultando no ultimo arquivo contendo todo o intervalo A1 até A9000 ja ordenado entao esse é o processo de comparacao entre distribuiées equilibradas Primeiro realizase uma divisdo de mil em mil em seguida unificase as colunas armazenando os registros no proximo arquivo dando continuidade ao processo até que se finalize toda a ordenacao gerando o ultimo arquivo com todas as séries 1 até 9000 classificadas httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1428 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento A11000 A10012000 A20013000 A30014000 A40015000 AS50016000 A60017000 A70018000 A80019000 ARQUIVO Ajl1000 A20013000 A40015000 A60017000 A80019000 ARQUIVO2 A K A30014000 AS50016000 A70018000 ARQUIVO3 A12000 A40016000A80019000 ARQUIVO4 A20014000 A60018000 ARQUIVO A14000 A80019000 ARQUIVO2 A40018000 ARQUIVO3 A18000 ARQUIVO A19000 ARQUIVO4 A80019000 Figura 2 Processo de classificacdo e ordenacao PraCegoVer A figura mostra 6 tabelas para simular o processo de classificagdo e ordenacao A primeira tabela possui uma linha e 9 colunas Os valores armazenados da esquerda para a direita respectivamente sao A11000 A10012000 A20013000 A30014000 A400015000 A50016000 A60017000 A70018000 A80019000 A segunda tabela possui duas linhas e 6 colunas A primeira linha tem os valores Arquivo A11000 A20013000 A40015000 A60017000 A80019000 A segunda linha tem os valores Arquivo2 A10012000 A30014000 A50016000 A70018000 A terceira tabela possui duas linhas e 3 colunas A primeira linha tem os valores Arquivo3 A12000 A40016000 A80019000 A segunda coluna possui os valores Arquivo4 A20014000 A60018000 Existem algumas setas apontando da segunda tabela para a terceira tabela A segunda e a terceira coluna da segunda tabela possuem setas apontando para a segunda coluna da terceira tabela A terceira e a quarta coluna da segunda tabela estao apontando para a terceira coluna da terceira tabela A quinta coluna da segunda tabela esta apontando para a quarta coluna da terceira tabela A quarta tabela possui duas linhas 3 colunas A primeira linha tem os valores Arquivo1 A14000 A80019000 A segunda linha tem os valores Arquivo2 A40018000 Existem algumas setas apontando da terceira tabela para a quarta tabela A segunda e terceira coluna da terceira tabela possuem setas apontando para a primeira coluna da quarta tabela A quarta coluna da terceira tabela possui uma seta apontando para a terceira coluna da quarta tabela A quinta tabela possui duas linhas 2 colunas A primeira tabela possui os valores Arquivo3 A18000 A segunda httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1528 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento linha possui os valores Arquivo4 80019000 Existe uma seta apontando da quarta tabela para a quinta tabela A segunda coluna da quarta tabela possui uma seta apontando para a segunda coluna da quinta tabela Por fim a sexta tabela possui uma linha e duas colunas A primeira coluna possui o valor arquivo e a segunda coluna possui 0 valor A19000 Existe uma seta apontando da quinta tabela para a sexta tabela VAMOS PRATICAR e Classifique 15000 registros B1 até B15000 usando o processo de ordenz vocé acabou de ver adote k2 eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee eee eee Nesta secdo foi possivel aprender sobre comparaao entre distribuiao equilibrada e como 0 método é aplicado com os dados simulando o k2 Nas sedes seguintes faremos uma simulacdo para k 23 e4e veremos os t6picos da classificagéo dos métodos de ordenacao externa ege 35 Classificagao dos metodos de ordenagao externa Quando falamos de ordenaao externa estamos falando de métodos para organizar arquivos que nao cabem na memoria tradicional do computador atualmente 0 método mais importante para classificagdo externa é o método por intercalacao VIANA 2015 Alguns métodos de ordenacdo externa sao os que vocé podera ver clicando nos fcones a seguir Intercalacao Balanceada de varios caminhos Implementagcdo por meio de Selecao por substituiao httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1628 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento Intercalaao Polifasica Quicksort externo também conhecido como Heapsort Definimos a intercalagao balanceada de varios caminhos como a intercalaao de blocos na qual é realizada uma varredura na memoria externa dividindoa em blocos compativeis com a memoria interna Os blocos sao intercalados realizando leituras sobre este arquivo criando blocos classificados cada vez maiores Ja a implementacdo por meio de Selecdo por substituicdo é uma implementacdo muito parecida com a intercalacado balanceada porém sofre um acréscimo da abordagem de filas por prioridade implementadas por um heap ZIVIANI 2012 VOCE SABIA e Na ciéncia da computacao uma fila de prioridade é um tipo de dados abstrato baseado em uma fila regular ou estrutura de dados de pilha porém cada elemento tem uma prioridade associada a ele J4 um heap é uma estrutura de dados baseada em Arvore na qual todos os nos da arvore estado em uma ordem especifica Em uma pilha o elemento de prioridade mais alta ou mais baixa é sempre armazenado na raiz dai o nome pilha Um heap nao é uma estrutura classificada e pode ser considerado como parcialmente ordenado A intercalacao polifasica excluf a necessidade de cépias adicionais pois distribui as fitas ordenadas por meio de uma selecdo desigual Convido vocé a ver com mais detalhes a classificagado de cada um desses métodos de ordenacao externa nas sedes seguintes e e ww e e e e 36 Classificagao Equilibrada de dois caminhos Um exemplo de classificagado equilibrada de dois caminhos pode ser visto na Figura 3 onde é adotado um limite de classificacao interna de trés registros entdo a intercalacdo sera realizada de trés em trés lembrando que na classificagao equilibrada de dois caminhos ou seja para k2 sera preciso quatro arquivos para realizar a ordenacado chamados de Arquivo1 Arquivo2 Arquivo3 e Arquivo4 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade3ebookindexhtml 1728 21082023 1627 Pesquisa Ordenagao e Técnicas de Armazenamento RI 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 6 26 15 EVEDES 10 19 RNIENEQ 2 12 5 BENE 2 Arquivol 6 eB A0 7 3 Arquivo2 D rg Arquivo3 3615232830 5910121318 Arquivo4 2810192434 624 Arquivol 23681015192324283034 Arquivo2 5691012131824 Arquivo3 235668910101213151819232424283034 Arquivo4 Figura 3 Classificagao equilibrada de 2 caminhos PraCegoVer Na mostra um processo de classificagdo equilibrada de 2 caminhos Primeiramente é mostrado uma tabela de duas linhas e 20 colunas Na primeira linha denominada RI da esquerda para a direita temos os valores 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Na segunda linha denominada KI da esquerda para a direita temos os valores 6 28 15 3 30 23 34 10 19 8 2 24 12 18 5 13 10 9 6 24 Em seguida é mostrado uma tabela de 2 linhas e 11 colunas Na primeira linha denominada Arquivo1 da esquerda para a direita temos os valores 6 15 28 10 19 39 5 12 18 6 24 Na segunda linha denominada Arquivo2 da esquerda para a direita temos os valores 3 23 30 2 8 24 9 10 13 Logo apés é mostrado uma tabela de 2 linhas e 2 colunas Na primeira linha denominada Arquivo3 da esquerda para a direita temos os valores 3615232850 5910121318 Na segunda linha denominada Arquivo4 da esquerda para a direita temos os valores 2810192434 624 Logo apés é mostrado uma tabela de 2 linhas e1 coluna Na primeira linha denominada Arquivo1 da esquerda para a direita temos os valores 23681015192324283034 Na segunda linha denominada Arquivo2 da esquerda para a direita temos os valores 5691012131824 Por fim é mostrado uma tabela de 2 linhas e1 coluna Na primeira linha denominada Arquivo3 da esquerda para a direita temos os valores 235668910101213151819232424283034 Na segunda linha denominada Arquivo4 nado tem nenhum valor httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1828 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento O primeiro passo é pegar os trés primeiros valores e trazer para o primeiro arquivo Arquivo1 ordenando 6 28 e 15 os préximos trés 3 30 e 23 serdo levados para 0 préximo arquivo Arquivo2 dando continuidade ao processo de intercalacdo de trés em trés Ao final sobraram 6 e 24 Como mencionado anteriormente os ultimos valores nao precisam ter o valor completo da taxa interna de registro apds realizado o primeiro passo com os dois arquivos Arquivol e Arquivo2 devese continuar realizando o processo de intercalacdo nesse caso 0 préximo passo sera pegar a primeira coluna que se refere aos dois arquivos e realizar a classificaao ou Seja armazenar no Arquivo3 Entdo teremos 3 6 15 23 28 e 30 ou seja os valores que estdo ordenados no Arquivo3 deve ser realizado 0 mesmo procedimento para os demais valores até que de fato cada fonte tenha um unico bloco todo ordenado Nesta sessdo aprendemos sobre classificacdo equilibrada de dois caminhos com um exemplo classico de Merge2 de ordenacao externa a seguir veremos o processo de classificacao equilibrada usando trés caminhos 37 Classificagao Equilibrada de trés caminhos Para a classificagdo equilibrada com k3 podemos usar também quatro arquivos de trabalho de modo que no inicio da fase de classificacdo seja possivel criar fitas de comprimento 1000 e as distribuir também em dois arquivos a Unica coisa que diferencia das demais é que em determinado momento da segunda fase usando a classificacdo de dois caminhos um dos arquivos fica vazio sendo utilizada a classificado de trés caminhos Observe na figura abaixo como ficaria essa classificaao httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 1928 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Fase 1 ordenacao interna e gravacao inicial Argi Al11000 A20013000 A40015000 A60017000 Arg2 A10012000 A30014000 A50016000 Arq3 Arq4 Fase 2 uso do Merge2 Ponteiro Arql A60017000 Arq2 Arg3 Al2000 A40016000 Arg4 A20014000 Fase 3 uso do Merge3 Fase 4 uso do Merge2 Arql Arql A17000 Arq2 A15000 Arq2 Arq3 A40016000 Arq3 Arq4 Arq4 a Figura 4 Processo de classificacao Equilibrada de trés caminhos Fonte Elaborada pela autora baseada em VIANA 2015 PraCegoVer A figura mostra um processo de classificacdo de trés caminhos De modo geral a figura mostra trés tabelas com uma frase acima delas Acima da primeira tabela tem a frase Fase 1 ordenacdo interna e gravaao inicial A primeira tabela tem 4 linhas e 4 colunas Na primeira linha coluna 1 A11000 coluna 2 A20013000 coluna 3 A40015000 coluna 4 A60017000 Na segunda linha coluna 1 A10012000 coluna 2 A30014000 coluna 3 A50016000 Em seguida acima da segunda tabela temos a seguinte frase Fase 2 uso do Merge2 A segunda tabela tem 4 linhas 3 4 colunas Na primeira linha coluna 4 A60017000 Na terceira linha coluna 1 A12000 na coluna 2 A40016000 Na quarta coluna linha 1 A20014000 Posteriormente acima da terceira tabela temos a frase Fase 4 uso do Merge3 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2028 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento A terceira tabela tem 4 linhas e 2 colunas Na segunda linha coluna 1 A15000 Na terceira linha coluna 2 A40016000 Por fim ao lado da terceira tabela tem a quarta tabela Acima desta tem a frase Fase 4 uso do Merge2 A tabela 4 possui 4 linhas e 1 coluna Na primeira linha coluna 1 A17000 E possivel notar que a fita A15000 é a saida no Merge3 com entrada obtida a partir de A60017000 A12000 e A20014000 praticamente nesta ordem A fase que finaliza diz respeito ao Merge2 Observe que para todas as fases deste tipo de classificagao pode ser usado 0 Merge3 dado que de acordo com sua descriao quando um dos arquivos esta com 0 ponteiro no final 0 Merge2 é acionado eee eee eee renee reer e reer eeeeeeeee eee eee VAMOS PRATICAR e Classifique 15000 registros B1 até B15000 usando o processo de ordenz vocé acabou de ver adote k3 ee A seguir veremos detalhes da ordenacao equilibrada de multiplos caminhos ege ope e e 38 Classificagao Equilibrada de multiplos caminhos De acordo com Viana 2015 quando tratamos de classificacdo equilibrada de varios caminhos também conhecida como classificacao equilibrada Mergek levamos em consideracao que para k4 é necessario k1 arquivos de trabalho A fase que da inicio a essa classificacdo cria fitas de tamanhos fixos e as insere alternadamente em k arquivos ou seja Arq1 e Arq2 deixando a ordem k1 livre A préxima fase utiliza o procedimento de intercalacao de varios caminhos 0 Mergek Veremos na figura abaixo um exemplo de classificagao equilibrada de Mergek httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2128 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Fase 1 Classificagao interna e distribuigdo alternada das fitas Arqi A11000 A40015000 Arq2 A10012000 A50016000 Arq3 A20013000 A60017000 Arg4 A30014000 Arq5 Fase 2 Merge4 Arql A40015000 Arq2 A50016000 Arq3 A60017000 Arq4 Arg5 A14000 Fase 3 Merge4 Arg4 A17000 Figura 5 Processo de classificacao Equilibrada de multiplos caminhos Fonte Elaborada pela autora baseada em VIANA 2015 PraCegoVer A figura mostra o processo de classificagdo equilibrada de multiplos caminhos De modo geral a figura mostra trés tabelas cada uma com uma frase acima delas Acima da primeira tabela tem a frase Fase 1 Classificado interna e distribuido alternada das fitas A primeira tabela possui 5 linhas e 2 duas colunas Na primeira linha chamada Arq1 temos a coluna 1 A1 1000 coluna 2 A40015000 Na segunda linha chamada Arq2 temos a coluna 1 A10012000 coluna 2 A50016000 Na terceira linha chamada Arq3 temos a coluna 1 A20013000 coluna 2 A6001 7000 Na terceira linha chamada Arq4 temos a coluna 1 A30014000 Acima da segunda tabela tem a frase Fase 2 Merge 4 A segunda tabela possui 5 linhas e 2 colunas Na primeira linha chamada Arq1 temos a coluna 2 A4001 5000 Na segunda linha chamada Arq2 temos a coluna 2 A50016000 Na terceira linha chamada Arq3 temos a coluna 2 A60017000 Na quinta linha chamada Argq5 temos a coluna A14000 Acima da terceira tabela tem a frase Fase 3 Merge4 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2228 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento A terceira tabela possui uma linha e uma coluna Na primeira linha chamada Arq4 temos a coluna 1 A1 7000 O processo de classificagdo equilibrada de multiplos consiste em fundir algoritmos e ocorre geralmente na segunda fase usando algoritmos de ordenado externa da mesma forma como é realizado com o Mergesort Uma jundo com varios pontos permite que os arquivos externos sejam incorporados em menos tempo do que em uma mesclagem binaria Esta redudo de passagem é especialmente importante considerando a enorme quantidade de informacdo que é usualmente classificada em primeiro lugar permitindo maiores aceleraées e ao mesmo tempo reduzindo a quantidade de acessos 4 memoria mais lenta Agora que vocé reconhece a classificacdo equilibrada de multiplos caminhos ja esta preparado para compreender o conceito de intercalacdo polifasica definida como a distribuicdo dos blocos ordenados por meio de uma seleao desigual assunto do topico a seguir eg ie 39 Intercalacao polifasica Na intercalacao polifasica os blocos ordenados sao distribuidos de forma desequilibrada entre as fitas disponiveis uma fita é deixada de forma livre e logo apos a intercalacao de blocos ordenados é executada até que uma das fitas esvazie Neste ponto uma das fitas de safda troca de papel com a fita de entrada ZIVIANE 2012 Ainda conforme Ziviane 2012 a intercalacao é realizada em diversas fases e essas fases ndo envolvem todos os blocos e nenhuma c6pia direta entre fitas é realizada De acordo com Viana 2015 0 objetivo deste tipo de intercalacdo é distribuir as séries iniciais de forma desequilibradas de modo que menos passos sejam necessarios para a classificacdo total Podemos observar na figura abaixo alguns passos do processo de uma ordenaao externa usando intercalaao polifasica Navegue na interacdo a seguir para entender cada passo da figura abaixo No passo um os blocos sao ordenados obtidos por meio de selecao por substituido a partir da frase INTERCALACAOBALANCEADA No passo dois intercalase para fita trés deixando a fita dois livre No passo trés intercalase a fita um e a fita trés na fita dois deixando a fita um livre No passo quatro intercalase para fita trés deixando a fita dois livre httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2328 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento LN C A O S A DA Gono Doon 1 DOOGEO DOGREOIRE SRECRSS 2 ND ogo Eng Onn 3 anh fo OO BE OD OG 4 Figura 6 Processo de ordenaao externa usando Intercalaao Polifasica PraCegoVer A figura mostra o processo de ordenaao externa usando intercalaao polifasica De modo geral a figura mostra um vetor e quatro passos para executar a ordenado O vetor possui os seguintes valores da esquerda para a direita I N T R E C A L A C A O B L A A N C E A D A Acima deste vetor tem a frase INTERCALACAOBALANCEADA No primeiro passo mostrase duas fitas A primeira fita mostra trés partes do vetor As partes sao respectivamente I N T R A C E L A A B C L O A segunda fita mostra duas partes do vetor As partes sao respectivamente A A C E N A A D httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2428 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento No segundo passo mostrase trés fitas A primeira fita mostra uma parte do vetor Essa parte possui os valores A A B C L O A segunda fita nado possui nenhuma parte do vetor A terceira fita possui duas partes do vetor As partes sao respectivamente A A C E I N N R T A A A C D E L No terceiro passo mostrase trés fitas A primeira fita nado possui nenhuma parte do vetor A segunda fita possui uma parte do vetor Essa parte possui os valores A A A A B C C E I L MN O R T A terceira fita possui uma parte do vetor Essa parte possui os valores A A A C D E L Por fim o quarto passo possui uma fita com o vetor inteiro Os valores do vetor sao A A A A A A A B C C C D E E I L L NN O R T Os blocos sao distribuidos entre unidades de forma desigual na intercalaao polifasica deixando apenas uma unidade reservada para guardar os blocos restantes das intercalagées Em cada fase uma unidade se esvazia e assim sucessivamente até que a intercalaao seja finalizada A intercalacdo é realizada em muitas fases estas ndo envolvem todos os blocos sendo ligeiramente melhor do que a intercalado balanceada O algoritmo Quicksort de ordenacao rapida introduzido em 1960 por Charles Antony Richard Hoare pertence a classe dos chamados algoritmos de divisdo e conquista semelhantes a classificacdo de mesclagem E popular por nao ser dificil de implementar além de ser uma boa classificaao de uso geral ja que funciona em varias situacdes e consome menos recursos do que qualquer outro algoritmo de classificaao eee eeeeeeeeeeeeeeeeeeeeeeeeeeeee eee eee VOCE QUER VER e O Quicksort 6 um algoritmo que foi desenvolvido em 1960 por Charles A R Hoare conhecido também como Tony Hoare é o método de classificacdo interna com maior rapidez para uma ampla variedade de situac6es Ele ganhou o Prémio Turing Association for Computing Machinery de 1980 CORMEM 2002 Para conhecer mais sobre a execucdo desse algoritmo clique aqui httpsyoutubeywWBy6J5gz8 httpsyoutubeywWBy6J5gz8 eee eeeeeeeeeeeeeeeeeeeee ee eee neers Ele funciona particionando um arquivo em duas partes e em seguida classificando as partes independentemente Os elementos sao divididos em duas submatrizes repetidamente até que apenas um elemento seja deixado A classificacdo de mesclagem usa armazenamento adicional para classificar a matriz auxiliar ou seja usando trés matrizes duas sdo usadas para armazenar cada metade e a terceira é usada para armazenar a lista final classificada mesclando outras duas cada matriz é classificada recursivamente Por fim todas as submatrizes sao mescladas para tornar 0 tamanho do elemento da matriz httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2528 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Um exemplo pode ser observado na figura abaixo Etapa 1 Escolha um pivé 5 3 9 T 2 4 1 6 Etapa 2 Valores menores vao para a esquerda valores iguais ou maiores vao para a direita 3 2 4 1 5 5 8 7 6 Etapa 3 Repita a etapa 1 com as duas sublistas G 3 2 4 bs 5 5 8 7 Figura 7 Processo de ordenaao usando o Algoritmo Quicksort Fonte Elaborada pela autora baseada em CORMEM 2002 PraCegoVer A figura mostra 0 processo de ordenacado usando o algoritmo Quicksort Inicialmente mostra uma frase dizendo Etapa 1 Escolha um pivo Em seguida é mostrado 10 nimeros que possuem os valores da esquerda para a direita 5 3 9 8 7 2 4 1 6 5 Sendo que o ultimo nimero com valor 3 esta em destaque Depois disso é mostrado uma outra frase que diz Etapa 2 Valores menores vao para a esquerda valores iguais ou maiores vao para a direita Em seguida 6 mostrado os mesmos 10 nimeros em uma sequéncia diferente Da esquerda para direita temos 3 2 4 1 5 5 9 8 7 6 Sendo que o numero 5 esta em destaque Por fim é mostrado uma outra frase que diz Etapa 3 Repita a etapa 1 com os duas sublistas Em seguida é mostrado os mesmos 10 nimeros em uma sequéncia diferente Da esquerda para a direita temos 3 2 4 1 5 5 9 8 7 6 Sendo que o numero 1 e 6 estao em destaque Temos como elemento o P Piv6 e a reorganizacdo é feita em trés subblocos nos quais os elementos iguais ou menores a P sdo agrupados a esquerda e os elementos P no bloco do meio Aqueles maiores ou igual a P sAo agrupados no bloco da direta O processo é repetido recursivamente para os subblocos esquerdo e direito O Quicksort acaba sendo o algoritmo de classificagdo mais rapido na pratica e muito eficiente para classificar os arquivos de dados Sintese Concluimos a unidade introdutoria relativa 4 ordenacdo externa e processos de intercalagao dos arquivos Agora que vocé ja conhece 0 processo de ordenaao externa e sabe que ela é empregada quando a quantidade de dados processada é grande e nao cabe na memoria interna do computador Também vimos os principais métodos de ordenaao com foco no conceito e funcionamento de cada um deles Além disso percebemos que caso o arquivo siga uma sequéncia é necessario empregar outros métodos baseados em processos de divisdo e medida conhecido como intercalacao de arquivos httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2628 21082023 1628 Pesquisa Ordenagao e Técnicas de Armazenamento Nesta unidade vocé teve a oportunidade de reconhecer os mecanismos de ordenagao externa conhecer os processos de intercalacao dos arquivos e verificar a eficiéncia entre as diversas distribuicoes Clique para baixar o contetido deste tema Bibliografia AGUILAR L J Fundamentos de Programagao Algoritmos estruturas de dados e objetos 3 ed Porto Alegre AMGH 2008 ARBEX W et al Intercalagdo e Ordenaao de arquivos por algoritmos de fusdo CES revista Juiz de Fora v 23 p 227 237 2009 Disponivel em httpsseercesjfbrindexphpcesRevistaarticleviewFile706559httpsseercesjfbrindexphpcesRev istaarticleviewFile706559 httpsseercesjfbrindexphpcesRevistaarticleviewFile706559 Acesso em 10102019 CORMEN T H LEISERSON C E RIVEST R L STEIN C Introduction to algorithmsstring matching Massachusetts MIT Press 2002 DASGUPTA S PAPADIMITRIOU C VAZIRANI U Algoritmos Porto Alegre AMGH 2011 DEITEL P DEITEL H Java como programar 8 ed Sdo Paulo Pearson 2015 DOBRUSHKIN V A Métodos para Analise de Algoritmos Rio de Janeiro LTC 2012 GUIMARAES A M LAGES N A C Algoritmos e estruturas de dados Rio de Janeiro LTC 2015 KNUTH D E Sorting and Searching The Art of Computer Programming 3 vol Massachussets AddisonWesley 1973 MAHMOUD H M A Distribution Theory New Jersey Wiley Interscience 2000 QUICKSORT WITH HUNGARIAN FOLK DANCE Criado por Sapientia University Tirgu Mures Marosvasarhely Romania Dirigido por Katai Zoltan and Toth Laszl6 654 min Disponivel em httpswwwyoutubecomwatchvywWBy 6J5gz8featureyoutubehttpswwwyoutubecomwatch VywWBy65gz8featureyoutube httpswwwyoutubecomwatch VywWBy65gz8featureyoutube Acesso em 08102019 SHELLSORT WITH ROMANIAN FOLK DANCE Criado por Sapientia University Tirgu Mures Marosvasarhely Romania Dirigido por Katai Zoltan and Toth Laszl6 Disponivel em httpswwwyoutubecomwatchvCm PA7zE8mx0httpswwwyoutubecom watchvCmPA7zE8mx0 httpswwwyoutubecomwatchvCmPA7zZE8mx0 Acesso em 08102019 SINGH B NAPS T L Introduction to Data Structure Minnesota West Publishing Co 1985 TAMASSIA R GOODRICH M T Estruturas de Dados e Algoritmos em Java Porto Alegre Grupo A 2011 VIANA G V R CINTRA G F NOBRE R H Pesquisa e ordenagao de Dados 2 ed Fortaleza EdeuECE 2015 ZIVIANI N Projeto de Algoritmos com implementagdes em JAVA e C Sdo Paulo Cengage Learning Editores 2012 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2728 21082023 1628 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade3ebookindexhtml 2828