Análise dos métodos de ordenação
David Couto Bitencourt
Sistemas de Informação – Universidade Estadual do Sudoeste da Bahia (UESB).
Caixa Postal 45.206 – 190 – Jequié – BA – Brasil
Colegiado do Curso de Sistemas de Informação
Departamento de Química e exatas (DQE)
david_couto1@hotmail.com
Abstract. The meta-paper describes and analyzes the performance of sorting algorithms: SelectionSort, InsertionSort, BubbleSort, ShellSort, QuickSort and MergeSort. The analysis consists of comparing algorithms using three performance metrics: number of key comparisons, copy number of records held and the total time spent sorting.
Keywords. methods, sorting, bubble, quick, merge.
Resumo. O meta-artigo descreve e analisa o desempenho dos algoritmos de ordenação: SelectionSort, InsertionSort, BubbleSort, ShellSort, QuickSort e MergeSort. A análise consiste em comparar os algoritmos considerando três métricas de desempenho: número de comparações de chaves, número de cópia de registros realizadas e o tempo total gasto para ordenação.
Palavras-Chave. métodos, ordenação, bubble ,quick, merge.
1. Introdução
A ordenação consiste em arranjar os elementos de um conjunto de modo a facilitar a posterior recuperação ou análise dos dados. Por ser tão importante a ordenação é uma das atividades mais utilizadas na computação.
Existem diversos métodos para dispor os dados da melhor forma, para uma subseqüente consulta, análise ou remoção de algum item, se for conveniente.
Neste trabalho iremos abordar alguns métodos de ordenação interna, são eles: BubbleSort, InsetionSort, SelectionSort, ShellSort, QuickSort e o MergeSort. Serão apresentados testes com vetores de palavras, de diferentes tamanhos (100, 1000, 10000, 100000) e tipos (ordenados em ordem crescente e decrescente).
Os vetores serão comparados entre si, segundo as métricas de desempenho:
- Número de comparações de chaves.
- Número de cópias de registros realizadas.
- Tempo total gasto para ordenação.
Os testes de ordenação foram feitos com base na tabela ASCII. Neste trabalho o número de comparações de chaves são as verificações entre dois quaisquer elementos que influenciem na forma como o vetor está ordenado. O número de cópias de registros realizadas, também chamado neste artigo de número de trocas, foi feito levando em consideração as movimentações que o método realizou entre os elementos do vetor que influenciaram em sua ordenação. O tempo de execução de cada algoritmo foi feito através do comando clock (), da biblioteca (time.h).
Este artigo tem como propósito demonstrar a eficiência dos métodos de ordenação para diferentes conjuntos de elementos, provando que existem algoritmos que são superiores aos demais e que a implementação do melhor método de ordenação depende do tamanho e do tipo de vetor a ser ordenado.
2. Métodos de Ordenação
Os métodos de ordenação são classificados em dois grandes grupos: ordenação interna e externa.
Ordenação Interna: São os métodos que não necessitam de uma memória secundária para o processo, a ordenação é feita na memória principal do computador;
Ordenação Externa: Quando o arquivo a ser ordenado não cabe na memória principal e, por isso, tem de ser armazenado em fita ou disco.
A principal diferença entre os dois grupos é que no método de ordenação interna qualquer registro pode ser acessado diretamente, enquanto no método externo é necessário fazer o acesso em blocos [1].
Neste trabalho vamos abordar apenas os métodos de ordenação interna.
– Métodos de ordenação Interna
Durante a escolha de um algoritmo de ordenação, deve-se observar um aspecto importante: o tempo gasto durante a sua execução. Para algoritmos de ordenação interna, as medidas de complexidade relevantes contam o número de comparações entre as chaves e o número de movimentações de itens do arquivo [2].
Outra medida que pesa na escolha é a quantidade de memória extra utilizada pelo algoritmo. Métodos que realizam a permutação dos elementos no próprio vetor são chamados in situ, esses métodos são os preferidos. Os métodos que necessitam de memória extra para armazenar outra cópia dos itens possuem menor importância.
Os métodos de ordenação interna são classificados em dois subgrupos.
2.1.1 Métodos simples:
1. BubbleSort
2. InsertionSort
3. SelectionSort
2.1.2 Métodos eficientes
SheelSort
QuickSort
HearpSort
MergeSort
2.1.1.1 BubbleSort
É o método mais simples em termos de implementação, porém é o menos eficiente.
A idéia principal do algoritmo é percorrer o vetor n-1 vezes, a cada passagem fazendo flutuar para o inicio o menor elemento da seqüência. Essa movimentação lembra a forma coma as bolhas procuram seu próprio nível, por isso o nome do algoritmo. Seu uso não é recomendado para vetores com muitos elementos [3].
Vantagens: é um algoritmo de fácil implementação, algoritmo estável.
Desvantagens: O fato de o arquivo estar ordenado não ajuda em nada, ordem de complexidade quadrática [3].
InsertionSort
O InsertionSort é eficiente quando aplicado à um vetor com poucos elementos. Em cada passo, a partir de i=2, o i-ésimo item da seqüência fonte é apanhado e transferido para a seqüência destino, sendo inserido no seu lugar apropriado [2]. O algoritmo assemelha-se com a maneira que os jogadores de cartas ordenam as cartas na mão em um jogo, como o pôquer, por exemplo.
O InsertionSort também é um método de simples implementação, e tem a complexidade igual ao BubbleSort. Pode ser aprimorado com o uso de sentinela e outras técnicas de algoritmos. É o melhor para se utilizar quando os arquivos já estão quase ordenados [3].
Vantagens: É um algoritmo de fácil implementação, algoritmo estável, o vetor já ordenado favorece a ordenação.
Desvantagens: Número grande de movimentações, ordem de complexidade quadrática, ineficiente quando o vetor está ordenado inversamente [3].
SelectionSort
O SelectionSort tem como principio de funcionamento selecionar o menor item do vetor e a seguir trocá-lo pela primeira posição do vetor. Isto ocorre para os n-1 elementos restantes, depois com os n-2 itens, até que reste apenas um elemento [2]. A principal diferença destes métodos em relação ao BubbleSort e ao InsertionSort é que ele realiza apenas uma troca por interação.
Vantagens: É um algoritmo de fácil implementação, pequeno número de movimentações, interessante para arquivos pequenos.
Desvantagens: O fato de o arquivo já estar ordenado não ajuda em nada, ordem de complexidade quadrática, algoritmo não estável [3].
2.1.2.1 ShellSort
Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell Sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção [3].
Vantagens: O algoritmo tem o código simples, interessante para arquivos de tamanho moderado.
Desvantagens: Algoritmo não estável, tempo de execução sensível à ordem inicial do arquivo [3].
QuickSort
É o algoritmo mais rápido que se conhece entre os de interna para ampla variedade de situações. Foi escrito em 1960 e publicado em 1962 por C.A.Hoare após vários refinamentos [2]. Adotando a estratégia dividir para conquistar o funcionamento resume-se a dividir o problema de ordenar um vetor de n posições em dois outros menores.
Vantagens: Extremamente eficiente, necessita apenas de uma pequena pilha como memória extra.Complexidade de n(log)n.
Desvantagens: Tem um pior caso de O(n²) , implementação difícil, não é estável [3].
2.1.2.3 MergeSort
É outro algoritmo de ordenação do tipo dividir para conquistar. Sua idéia básica é criar uma seqüência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a seqüência original em pares de dados, ordena-as; depois as agrupa em seqüencial de quatro elementos, e assim por diante, até ter toda a seqüência dividida em apenas duas partes [3].
Os três passos úteis dos algoritmos dividir para conquistar, que se aplicam ai Mergesort são:
Dividir: Dividir os dados em subseqüências pequenas;
Conquistar: Classificar as duas metades recursivamente aplicando o mergesort;
Combinar: Juntar as duas metades em um único conjunto já classificado.
Vantagens: Passível de ser transformado em estável, fácil implementação, complexidade O(nlogn).
Desvantagens: utiliza memória auxiliar
3. Resultados
Foram testados os seis métodos de ordenação, para cada método foi testado um tamanho diferente de vetor (100, 1000, 10000, 1000000) e para cada tamanho um tipo diferente (Ordenado Crescente, Ordenado Decrescente). Os resultados serão apresentados em quatro grupos, divididos pelo tipo do vetor. Os métodos serão numerados para apresentação na tabela, conforme a lista abaixo:
BubbleSort
InsertSort
SelectSort
ShellSort
QuickSort
MergeSort
Também serão utilizadas as seguintes abreviações para os tipos de vetores:
OrdC: Vetor ordenado em ordem crescente.
OrdD: Vetor ordenado em ordem decrescente.
3.1 Vetor ordenado em ordem crescente
A figura 1 apresenta a quantidade de comparações e movimentos para o vetor de tipo OrdC, enquanto a figura 1.1 apresenta os resultados em função do tempo.
Vetor em Ordem Crescente
100
1000
10000
100000
Comp.
Mov.
Comp.
Mov.
Comp.
Mov.
Comp.
Mov.
1
9900
0
999000
0
99990000
0
1409965408
0
2
99
0
999
0
9999
0
99999
0
3
4950
0
499500
0
49995000
0
704982704
0
4
503
0
8006
0
120005
0
1500006
0
5
606
63
9009
511
125439
5904
1600016
65535
6
672
316
9976
4932
133616
64608
1668928
815024
Figura 1: Quantidade de comparações e movimentos dos testes no vetor OrdC.
Vetor em Ordem Crescente
100
1000
10000
100000
1
0.003
0.25
23.821
2665.74
2
0
0
0.005
0.047
3
0
0.078
7.625
796.182
4
0
0
0.047
0.664
5
0
0.002
0.028
0.343
6
0
0
0.047
0.577
Figura 1.1: Tempo gasto pelos testes no vetor OrdC.
A seguir as figuras 1.2, 1.3, 1.4 e 1.5 apresentam os gráficos em função do número de comparações e movimentos para os quatro tamanhos de vetores testados.
Ordem Crescente – 100 Elementos
Figura 1.2: Número de comparações e movimentações do teste aplicado em um vetor de 100 posições do tipo OrdC. Em escala logarítmica.
Ordem Crescente – 1000 Elementos
Figura 1.3: Número de comparações e movimentações do teste aplicado em um vetor de 1000 posições do tipo OrdC. Em escala logarítmica.
Ordem Crescente – 10000 Elementos
Figura 1.4: Número de comparações e movimentações do teste aplicado em um vetor de 10000 posições do tipo OrdC. *Valores reduzidos em 1000 vezes. Em escala logarítmica.
Ordem Crescente – 100000 Elementos
Figura 1.5: Número de comparações e movimentações do teste aplicado em um vetor de 100 posições do tipo OrdC. *Valores reduzidos em 100000 vezes. Em escala logarítmica.
Baseado nas tabelas e nos gráficos, percebemos que para arquivos pequenos o SheelSort foi o melhor em número de movimentações e que seu tempo de execução foi semelhante ao do QuickSort e do MergeSort .O InsertionSort foi excelente em todos os tamanhos em um vetor já ordenado . O BubbleSort demonstrou um número de comparações muito grande para qualquer tamanho de vetor sendo um dos piores métodos para um vetor já ordenado junto com o SelectionSort.
Vetor ordenado em ordem decrescente
A figura 1.6 apresenta a quantidade de comparações e movimentos para o vetor de tipo OrdD, enquanto a figura 1.7 apresenta os resultados em função do tempo.
Vetor em Ordem Decrescente
100
1000
10000
100000
Comp.
Mov.
Comp.
Mov.
Comp.
Mov.
Comp.
Mov.
1
9900
4950
999000
499500
99990000
49995000
1409965408
704982704
2
99
99
999
999
9999
9999
99999
99999
3
4950
50
499500
500
49995000
5000
704982704
50000
4
503
256
8006
4372
120005
62032
1500006
811248
5
610
112
9016
1010
125452
10904
1600030
115534
6
672
316
9976
4932
133616
64608
1668928
815024
Figura 1.6: Quantidade de comparações e movimentos dos testes no vetor OrdD.
Vetor em Ordem Decrescente
100
1000
10000
100000
1
0.004
0.49
48.546
4890.81
2
0.002
0.187
17.238
1716.55
3
0.001
0.121
12.631
1258.72
4
0
0.005
0.081
1.018
5
0
0.002
0.031
0.4
6
0
0.015
0.063
0.771
Figura 1.7: Tempo gasto pelos testes no vetor OrdD
A seguir as figuras 1.8, 1.9, 2.0 e 2.1 apresentam os gráficos em função do número de comparações e movimentos para os quatro tamanhos de vetores testados.
Ordem Decrescente – 100 Elementos
Figura 1.8: Número de comparações e movimentações do teste aplicado em um vetor de 100 posições do tipo OrdD. Em escala logarítmica.
Ordem Decrescente – 1000 Elementos
Figura 1.9: Número de comparações e movimentações do teste aplicado em um vetor de 1000 posições do tipo OrdD. Em escala logarítmica.
Ordem Decrescente – 10000 Elementos
Figura 2.0: Número de comparações e movimentações do teste aplicado em um vetor de 10000 posições do tipo OrdD. Em escala logarítmica.
Ordem Decrescente – 100000 Elementos
Figura 2.1: Número de comparações e movimentações do teste aplicado em um vetor de 100000 posições do tipo OrdD. *Valores reduzidos em 100000 vezes. Em escala logarítmica.
Com base nos testes, podemos afirmar que para vetores em ordem decrescente com tamanho até 10000 elementos o ShellSort provou ser o melhor, acima deste tamanho o QuickSort o supera em termos de tempo de execução. O BubbleSort, o InsertionSort e o SelectionSort são os piores métodos para vetores ordenados inversamente. O MergeSort demonstrou ser um excelente método para tamanhos grandes de vetores que estão ordenados inversamente.
Conclusão
Foram apresentados seis métodos de ordenação interna levando em consideração a comparação de chaves. Após os testes e o estudo dos resultados e dos algoritmos, são apresentados observações sobre cada um dos métodos.
BubbleSort
Apresentou-se como pior método de ordenação.
InsertionSort
Em arranjos já ordenados demonstrou um comportamento linear, sendo útil para ordenação de arquivo com poucos elementos fora da ordem.
SelectionSort
Apresentou uma vantagem apenas no número de movimentações, porém seu tempo de execução é pior que o InsertionSort.
A sua utilização deve ser feita quando os registros dos arquivos forem grandes, em virtude da quantidade de movimentos que é realizada para a operação.
ShellSort
Apresentou-se eficiente em todos os testes.
Em geral é um método que se adéqua a todas as situações.
A sua relação com o QuickSort cresce a medida que o número de elementos aumenta.
Em todas as situações manteve-se próximo do algoritmo mais rápido do teste.
QuickSort
Obteve o melhor resultado na maioria dos testes.
Sua eficiência foi identificada apenas nos grandes arquivos.
MergeSort
Apresentou um tempo de execução semelhante ao do QuickSort, usando a estratégia de ordenação por fusão, provou ser eficiente em vetores de arquivos grandes.
Pelos testes realizados, conclui-se que a escolha de um algoritmo de ordenação depende do tipo de vetor e tamanho a ser ordenado.
Podemos concluir, ainda, que fica evidente a discrepância entre alguns métodos de ordenação em relação aos seus respectivos desempenhos, tanto na quantidade de comparações e trocas, quanto no seu tempo de execução. Podemos citar como exemplo a diferença entre o BubbleSort e o QuickSort.
A partir dos resultados apresentados neste trabalho, podemos afirmar que para acessar dados de uma forma mais rápida e objetiva, além de estarem ordenados, é interessante que sejam ordenados da forma mais eficiente possível. Para isto o desenvolvedor deve ter conhecimentos referentes aos métodos de ordenação mais utilizados, sabendo qual o melhor método se aplica a cada caso, obtendo, assim, um maior desempenho da sua aplicação.
5. Referências
[1] Álvaro Borges de Oliveira. Métodos de Ordenação Interna. Visual Book, São Paulo, 1st edição, 2002.
[2] Nivio Ziviane. Projeto de Algoritmos com implementação e C++ e Java. THOMPSON Learning, São Paulo, 1st edição 2007.
[3] David Mennoti Gomes. Ordenação. Algoritmos e estrutura de dados – Métodos de ordenação interna, 2008. http://webcache.googleusercontent.com/search?q=cache:AwIkQANy6D4J:www.decom.ufop.br/menotti/aedI082/tps/tp3-sol1.pdf+&cd=2&hl=pt-BR&ct=clnk&gl=br. Acessado em 20/04/2014.
102
S. Sandri, J. Stolfi, L.Velho
102
S. Sandri, J. Stolfi, L.Velho
Proceedings of the XII SIBGRAPI (October 1999)
Proceedings of the XII SIBGRAPI (October 1999) 101-104
Proceedings of the XII SIBGRAPI (October 1999)
Proceedings of the XII SIBGRAPI (October 1999) 101-104