Trabalho métodos de ordenação

  • Published on
    17-Dec-2014

  • View
    8.800

  • Download
    1

Embed Size (px)

DESCRIPTION

 

Transcript

<ul><li> 1. UNIVERSIDADE DO CONTESTADO UNC/CONCRDIACurso: Sistemas de Informao 1/2012 3 Fase 20/06/2012 Disciplina: Estruturas de Dados Professor: Maximiliano Zambonatto Pezzin Acadmica: Daiana Paula de vilaIntroduoEm vrios momentos do dia a dia, o homem depara-se com a necessidade deconsultar dados ordenados. Como exemplo, pode-se citar uma lista telefnica.Imagine como seria consultar o telefone de uma pessoa se os nomes noestivessem classificados em ordem alfabtica. Por isso uma das atividades maisutilizada na computao a ordenao.As ordens mais utilizadas so as nmericas e as lexicogrficas.Existem diversos algoritmos para ordenao interna. No presente trabalho serapresentada a implementao e os testes de seis destes mtodos. Bubble Sort Insertion Sort Selection Sort Shell Sort Quick Sort Heap Sort Merge SortOs testes foram realizados com vetores de nmeros inteiros de tamanho 25 e tipos(ordenados em ordem crescente e decrescente, aleatrios e parcialmenteordenados com apenas 20% dos elementos fora da ordem).Como medida para a comparao entre os mtodos foi colhido durante cadateste:1. Nmero de comparaes entre chaves do vetor;2. Nmero de movimentaes;3. Contagem do tempo gasto durante a execuo do algoritmo;</li></ul> <p> 2. Mtodos de OrdenaoOrdenar corresponde ao processo de rearranjar um conjunto de objetos em ordemascendente ou descendente. O objetivo principal da ordenao facilitar arecuperao posterior de itens do conjunto ordenado.Os mtodos de ordenao so classificados em dois grandes grupos: ordenaointerna e externa.1. Ordenao Interna: So os mtodos que no necessitam de uma memriasecundria para o processo, a ordenao feita na memria principal docomputador;2. Ordenao Externa: Quando o arquivo a ser ordenado no cabe na memriaprincipal e, por isso, tem de ser armazenado em fita ou disco.A principal diferena entre os dois grupos que no mtodo de ordenao internaqualquer registro pode ser acessado diretamente, enquanto no mtodo externo necessrio fazer o acesso em blocos.Bubble Sort o mtodo mais simples em termos de implementao, porm o menos eficiente.A idia principal do algoritmo percorrer o vetor n - 1 vezes, a cada passagemfazendo flutuar para o inicio o menor elemento da sequncia. Seu uso no recomendado para vetores com muitos elementos. 3. Ilustrao do funcionamento do algoritmo Bubble Sort.ImplementaoO algoritmo procede da seguinte forma:1. Zera os valores das vriveis de medio atravs do mtodo ClearAll();2. Inicia a contagem de tempo com a funo start();3. Percorre o vetor, trazendo para o incio o menor elemento encontrado;4. A cada comparao incrementa a varivel mComparations e a cada movimen-tao incrementa a varivel mMoviments; 4. 5. Pausa a contagem de tempo e calcula o tempo gasto armazenando o valor navarivel mTime;Uma maneira mais eciente de implementao do BubbleSort consiste em parar oprocesso logo que se detecte que, ao longo de uma passagem no foram efetuadastrocas de chaves.Anlise do algoritmoO Bubble Sort um mtodo de simples implementao, porm a sua eficincia a menor entre os mtodos de ordenao interna]. Admite contudo vriosmelhoramentos e tambm uma boa base para a construo de mtodos maiselaboradosVantagens- Fcil Implementao;- Algoritmo Estvel;Desvantagens- O fato de o arquivo j estar ordenado no ajuda em nada [7];- Ordem de complexidade quadrtica;Insertion SortInsertion Sort um algoritmo elementar de ordenao. eficiente quando aplicado um vetor com poucos elementos. Em cada passo, a partir de i = 2, o i-simo itemda sequncia fonte apanhado e transferido para a sequncia destino, sendoinserido no seu lugar apropriado. 5. Ilustrao do funcionamento do algoritmo Insertion Sort.ImplementaoO algoritmo procede da seguinte maneira:1. Zera os valores das variveis de medio atravs do mtodo ClearAll();2. Inicia a contagem de tempo com a funo start();3. O primeiro lao de repetio tem a funo de controlar o tamanho da sequnciaanalisada;4. O segundo lao responsvel de colocar o novo elemento da sequncia, emrelao anterior, no lugar apropriado;5. A cada comparao incrementa a varivel mComparations e a cadamovimentao incrementa a varivel mMoviments;6. Pausa a contagem de tempo e calcula o tempo gasto armazenando o valor navarivel mTime; 6. Uma soluo melhor, mas que no ser utilizada durante os testes, a utilizao deum registro sentinela: na posio zero do vetor coloca-se o prprio registro emconsiderao. Assim evitando duas comparaes no anel mais interno do algoritmo,porm seria necessrio uma implementao do vetor a partir do ndice 1, e no de 0como proposto neste trabalho.Anlise do algoritmoO InsertSort tambm um mtodo de simples implementao, e tem acomplexidade igual ao BubbleSort . Pode ser aprimorado com o uso de sentinela eoutras tcnicas de algoritmos. o melhor mtodo para se utilizar quando osarquivos j esto quase ordenados.Vantagens- Fcil Implementao- Algoritmo Estvel- O vetor j ordenado favorece a ordenaoDesvantagens- Nmero grande de movimentaes- Ordem de complexidade quadrtica- Ineficiente quando o vetor est ordenado inversamente;Selection SortTem como principio de funcionamento selecionar o menor item do vetor e a seguirtroc-lo pela primeira posio do vetor. Isto ocorre para os n-1 elementos restantes,depois com os n-2 itens, at que reste apenas um elemento. A principal diferenadestes mtodos em relao aos dois j apresentados que ele realiza apenas umatroca por iterao. 7. Ilustrao do funcionamento do algoritmo Selection Sort.ImplementaoA colocao do item no seu lugar correto na sequncia ordenada, realizadatrocando o item de menor valor pela primeira posio do vetor.O algoritmo procede da seguinte forma:1. Zera os valores das variveis de medio atravs do mtodo ClearAll();2. Inicia a contagem de tempo com a funo start();3. O primeiro lao determina a dimenso de busca do menor elemento;4. O segundo lao responsvel por realizar a busca pelo menor elemento; 8. 5. Feito a busca realizada a troca do menor elemento pelo primeiro elemento;6. Aps a troca o processo realizado novamente para os n-i itens restantes;7. A cada comparao incrementa a varivel mComparations e a cada movimen-tao incrementa a varivel mMoviments;8. Pausa a contagem de tempo e calcula o tempo gasto armazenando o valor navarivel mTime;Anlise do algoritmoO Selection Sort um mtodo muito simples. Alm disso, o algoritmo de seleoapresenta um comportamento espetacular quanto ao nmero de movimentos deregistros, cujo tempo de execuo linear, esta particularidade dificilmenteencontrada em outros algoritmos de ordenao. o algoritmo ideal para arquivoscom registros muito grandes.Vantagens- Fcil Implementao- Pequeno nmero de movimentaes- Interessante para arquivos pequenosDesvantagens- O fato de o arquivo j estar ordenado no influencia em nada- Ordem de complexidade quadrtica- Algoritmo no estvelShellSortEste algoritmo uma extenso do mtodo Insertion Short proposto por Donald Shellem 1959. O algoritmo de insero troca itens adjacentes quando est procurando oponto de insero na sequncia destino. Se o menor item estiver na posio mais direita no vetor, ento o nmero de comparaes e movimentaes igual a n-1para encontrar o seu ponto de insero. O ShellSort contorna este problema,permitindo trocas de registros distantes um do outro. De maneira geral ele passavrias vezes no vetor dividindo-o em vetores menores, e nestes so aplicados o 9. algoritmo de ordenao por insero tradicional. Dentre os programas de ordenaointerna que tem ordem de complexidade quadrtica,o ShellSort o mais eficiente.Ilustrao do funcionamento do algoritmo ShellSort. 10. ImplementaoO diferencial do ShellSort a diviso em h intervalos que ele realiza paraposteriormente aplicar o mtodo de insero. Vrias sequncias para h tm sidoexperimentadas. Knuth(1973) mostrou experimentalmente que a escolha doincremento para h, mostrada a seguir na Equao 2.7 difcil de ser batida em maisde 20% dos casos em ecincia no tempo de execuo.O algoritmo procede da seguinte forma:1. Zera os valores das variveis de medio atravs do mtodo ClearAll();2. Inicia a contagem de tempo com a funo start();3. O algoritmo usa uma varivel auxiliar denominada distncia de comparao(h);4. O valor de h inicializado com um valor prximo de n=2;5. A troca feita entre elementos que esto distanciados h posies (se estiveremfora de ordem);6. Aps todas as trocas de elementos cuja distancia h, o valor de h deve serreduzido: conforme Equao 2.7;7. O algoritmo repetido at que a distncia de comparao h seja igual a um (h =1);8. Para h = 1 (ultima passada) executado o algoritmo de insero;9. A cada comparao incrementa a varivel mComparations e a cadamovimentao incrementa a varivel mMoviments;10. Pausa a contagem de tempo e calcula o tempo gasto armazenando o valor navarivel mTime;Anlise do algoritmoO ShellSort uma tima opo para arquivos de tamanho moderado, mesmoporque sua implementao simples e requer uma quantidade de cdigo pequena.Vantagens- Cdigo Simples- Interessante para arquivos de tamanho moderadoDesvantagens 11. - Algoritmo no estvel- Tempo de execuo sensvel ordem inicial do arquivo.QuickSort o algoritmo mais rpido que se conhece entre os de ordenao interna para umaampla variedade de situaes. Foi escrito em 1960 e publicado em 1962 por C.A. R. Hoare aps vrios refinamentos. Porm em raras instncias especiais ele lento. Adotando a estratgia Dividir para conquistar o funcionamento resume-se adividir o problema de ordenar um vetor de n posies em dois outros menores. OQuickSort provavelmente o mais utilizado, porm a sua implementao demandaum pouco mais de pacincia e cautela.Ilustrao do funcionamento do algoritmo QuickSort. 12. ImplementaoA parte crucial do algoritmo o mtodo Partition quem tem a funo de rearranjar ovetor por meio da escolha de um piv, de tal forma que ao final o vetor estarparticionado em uma parte esquerda com chaves menores ou iguais ao piv e outramaiores ou iguais.O algoritmo procede da seguinte forma:1. Zera os valores das variveis de medio atravs do mtodo ClearAll();2. Inicia a contagem de tempo com a funo start();3. Escolha um elemento aux1 do vetor Array para ser o piv;4. Usando aux1 divida o vetor Array em duas partes, da seguinte maneira: Comeando com i = posio inicial, percorra o vetor em forma crescente at queum elemento Array[i] = aux1 seja encontrado. Comeando com j = posio nal, percorra o vetor em forma descendente at queum elemento A[j] = X seja encontrado; Se i</p>