ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

UNIP – UNIVERSIDADE PAULISTA
INSTITUTO DE CIÊNCIAS EXATAS E TECNOLOGIA (ICET)

André Araujo Hamada RA: 782386-0

ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE
DADOS

SÃO PAULO
2012
Índice

1–Objetivo do Trabalho...............................................................................................5
2–Introdução................................................................................................................6
3–Referencial Teórico..................................................................................................8
3.1–Blubble Sort......................................................................................................8
3.2–Merge Sort........................................................................................................9
3.3–Quick Sort……................................................................................................11
4–Resultados e Discussão.........................................................................................12
4.1–Vetor Ordenado..............................................................................................12
4.2–Vetor Quase Ordenado..................................................................................14
4.3–Vetor Aleatório................................................................................................16
4.4–Vetor Inversamente Ordenado.......................................................................18
4.5–Vantagens e Desvantagens...........................................................................20 
5–Considerações Finais.............................................................................................22
6–ReferênciasBibliográficas......................................................................................23

Lista de Imagens

Figura 1: Ilustração do funcionamento do algoritmo Bubble Sort...............................8
Figura 2: Ilustração do funcionamento do algoritmo Merge Sort...............................10
Figura 3: Ilustração do funcionamento do Quick Sort................................................11
Figura 4: Gráficos de atribuições 1............................................................................13
Figura 5: Gráficos de comparações 1........................................................................14
Figura 6: Gráficos de atribuições 2............................................................................15
Figura 7: Gráficos de comparações 2........................................................................16
Figura 8: Gráficos de atribuições 3............................................................................17
Figura 9: Gráfico de Comparações 3.........................................................................18
Figura 10: Gráficos de atribuições 4..........................................................................19
Figura 11: Gráfico de Comparações 4.......................................................................20

Lista de Tabelas

Tabela 1: Atribuições para um vetor ordenado.........................................................12
Tabela 2: Comparações para um vetor ordenado.....................................................12
Tabela 3: Tempo de execução para um vetor ordenado...........................................13
Tabela 4: Atribuições para um vetor quase ordenado...............................................14
Tabela 5: Comparações para um vetor quaseordenado...........................................14
Tabela 6: Tempo de execução para um vetor quase ordenado.................................15
Tabela 7: Atribuições para um vetor aleatório............................................................16 
Tabela 8: Comparações para um vetor aleatório.......................................................16
Tabela 9: Tempo de execução para um vetor aleatório.............................................17
Tabela 10: Atribuições para um vetor inversamente ordenado..................................18
Tabela 11: Comparações para um vetor inversamente ordenado.............................18
Tabela 12: Tempo de execução para um vetor inversamente ordenado...................19
Tabela 13: Vantagens e Desvantagens do Vetor Ordenado......................................20 
Tabela 14: Vantagens e Desvantagens do Vetor Quase Ordenado..........................20 
Tabela 15: Vantagens e Desvantagens do Vetor Aleatório.......................................21
Tabela 16: Vantagens e Desvantagens do Vetor Inversamente................................21 

1 - Objetivo do Trabalho

O objetivo desse trabalho é analisar a performance de algoritmos de ordenação de dados, tais como: 
* BubleSort
* SelectSort
* InsertSort
* QuickSort
* MargeSort

2 – Introdução

A ordenação é um dos aspectos fundamentais das ciências computacionais. Torna-se, então, importante reduzir ao máximo a complexidade temporal dos algoritmos que lidam com este problema. As melhores ordenações em série normalmente demoram O(n log n), tempo que tende a agravar com o aumento do número de elementos. Deste modo, foram desenvolvidas versões para funcionamento em paralelo destes algoritmos, cujo objetivo é diminuir consideravelmente o tempo deexecução dos mesmos.
Neste trabalho irei abordar alguns algoritmos de ordenação. Relativamente aos que realizam operações de comparação e troca, existem o bubble sort, quick sort, merge sort, insert sort e select sort. 
O algoritmo de ordenação bubble sort usa uma estratégia de comparação e troca, mas é o menos efeciente. Os elementos vão borbulhando a cada iteração do método até a posição correta e cada passada do algoritmo é garantante-se q o maior elemento fique na ultima posição do vetor. (Quinn, 2003)
O algoritomo de ordenação quick sort foi inventado por C.A.R. Hoare, é um algoritmo recursivo que tem como base a comparação de valores para ordenar uma lista desordenada. Mais especificamente, quando é passada uma lista de números, o algoritmo seleciona um número dessa lista, tornando-o pivô. Após isso, a lista é partida em duas sub-listas: uma contendo números inferiores ao pivot, e outra com os números superiores. Chama-se depois a si mesma recursivamente para ordenar as duas sub-listas. A função retorna a concatenação da primeira lista, pivot e segunda lista. (Tsigas e Zhang, 2003)
O merge sort, diferente dos outros algoritmos, procede à sua junção (merge), retornando no final uma única lista com todos os elementos ordenados. Consiste em ir separando em metades uma lista de elementos, até ficar com todos os elementos separados. Esta técnica tem o objetivo de dividir para conquistar após estes elementos estarem separados. (Wilkison e Allen, 2005)
No algoritmo de insert sort o vetor é dividido em dois segmentos, um com os elementos já ordenados e o outro com os elementos a ordenar. No início só o primeiro elemento está no segmento já ordenado, então é verificado qual a posição do primeiro elemento do segmento a ordenar no segmento já ordenado, então oelemento é retirado do segmento a ordenar e inserido no já ordenado. Esse processo se repete até que não exista segmento a ordenar o que coincide com a ordenação do vetor. (Cormen op. Cit.)
E o algoritmo select sort é feita a procura do menor elemento de todo e então este elemento é trocado de lugar o primeiro elemento do vetor. Então a procura pelo menor número é feita a partir do segundo elemento e é trocado de lugar com o segundo elemento do vetor, e assim sucessivamente até o penúltimo elemento e então o vetor estará ordenado. (Ziviani, 2004)



















3 – Referencial Teórico

3.1 – Bubble Sort
O algoritmo de ordenação Bubble Sort é bem simples de ser implementado, mas é o menos eficiente. A idéia desse algoritmo é percorrer o vetor n – 1 vezes, a cada passagem fazendo ir para inicio o menor elemento da sequência. Esse tipo de movimentação monstra na figura 1. Esse algoritmo lembra muito de uma forma de bolhas que procuram seu próprio nível e não é recomendado para vetores com vários elementos. (Quinn, 2003)


Figura 1: Ilustração do funcionamento do algoritmo Bubble Sort (Junior, 2008)

O bubble sort usa a compração e troca como estratégia, isso é aplicada em várias iterações sobre os dados as serem ordenados. Irei falar um pouco do algoritmo seqüencial. (Quinn, 2003)
Começando do inicio onde se deseja ordenar, isso de forma crescente, um vetor de números nas seguintes posições: x0, x1, …, xn-1, xn. Esse algoritmo inicia comparando o número que se encontra na posição x0 com o da posição x1, e troca quando necessário os números de maneira a ficar o maior da posição x1. Em seguida, repete o mesmo procedimento para as posições x1 e x2, onde na posição x2 ficará o maior dos números que se encontranas posições x1 e x2. Este processo é repetido de forma análoga até chegar à comparação entre as posições xn-1 e xn. Este processo anterior de comparações e trocas será considerado uma fase do algoritmo, sendo o algoritmo bubble sort constituído, na pior das hipóteses, por n-1 fases semelhantes à anterior. (Wilkinson e Allen)

3.2 – Merge Sort
O Merge Sort é um algoritmo de ordenação que consiste em ir separando em metades uma lista de elementos, até ficando com todos os elementos separados. O objetivo é de dividir para conquistar. Quando os elementos tiverem separados, o algoritmo procede à sua junção (merge), voltando no final uma única lista com todos elementos ordenados. (Goodrich, 2004)
Considerando uma lista de quatro elementos sem ordem alguma, e que se quiser ordenar de forma crescente todos os seus elementos.
Em todo o processo da divisão da lista, não é feita qualquer computação sobre os elementos e sua ordem na lista, e a primeira lista de quatro elementos é apenas separada em metade, ficando duas listas, sendo de seguida o método repetido, ficando todos os elementos separados. (Amato op. Cit.)
É nessa fase da junção (merge) que os elementos são ordenados de forma pretendida pelo algoritmo. No caso, para ordenar de forma crescente, o algoritmo pega os dois primeiros elementos e os junta numa lista, ficando o menor valor na primeira posição e o maior na segunda posição. Para os dois últimos elementos que sobram, é utilizado o mesmo método. Este processo é repetido para duas listas criadas anteriormente, juntando os elementos de cada uma dessas duas listas numa única lista, ficando assim uma lista ordenada de forma crescente. (Amato op. Cit.)
A seguir uma figura do funcionamento do algoritmo merge sort.

Figura 2: Ilustração dofuncionamento do algoritmo Merge Sort (Junior, 2008)

3.3 – Quick Sort
O Quick Sort é um algoritmo recursivo que tem como base a comparação de valores para ordenar uma lista de números desordenada. Foi inscrito por C.A.R Hoare em 1960 e publicado em 1962. Quando é passada uma lista de números, o algoritmo seleciona um número dessa lista, tornando-se o pivot. Depois disso, a lista é partida em duas sub-lista: uma lista que tem números inferiores ao pivot, e outra lista com números bem superiores. Chama-se depois a si mesma recursivamente para ordenar as duas sub-listas. A função retorna a concatenação da primeira lista, pivot e segunda lista. (Tsigas e Zhang, 2003)
Esse algoritmo é o mais rápido que tem entre os de ordenação interna para uma ampla variedade de situações. Porém em raras instâncias especiais ele é um pouco lento. Adota-se a estratégia de dividir para conquistar o funcionamento que resume-se a dividir o problema de ordenar um vetor de n posições em dois outros menores. (Ziviani, 2007)
A figura 3 monstra como funciona o algoritmo Quick Sort.

Figura 3: Ilustração do funcionamento do Quick Sort (Junior, 2008)
4-Resultados e Discussão

Devido ao tempo para entregar esse trabalho não foi possível realizar os testes, sendo tirados os testes de um site que se encontra nas referencias bibliográficas. (Santos, 2008) 
Nesse site que tirei os testes foram testados com 6 algoritmos, eu usarei nos testes 3 algoritmos: bubble sort, merge sort e quick sort, sendo:
1. Bubble Sort
2. Merge Sort
3. Quick Sort
Para cada algoritmo de ordenação foi testado um tamanho diferente de vetor, sendo: 100, 1000, 10000 e 100000 e para cada tamanho um tipo diferente, sendo: Elementos Ordenados, Quase Ordenados, Aleatórios eInversamente Ordenados.

4.1-Vetor Ordenado
As tabelas a seguir mostram o número de atribuições, comparações e tempo de execução em um vetor ordenado os algoritmos.

Vetor Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Atributo | Atributo | Atributo | Atributo | Atributo |
Bubble | 0 | 0 | 0 | 0 | 0 |
Merge | 40 | 700 | 10000 | 140000 | 1700000 |
Quick | 27 | 283 | 2871 | 29167 | 286372 |
Tabela 1: Atribuições para um vetor ordenado (Santos, 2009)

Vetor Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Comparação | Comparação | Comparação | Comparação | Comparação |
Bubble | 9 | 99 | 999 | 9999 | 99999 |
Merge | 21 | 372 | 5052 | 71712 | 877968 |
Quick | 45 | 840 | 12782 | 177511 | 1828462 |
Tabela 2: Comparações para um vetor ordenado (Santos, 2009)
Vetor Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Tempo | Tempo | Tempo | Tempo | Tempo |
Bubble | 0.000002 | 0.000003 | 0.000009 | 0.000079 | 0.000806 |
Merge | 0.000004 | 0.000012 | 0.000486 | 0.001624 | 0.019310 |
Quick | 0.000013 | 0.000013 | 0.000114 | 0.001382 | 0.013914 |
Tabela 3: Tempo de execução para um vetor ordenado (Santos, 2009)

A seguir são apresentados os gráficos com o número de atribuições e comparações em um vetor ordenado para os algoritmos.


Figura 4: Gráficos de atribuições 1 (Santos, 2009)





Figura 5: Gráficos de comparações 1 (Santos, 2009)

4.2-Vetor Quase Ordenado
As tabelas a seguir representam o números de atribuições e tempo de execução em um vetor quase ordenado os algoritmos.

Vetor Quase Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Atributo |Atributo | Atributo | Atributo | Atributo |
Bubble | 3 | 1155 | 175656 | 16936458 | 435576432 |
Merge | 40 | 700 | 10000 | 140000 | 1700000 |
Quick | 27 | 326 | 3626 | 40888 | 403955 |
Tabela 4: Atribuições para um vetor quase ordenado (Santos, 2009)

Vetor Quase Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Comparação | Comparação | Comparação | Comparação | Comparação |
Bubble | 17 | 4209 | 498510 | 49985684 | 65833800 |
Merge | 22 | 504 | 8154 | 116662 | 1076802 |
Quick | 45 | 865 | 13127 | 162276 | 162276 |
Tabela 5: Comparações para um vetor quase ordenado (Santos, 2009)

Vetor Quase Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Tempo | Tempo | Tempo | Tempo | Tempo |
Bubble | 0.000002 | 0.000045 | 0.004870 | 0.549886 | 26.240775 |
Merge | 0.000004 | 0.000015 | 0.000155 | 0.002483 | 0.029665 |
Quick | 0.000004 | 0.000014 | 0.000160 | 0.001602 | 0.018154 |
Tabela 6: Tempo de execução para um vetor quase ordenado (Santos, 2009)

A seguir são representados os gráficos com número de atribuições e comparações em um vetor quase ordenado para os algoritmos.


Figura 6: Gráficos de atribuições 2 (Santos, 2009)








Figura 7: Gráficos de comparações 2 (Santos, 2009)

4.3-Vetor Aleatório
As tabelas a seguir apresentam o número de atribuições, comparações e tempo de execução em um vetor aleatório para os algoritmos.

Vetor Aleatório |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Atributo | Atributo | Atributo | Atributo | Atributo |
Bubble | 39 | 6714 | 664107 | 68328030 | 1810376450 |
Merge | 40 | 700 | 10000 | 140000 | 1700000 |
Quick |27 | 439 | 6192 | 79301 | 970996 |
Tabela 7: Atribuições para um vetor aleatório (Santos, 2009)

Vetor Aleatório |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Comparação | Comparação | Comparação | Comparação | Comparação |
Bubble | 45 | 4905 | 498905 | 49978710 | 704930378 |
Merge | 21 | 560 | 8700 | 123472 | 1564552 |
Quick | 45 | 924 | 12127 | 155573 | 1780578 |
Tabela 8: Comparações para um vetor aleatório (Santos, 2009)

Vetor Aleatório |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Tempo | Tempo | Tempo | Tempo | Tempo |
Bubble | 0.000002 | 0.000081 | 0.008100 | 0.912763 | 81.658714 |
Merge | 0.000004 | 0.000016 | 0.000184 | 0.002505 | 0.045945 |
Quick | 0.000004 | 0.000018 | 0.000178 | 0.002246 | 0.026545 |
Tabela 9: Tempo de execução para um vetor aleatório (Santos, 2009)

A Seguir são apresentados os gráficos com o número de atribuições e comparações em um vetor aleatório para os algoritmos.


Figura 8: Gráficos de atribuições 3 (Santos, 2009)


Figura 9: Gráfico de Comparações 3 ( Santos, 2009)

4.4-Vetor Inversamente Ordenado
As tabelas a seguir apresentam o número de atribuições, comparações e tempo de execução em um vetor inversamente ordenado para os algoritmos.

Vetor Inversamente Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Atributo | Atributo | Atributo | Atributo | Atributo |
Bubble | 135 | 14847 | 1498500 | 149984142 | 2114940093 |
Merge | 40 | 700 | 10000 | 140000 | 1700000 |
Quick | 27 | 433 | 4371 | 44032 | 435040 |
Tabela 10: Atribuições para um vetor inversamente ordenado (Santos, 2009)

Vetor Inversamente Ordenado |
Elementos | 10 | 100 | 1000| 10000 | 100000 |
| Comparação | Comparação | Comparação | Comparação | Comparação |
Bubble | 45 | 4950 | 499500 | 49995000 | 704930378 |
Merge | 15 | 316 | 4932 | 64749 | 816361 |
Quick | 45 | 754 | 11802 | 166712 | 1723642 |
Tabela 11: Comparações para um vetor inversamente ordenado (Santos, 2009)

Vetor Inversamente Ordenado |
Elementos | 10 | 100 | 1000 | 10000 | 100000 |
| Tempo | Tempo | Tempo | Tempo | Tempo |
Bubble | 0.000003 | 0.000099 | 0.010459 | 1.149.139 | 111.727621 |
Merge | 0.000003 | 0.000011 | 0.000112 | 0.001522 | 0.021986 |
Quick | 0.000004 | 0.000018 | 0.000118 | 0.001527 | 0.015736 |
Tabela 12: Tempo de execução para um vetor inversamente ordenado (Santos, 2009)

A seguir são apresentados os gráficos com o número de atribuições e comparações em um vetor inversamente ordenado para os algoritmos.


Figura 10: Gráficos de atribuições 4 (Santos, 2009)




Figura 11: Gráfico de Comparações 4 ( Santos, 2009)

4.5-Vantagens e Desvantagens
Agora citarei algumas vantagens e desvantagens dos algoritmos Bubble Sort, Merge Sort e Quick Sort em cada tipo: vetor ordenado, quase ordenado, aleatório e inversamente ordenado. 

Vetor Ordenado |
| Vantagens | Desvantagens |
Bubble | Fácil Implementação | Exige um número maior de comparações |
Merge | Útil para ordenação externa | Mais lento do que o Quick Sort |
Quick | Muito rápido | Não é estável |
Tabela 13: Vantagens e Desvantagens do Vetor Ordenado

Vetor Quase Ordenado |
| Vantagens | Desvantagens |
Bubble | Simplicidade do Algoritmo | Lentidão |
Merge | Aplicações com restrições de tempo | Utiliza memória auxiliar |
Quick | Muito rápido, emmédia | Pior caso de comparações |
Tabela 14: Vantagens e Desvantagens do Vetor Quase Ordenado

Vetor Aleatório |
| Vantagens | Desvantagens |
Bubble | Algoritmo Estável | Ordem de complexidade quadrática |
Merge | Fácil Implementação | Alto consumo de memória |
Quick | Extremamente Eficiente | Implementação difícil |
Tabela 15: Vantagens e Desvantagens do Vetor Aleatório

Vetor Inversamente Ordenado |
| Vantagens | Desvantagens |
Bubble | O vetor já estava ordenado antes de terminar todas as iterações | O fato de o arquivo já estar ordenado não ajuda em nada |
Merge | Mais rápido na comparação em relação ao Bubble e Quick Sort | Mais lento no atributo do que o Quick Sort |
Quick | Velocidade igual ao do vetor ordenado | Processo lento |
Tabela 16: Vantagens e Desvantagens do Vetor Inversamente Ordenado













5-Considerações Finais

Este trabalho me possibilitou o aprofundamento mais detalhados dos algoritmos de ordenação, visto que com a análise dos números dos atributos, comparações e tempo foram bem eficientes. Pelos resultados que vi, verifiquei que os três algoritmos Bubble Sort, Merge Sort e Quick Sort são bem eficientes
Entre os três algoritmos, porém verifiquei que o Bubble Sort é bem mais lento em comparado com Merge Sort e Quick Sort. O mais rápido é o Merge Sort, mas não é o mais eficiente para ordenar vetores de grandes dimensões, o Quick Sort é o mais eficiente para esse tipo de ordenação.
O algoritmo Bubble Sort foi verificado que é bom para inserir a verificação de ordenação, já o algoritmo Merge Sort foi verificado que para vetores até 1000 posições ele é o mais rápido, mas vetores acima de 1000 posições o Quick Sort se torna o mais rápido,portanto o ele é o mais eficiente dentre os três descrito no trabalho.













6-Referencias Bibliográficas

Amato, N. M.; Iyer, R.; Sundaresan, S.; Wu, Y.. A Comparison of Parallel Sorting Algorithms on Different Architectures, 1988.
Cormen H., Thomas; Leiserson E., Charles; Rivest L., Ronald; Stein, Clifford. Algoritmos, Teoria e Prática. Edição 1. Editora: Campus, 2002.
Feofiloff, Paulo. Algoritmos em Linguagem C, 2009
Goodrich, Michel T.. Projeto De Algoritmos: Fundamentos, Análise e Exemplos da Internet, 2004.
Junior, Carlos do Nazaré. Algoritmo de Estrutura de Dados, Métodos de Ordenação Interna, 2008. 
Disponível em: http://www.decom.ufop.br/menotti/aedI082/tps/tp3-sol1.pdf
Acessado em: 02/03/2012
Medina, Marco. Algoritmos e Programação - Teoria e Prática, 2005.
Niklaus. Wirth, Algoritmos e Estruturas de Dados. Editora Prentice Hall, 1986.
Quinn, Micheal. Parallel programming in C with MPI and OpenMP, 2003.
Santos, Luiz Henrique. Algoritmo de Estrutura de Dados, Análise de Desempenho de Algoritmos de Ordenação por Comparação e suas Variações e Otimizações, 2009 .
Disponível em:www.decom.ufop.br/menotti/aedI091/tps/tp5.pdf 
Acessado em: 02/03/2012
Sedgewick, Robert; Wayne, Kevin. Algorithms. 4th Edition, 2011.
Tsigas, Philippas and Zhang, Yi. A Simple, Fast Parallel Implementation of Quicksort and its Performance Evaluation on SUN Enterprise 10000, 2003.
Wilkinson, Barry; Allen, Michel. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, Prentice Hall, 2005.
Ziviani, Nivio. Projeto de Algoritmos: com implementações em Pascal C. Edição 2, 2004.
Ziviani, Nivio. Projeto de Algoritmos com implementação em C++ e Java. THOMSON Learning. Edição 2, 2007.

...