Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 LUCAS GALHARDI MATHEUS NOVAES RODOLFO SALDANHA ORDENAÇÃO PARCIAL LONDRINA 2014 2 SUMÁRIO 1 INTRODUÇÃO .......................................................................................................................... 3 2 MATERIAL E MÉTODOS ........................................................................................................ 5 3 RESULTADOS E DISCUSSÃO .............................................................................................. 11 4 CONCLUSÕES ........................................................................................................................ 22 5 REFERÊNCIAS ........................................................................................................................ 25 3 1 INTRODUÇÃO O processo de classificar um conjunto de objetos em uma ordem ascendente ou descendente é definido como ordenação. A prática de ordenação visa de certo modo facilitar a recuperação consecutiva dos elementos do conjunto ordenado (THOMSON, 2007). A classificação pode ser denotada de duas maneiras: interna e externa. A classificação interna é quando os registros a serem classificados encontram-se na memória principal, e externa se alguns dos registros que ela classificar estiver no armazenamento auxiliar (TENENBAUM, LANGSAM e AUGENSTEIN, 1995). A principal diferença entre os dois grupos é que o método de ordenação interna qualquer registro pode ser acessado diretamente, por outro lado, no método externo o acesso é feito em blocos. Uma técnica de classificação é considerada estável, se e somente se, após a ordenação os conteúdos com a mesma chave se manterem na mesma ordem relativa em que estavam antes da classificação. Os métodos de classificação mais conhecidos são: classificação por troca, classificação por seleção e classificação por inserção. No método de ordenação por troca é realizada uma comparação entre dois elementos do conjunto verificando se a posição do antecessor e do elemento sucessor segue a base de classificação especificada. De tal maneira haja cumprimento do critério estabelecido nada é realizado, caso contrário troca-se a posição, por exemplo, BubbleSort e QuickSort. A ordenação por inserção em cada momento toma-se um determinado elemento em que se encontra um trecho ainda não ordenado e realiza-se a inserção deste elemento na posição correta seguindo o critério de classificação especificado, por exemplo, InsertionSort e ShellSort. A classificação por seleção, em cada instante é selecionado da parte ainda não classificado do conjunto o elemento mais apropriado para ser acrescentado no trecho já classificado, reduzindo por consequência o trecho ainda não classificado e aumentando a parcela do conjunto já classificado, por exemplo, SelectionSort e HeapSort. Os objetivos deste trabalho consistiram em programar e analisar o comportamento e eficiência dos algoritmos de ordenação parcial levando em consideração os seguintes fatores: 4 1. Número de comparações realizadas entre as chaves do vetor; 2. Número de trocas; 3. Contagem do tempo gasto durante a execução de cada algoritmo com diferentes tamanhos de vetores. Os 3 fatores descritos foram obtidos combinando se 4 fatores para gera-los: 1 –O Algoritmo de Ordenação Parcial utilizado; 2 – Tamanho de N, com N sendo o número de elementos do vetor; 3 – Tamanho de K, com K sendo os K maiores ou menores elementos; 4 – Se o vetor está previamente ordenado, embaralhado ou inversamente ordenado; Variantes Há ainda outro fator que influencia o desempenho, se o vetor retornado com os k maiores ou menores elementos precisa estar ordenado ou não (variantes). Porém foi constatado que esse fator só pôde ser aplicado ao QuickSort e será descrito mais a frente. 5 2 MATERIAL E MÉTODOS 2.1 Métodos de Ordenação Para a escolha de um determinado algoritmo de ordenação é necessário levar em consideração alguns fatores de suma importância, que incluem o tempo que será gasto durante a sua execução, o número de comparações entre as chaves e o número de movimentações dos registros no arquivo. Os métodos de classificação interna podem ser classificados em duas subdivisões (THALES, 2008): Métodos simples: 1. InsertSort (ou InsertionSort) 2. SelectSort (ou SelectionSort) Métodos eficientes: 1. ShellSort 2. QuickSort 3. HeapSort A metodologia de ordenação parcial consiste em obter os K primeiros elementos de um determinado arranjo ordenando com n elementos. Os métodos simples de ordenação possuem função de complexidade e os métodos eficientes ou sofisticados possuem complexidade em um cenário médio, porém apenas no caso do ShellSort não é possível afirmar pois sua análise é difícil e depende do gap (o valor do pulo, do “h”). A seguir serão apresentados os métodos de ordenação e trechos de código, os códigos completos podem ser encontrados no CD. 6 2.2 InsertSort O método de classificação InsertSort é considerado um dois métodos mais elementares no que diz respeito a sua implementação, porém deixa a desejar no critério de eficiência, seu melhor desempenho é quando aplicado a vetores com poucos elementos. A abstração elementar do algoritmo o i-ésimo elemento da sequência fonte é apanhado e transferido para a sequência de destino sendo colocado na sua posição correta de classificação (Figura 1). Figura 1. Trecho de código referente ao algoritmo de classificação InsertSort parcial. 7 2.3 SelectSort Tem como priori selecionar o menor elemento do arranjo e trocá-lo pela primeira posição do arranjo. De tal maneira isto ocorre para os n – 1 elementos que restaram, em continuidade os n – 2 elementos, até que reste apenas um elemento (THALES, 2008). Conforme ilustração referente à implementação parcial do algoritmo (Figura 2). Figura 2. Trecho de código referente ao algoritmo de classificação SelectSort parcial. 8 2.4 ShellSort O ShellSort é uma extensão do método InsertSort. Proposto por Shell em 1959. O algoritmo consiste em trocar itens adjacentes quando está procurando o ponto de inserção na sequência destino. Os itens separados em h posições são rearranjados, todo h-ésimo item leva uma sequência ordenada. Tal sequência e detonada h-ordenada. No entanto, foi implementado a ordenação parcial ( Figura 3). Figura 3. Trecho de código referente ao algoritmo de classificação ShellSort parcial. 9 2.5 QuickSort É o algoritmo que apresenta a maior velocidade de ordenação que se conhece entres os algoritmos de ordenação interna para inúmeras variedades de situações. Foi proposto em 1960 e publicado em 1962 por C. A. R. Hoare. A priori consiste em dividir o problema de ordenar em um arranjo com n itens em dois problemas menores. Foi implementado o QuiksSort parcial (Figura 4). Figura 4. Trecho de código referente ao algoritmo de classificação QuickSort parcial. 10 2.6 HeapSort Utilizando o mesmo princípio do SelecSort , o HeapSort é um algoritmo que utiliza uma estrutura de dados denotada como Heap que é organizada como árvore bináriabalanceada, seguindo algumas regras (CORMEN, 2009). Existem dois tipos de heaps: Os heaps de máximo, em que o valor de todos os nós é menor que os de seus respectivos pais; e os heaps de mínimo, em que o valor de todos os nós maiores que seus respectivos pais (CORMEN, 2009). Foi o implementado a ordenação parcial utilizando o HeapSort (Figura 5). Figura 5. Trecho de código referente ao algoritmo de classificação HeapSort parcial. 11 3 RESULTADOS E DISCUSSÃO Foram testados todos os cinco métodos de ordenação parcial, para cada método foi adotado diferentes tamanhos (n) de vetores ( 2 13 , 2 14 , 2 15 , 2 16 , 2 17 , 2 18 , 2 19 e 2 20 ) e para cada tamanho três tipos de arranjo dos vetores( Aleatório, Ordenado e Inversamente ordenado) e diferentes k elementos a serem ordenados ( 20%, 50% e 80%). Analisando se os algoritmos não foi encontrada uma maneira mais eficiente que retornasse os primeiros k elementos sem estarem ordenados, portanto o único algoritmo que possui diferença na execução da variável findSorted_k_Smallest e da find_k_Smallest foi o QuickSort, será mostrado uma comparação de ambos. Foi constatado por experimentação que o Largest e o Smallest têm o mesmo desempenho, portanto a variante usada em todos os testes foi a findSorted_k_Smallest. A partir dos testes foram gerados arquivos .txts com os dados e a partir dai copiados para planilhas do Excel onde foram gerados os gráficos. Os dados e as planilhas podem ser vistos no CD. 12 Vetor Aleatório (tempo) Quick Sort Para vetores aleatórios, dentre os algoritmos sofisticados, o Quick Sort é o mais rápido. Quick, Heap e Shell apresentam um crescimento perto do linear e conforme aumenta o valor de K se aumenta o tempo, exceto para o Shell que o valor de K não influencia significativamente em seu tempo. O Shell fica atrás do Heap. Heap Sort Já o crescimento do Selection e do Insertion é parecido, devido a sua complexidade quadrática. Conforme o K varia seus tempos também variam. Apesar de semelhantes é notável que o Insertion consegue ser um pouco melhor. Shell Sort A diferença de tempo, para um mesmo N e K, entre o mais rápido (Quick) e o mais lento (Selection) é absurda, enquanto o primeiro não chega a 0,2 segundos o outro chega a 1500 segundos (cerca de 7500x mais lento). Selection Sort Insertion Sort 13 Vetor Aleatório (comparações) Quick Sort As comparações para os vetores aleatórios seguem o mesmo padrão do tempo, Quick sendo o melhor, o Heap atrás e depois o Shell. Heap Sort Já o crescimento do Selection e do Insertion é parecido em sua forma novamente, porém dessa vez é constatado que o Insertion realiza cerca de metade das comparações que o Selection. Shell Sort A diferença de comparações para os algoritmos sofisticados e simples fica evidente, já que o Heap, Quick e Shell ficam entre 0 e 100 milhões enquanto o Selection e o Insertion podem chegar a 300 ou 600 bilhões. Selection Sort Insertion Sort 14 Vetor Aleatório (trocas) Quick Sort O Quick e o Heap fazem menos trocas que comparações, ao contrario do Shell, que apesar de sofisticado faz mais trocas que comparações. Heap Sort Em relação às trocas, o Selection é bem diferente do Insertion, pois a quantidade de trocas é linear, enquanto o Insertion realiza quase a mesma quantidade de trocas e comparações (300 bilhões). Shell Sort Comparando os métodos sofisticados e simples, o Selection se destaca sendo o melhor, porém apenas no aspecto de quantidade de trocas. Selection Sort Insertion Sort 15 Vetor Já Ordenado (tempo) Quick Sort Para quando o vetor já está ordenado, o Insertion se mostrou muito mais eficiente em relação aos demais, não ultrapassando o tempo de 0,010 segundos. O Quick e o Shell também se mostraram bastante eficientes, com o Quick em Heap Sort vantagem. Heap foi mais rápido que o Shell apenas para k = 20%. O Selection mostrou-se como o pior caso para vetores já ordenados, o seu termo foi maior 20000x que o Insertion, o melhor no caso. Shell Sort O Shell praticamente não sofre influência grave do k, mesmo variando foi possível observar que o tempo é quase o mesmo. O Insertion obteve esse gráfico estranho devido ao tempo ser muito pequeno e o processo de medir o tempo não ser muito preciso a valores tão baixos. Selection Sort Insertion Sort 16 Vetor Já Ordenado (comparações) Quick Sort Em relação ao número de comparações, o Insertion demonstrou-se mais eficiente realizando um número bem menor de comparações em relação aos demais. Independente do K o número de comparações será a mesma para esse tipo de ordenação. Heap Sort O Selection realiza cerca de 600000x comparações a mais em ralação ao Insertion, sendo o pior caso de novo. O Heap também não mostrou um bom desempenho em relação ao número de comparações. Shell Sort O Shell com um k superior a 50% se mostrou mais eficiente que o Heap, no entanto, para valores menores de k perde para o Heap e o Quick. Selection Sort Insertion Sort 17 Vetor Já Ordenado (trocas) Quick Sort Exceto o Heap, os demais métodos de ordenação não realizam trocas quando o vetor já está ordenado. Heap Sort O Heap realiza trocas pelo fato de primeiramente ele construir a Heap, fazendo trocas, antes de fazer qualquer comparação, dessa maneira desordenando o vetor antes de ser notado que o vetor já estava ordenado. Shell Sort Selection Sort Insertion Sort V 18 Vetor Inversamente Ordenado (tempo) Quick Sort Como nos outros casos o Quick está entre os melhores em relação ao desempenho do tempo, e nesse caso específico é o mais rápido. Heap Sort Os métodos que apresentaram pior desempenho foram o Insertion e o Selection, sendo que o Insertion foi o que obteve pior desempenho, com uma diferença imensamente discrepante de tempo do Quick, que obteve melhor resultado. Essa diferença de tempo chega à Shell Sort aproximadamente 30000x. Nesse caso, quando k for maior que 50%, depois do Quick, o que tem melhor desempenho é o Shell, passando o Heap, que também é um algoritmo sofisticado. Selection Sort Insertion Sort 19 Vetor Inversamente Ordenado (comparações) Quick Sort Assim como em relação ao tempo, o Quick apresenta melhor desempenho nas comparações, ou seja, é o método que faz o menor número de comparações e o Insertion e o Selection são os que possuem pior desempenho, fazendo um número bem superior de comparações que os demais Heap Sort métodos. É notado que para k>50%, o Shell atinge um desempenho melhor que o Heap,fazendo um número menor de comparações. Shell Sort Assim como foi observado muitas vezes, o número de comparações feita pelo Shell independe de k, sendo o mesmo para os três valores de k. Selection Sort Insertion Sort 20 Vetor Inversamente Ordenado (trocas) Quick Sort Caso o vetor esteja inversamente ordenado, o k não interfere no número de trocas feitas pelo Quick, assim como Shell também permanece quase que inalterado independentemente do k. Heap Sort O Selection obtém bom desempenho nas trocas inversamente ordenado, pois devido ao seu modo de funcionamento ele vai ordenando a 2ª metade do vetor indiretamente. Exemplo: ele troca o 0 com o 999, o 1 com o 998 e assim quando chega na metade já ordenou Shell Sort tudo. Portanto para k>=50% ele é igual. Assim como no tempo, a partir de k=50% o número de trocas no Heap passa a ser maior que o do Shell, justificando assim o tempo superior. Selection Sort Insertion Sort 21 Comparação 2 variantes do QuickSort Para o método do QuickSort foi possível criar a variante find_k_Smallest de forma a mesma obtivesse um desempenho melhor que a findSorted_k_Smallest. O QuickSort funciona da seguinte maneira: um elemento é escolhido como pivô e então os valores menores que o pivô são colocados antes dele e os maiores depois. Isso é feito através de dois marcadores de índices chamados “esq” e “dir” que são esquerda e direita e conforme a esq for menor que o pivô vai se avançando rumo a direita e conforme a dir for maior que o pivô vai em direção a esquerda. Dessa forma quando a esquerda e a direita se cruzarem isso significa que todos elementos a esquerda do pivô são menores que ele, e todos a direita são maiores, portanto é possível parar a ordenação da partição esquerda quando o esq for < k, pois isso significa q os k elementos já estão do lado esquerdo. E essa simples alteração no algoritmo proporciona ótimos resultados em relação ao tempo, as comparações e trocas pois é possível evitar muitas chamadas a função, dada que ela é recursiva. Ao lado e abaixo são mostrados 3 gráficos onde o k usado foi k = 50% em um vetor embaralhado (ordem aleatória) para fins de comparação entre as 2 funções. É possível observar que a diferença das duas variantes é muita expressiva, o que mais que justifica o uso da find_k_Smallest caso não haja necessidade do vetor retornado estar ordenado. 22 4 CONCLUSÕES SelectionSort: Em seus gráficos é possível notar a forma quadrática, confirmando que o desempenho do algoritmo se mantem no caso da ordenação parcial. O Selection possui uma única vantagem sobre os demais, que é a sua quantidade de trocas para vetores aleatórios que é linear. Porém suas vantagens acabam ai, pois seu numero de comparações é sempre igual e quanto maior o valor de N mais distante é dos outros algoritmos. Obteve o pior desempenho em quase todos os testes, ganhou apenas na troca para vetor aleatório e ganhou do Insertion apenas no tempo e no numero de trocas para vetor inversamente ordenado. Uma única outra vantagem, porém não muito significativa, é que ele tem o menor numero de trocas em vetores inversamente ordenados, pois ao ordenar metade do vetor, a 2ª metade também ficará automaticamente ordenada, sendo melhor que o Quick para k<50% e igual para k>=50%. Porém devido a seu numero gigantesco de comparações que sempre se mantem ele acaba tendo um péssimo desempenho no tempo, porém o baixo numero de trocas possibilita que ele seja melhor que o Insertion neste caso. InsertionSort: O Insertion é o outro algoritmo simples e pode ser comparado com o Selection. No geral o Insertion é melhor que o Selection, pois no vetor aleatório obtém melhor desempenho. Porém devido à “propriedade especial do Selection para vetor inversamente ordenado” o Insertion perde nesse ponto, porém em questão de tempo não fica tão atrás assim. Entretanto o maior trunfo do Insertion fica por conta do vetor já ordenado, onde ele é imbatível em tempo, comparações e trocas, ganhando até mesmo dos algoritmos sofisticados. 23 ShellSort: Dentre os 3 algoritmos sofisticados analisados é o que tem pior desempenho. Porém é notado que ele faz jus ao nome de sofisticado, não ficando muito atrás do Quick e do Heap. Devido ao modo como o Shell funciona não foi possível alterar muito seu algoritmo para que ordene parcialmente. A solução encontrada foi usar a mesma alteração do Insertion quando o Shell esta trabalhando com o 1-ordenada, pois nesse caso ele é exatamente o algoritmo de Inserção. Quando se chega na 1-ordenada o Shell já deixou o vetor “praticamente ordenado” e como o InsertionSort é muito rápido para o vetor já ordenado e consequentemente para o quase ordenado então o tempo economizado acaba não sendo tão grande. O ponto mais positivo do Shell é que ele ganhou do Heap em certos momentos, para valores de k>50%. HeapSort: Devido ao uso de uma estrutura chamada Heap, que é parecida com uma árvore binária, este algoritmo possui um ótimo desempenho. Perdendo quase todas as vezes apenas para o Quick este algoritmo é excelente. Um ponto negativo seu é que ele é o único dos algoritmos estudados que realiza trocas quando o vetor já esta ordenado. Já um ponto positivo é que para o pior caso ele mantem a complexidade enquanto o Quick possui nesse caso (apesar de muito raro). Outra vantagem sobre o Quick é que ele não utiliza recursão, evitando assim, o uso de memória adicional, pois não há chamadas recursivas. Portanto caso se queira um algoritmo confiável que seja eficiente mesmo no pior caso e se deseja evitar memoria adicional este é o algoritmo certo. QuickSort: O QuickSort é o algoritmo de ordenação mais eficiente para a maioria dos casos, inclusive para a parcial e para o caso de retornar os k primeiros elementos sem a necessidade dos mesmos estarem ordenados. Ele perde em desempenho apenas para o Insertion no caso do vetor já ordenado, praticamente empata em trocas com o Selection no inversamente ordenado e possui a desvantagem do uso de memoria adicional enquanto os outros não precisam. 24 Representando 9 diferentes situações: 1 – Vetor aleatório (tempo) 2 – Vetor aleatório (comparações) 3 – Vetor aleatório (trocas) 4 – Vetor já ordenado (tempo) 5 – Vetor já ordenado (comparações) 6 – Vetor já ordenado (trocas) 7 – Vetor inversamente ordenado (tempo) 8 – Vetor inversamente ordenado (comparações) 9 – Vetor inversamente ordenado (trocas) Os algoritmos tiveram o melhor desempenho em: QuickSort: 1, 2, 3, 6, 7, 8 HeapSort: ShellSort: 6 InsertionSort: 4, 5, 6 SelectionSort: 6, 9 A partir disso é possível concluir que o QuickSort é o melhor para a maioria dos casos, há apenas 1 caso que ele empata com os outros como melhor (6) e apenas 2 casos que ele perde (4 e 5), para o Insertion. Ele perde também em 1 caso (9) para o Selection, por pouco, pois para k>=50% eles tem desempenho igual, porém o Selection ganha para valores de k<50%. O “2º lugar” é dividido para o Shell e o Heap, que mantem bons números porem dependendo do valor de K um é melhor e em outro caso o outro é melhor. Por fim sobram o Insertion e o Selection que possuem desempenho muito parecido, ora um obtém desempenho melhor, ora outro. Porém no caso do vetorjá ordenado o Insertion é excelente enquanto o Selection é péssimo, pois seu valor de comparações é igual para todos os casos. 25 5 REFERÊNCIAS F. LORENZI, P. N. DE MATTOS, T. P. DE CARVALHO. Estruturas de Dados. Thomson, 2007. TENENBAUM, A.M., LANGSAM, Y., AUGENSTEIN, M.J. Estruturas de Dados Usando C, Makron Books, 1995. CORMEN, T. H., LEISERSON, C. E., RIVEST, R. L. and STEIN, C. Introduction to Algorithms, 3rd Edition, The MIT Press, 2009.
Compartilhar