Analise Experimental e Assintotica de Algoritmos de Ordenacao

Prévia do material em texto

Universidade Estadual Ju´lio de Mesquita Filho
FCT-UNESP
Projeto e Ana´lise de Algoritmos
Ana´lise experimental e assinto´tica de algoritmos de ordenac¸a˜o
Gabriel de Oliveira Almeida
Gustavo Lopes Santana
Joa˜o Victor Silva Menezes
Presidente Prudente - SP
Suma´rio
1 Introduc¸a˜o 3
2 Ana´lise dos Algoritmos de Ordenac¸a˜o 3
2.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Bubble Sort Melhorado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3.1 QuickSort (Pivoˆ Primeiro Elemento da Lista) . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3.2 Quick Sort (Pivoˆ Elemento Central da Lista) . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.6 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.7 Heap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.8 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Comparac¸o˜es e Discusso˜es 8
31 Introduc¸a˜o
As operac¸o˜es de ordenac¸a˜o de dados sa˜o de suma importaˆncia para sistemas computacionais, a escolha do
me´todo mais eficiente tem grande impacto no desempenho de uma determinada aplicac¸a˜o, ja´ que, cada algoritmo
apresenta uma vantagem particular sobre o outro.
Ordenar corresponde ao processo de rearranjar um conjunto de objetos em um ordem ascendente ou decrescente.
O objeto principal da ordenac¸a˜o e´ facilitar a recuperac¸a˜o posterior de itens do conjunto ordenado.
A escolha do tipo para a chave e´ arbitra´ria. Qualquer tipo sobre o qual exista uma regra de ordenac¸a˜o bem-
definida pode ser utilizado. As ordens nume´rica e alfabe´tica sa˜o as usuais.
Este trabalho tem como pauta demonstrar testes para comparac¸a˜o entre algoritmos de ordenac¸a˜o de valores
em ordem crescente, decrescente e aleato´ria, analisando a performance sobre cada uma delas, que sera´ realizado
obtendo o tempo de execuc¸a˜o que desse modo, tambe´m implica na apresentac¸a˜o da ana´lise assinto´tica, explicitando
o rendimento de cada algoritmo.
Observaremos o rendimento dado as situac¸o˜es possı´veis para execuc¸a˜o, descritas como: Melhor caso: vetor
disposto de forma a reduzir o numero de comparac¸o˜es efetuadas pelo algoritmo. Pior caso: vetor disposto de
formar executar comparac¸o˜es e permutar em todas as ocasio˜es possı´veis. Caso me´dio: disposic¸a˜o do vetor de
forma a evitar o melhor caso e pior caso, sendo considerado a possı´vel forma de execuc¸a˜o para mais de 90% dos
testes.
A quantidade de posic¸o˜es do vetor bem como os valores nume´ricos das chaves sa˜o os mesmos para todos os
algoritmos. Tais vetores sa˜o gerados aleatoriamente pela func¸a˜o rand(), ordenado em ordem crescente com valor
inicial de 1 ate´ o tamanho do vetor (1000, 5000, 10000, 15000, 20000, 25000), e tambe´m em ordem decrescente
com valores iniciais do tamanho do vetor ate´ 1. Cada algoritmo sera´ executado mais de uma vez, ficara´ dentro de
um lac¸o de repetic¸a˜o, e sera´ obtido o tempo (milisegundos) capturado pela func¸a˜o clock() do total de execuc¸a˜o do
algoritmo (30 vezes). Os testes sera˜o realizados no mesmo computador, Intel i5-5200U, 8GB RAM, placa de vı´deo
integrada, garantindo assim que as condic¸o˜es sejam as mesmas para todos os algoritmos, desse modo, permite que
resultados obtidos sejam confia´veis.
Os algoritmos utilizados sera˜o: BubbleSort, BubbleSort Melhorado, QuickSort (com pivoˆ sendo o valor inicial
e central do vetor), InsertionSort, ShellSort, SelectionSort, HeapSort e MergeSort, implementado em linguagem
C.
2 Ana´lise dos Algoritmos de Ordenac¸a˜o
2.1 Bubble Sort
O me´todo Bubble Sort requer comparac¸o˜es com a posic¸o˜es adjacente e se for necessa´rio, a maior chave que
estiver fora de posic¸a˜o, havera´ a permutac¸a˜o entre suas posic¸o˜es, por isso, pode-se garantir que que o maior item
tera´ sido deslocado para u´ltima posic¸a˜o do vetor. Para se obter o vetor ordenado, tera´ que repetir esse processo.
Apesar da facilidade de implementac¸a˜o e estabilidade, e mesmo assim, com qualquer vetor de entrada, orde-
nado, aleato´rio, inversamente ordenado, O algoritmo faz todas as verificac¸o˜es possı´veis.
Analise de Desempenho
1. Melhor Caso: O(n2)
2. Caso Me´dio: O(n2)
3. Pior Caso: O(n2)
Figura 1. Grafico de Desempenho: Bubble Sort
2.2 Bubble Sort Melhorado
o Algoritmo segue a ideˆntico ao Bubble Sort, pore´m sua versa˜o melhorada, ha´ verificac¸a˜o se o vetor ja´ estiver
ordenado ocorre a interrupc¸a˜o do algoritmo instantaneamente.
Analise de Desempenho
1. Melhor Caso: O(n)
2. Caso Me´dio: O(n2)
3. Pior Caso: O(n2)
Figura 2. Grafico de Desempenho: Bubble Sort Melhorado
2.3 Quick Sort
Algoritmo Quick Sort e´ ordenar um conjunto com n itens em dois problemas menores (particionamento). A
seguir os problemas menores sa˜o ordenados independente e depois os resultados sa˜o combinados para produzir a
soluc¸a˜o do problema maior.
Utilizando o paradigma de divisa˜o (pivoˆ) e conquista (recursivamente divide em partes para divisa˜o), a escolha
do pivoˆ - elemento que sera´ utilizado, para troca do conjunto, ha´ troca caso os elementos forem maiores que ele -
influencia demasiadamente na eficieˆncia, pode ser executado, se balanceado, assintoticamente rapido.
Por isso, esse processo e´ realizado em treˆs passos: dividir, conquistar e combinar.
2.3.1 QuickSort (Pivoˆ Primeiro Elemento da Lista)
Leva ao seu pior caso, pois as partic¸o˜es sera˜o desiguais, a chamada para ordenando um por cada chamada
recursiva.
2.3.2 Quick Sort (Pivoˆ Elemento Central da Lista)
Obte´m melhora significativa quando dividido em duas partes iguais, ja´ que consegue alcanc¸ar os melhores casos
Analise de Desempenho
O pior caso e´ quando pivoˆ e´ o maior/menor elemento da partic¸a˜o, enquanto o melhor caso e´ quando o pivoˆ
divide a lista em duas partic¸o˜es iguais.
1. Melhor Caso: O(n log n)
2. Caso Me´dio: O(n log n)
3. Pior Caso: O(n2)
Figura 3. Quick Sort com Pivoˆ Primeiro Elemento
Figura 4. Quick Sort com Pivoˆ Central
2.4 Insertion Sort
O algoritmo Insertion Sort, em cada passo, a partir da posic¸a˜o i do vetor, para i=2, o i-e´simo item da sequeˆncia
fonte e´ selecionado e transferido para a sequeˆncia destino, sendo inserido no seu lugar o apropriado.
O nu´mero mı´nimo de comparac¸o˜es e movimentos ocorre quando os itens esta˜o originalmente em ordem, e o
nu´mero ma´ximo ocorre quando os itens esta˜o originalmente na ordem reversa, o que indica um comportamento
natural para o algoritmo. Para arquivos ja´ ordenados o algoritmo descobre a um custo 0(n) que cada item ja´ esta´
no seu lugar. Logo, o me´todo da inserc¸a˜o e´ o me´todo a ser utilizado quando o arquivo esta´ ”quase”ordenado. E
tambe´m um bom me´todo quando se deseja adicionar uns poucos itens a um arquivo ja´ ordenado e depois obter um
outro arquivo ordenado: neste caso o custo e´ linear. Ale´m disso, o me´todo de ordenac¸a˜o por inserc¸a˜o e´ esta´vel,
pois ele deixa os registros com chaves iguais na mesma posic¸a˜o relativa.
Analise de Desempenho
1. Melhor Caso: O(n)
2. Caso Me´dio: O(n2)
3. Pior Caso: O(n2)
Figura 5. Insertion Sort
2.5 Shell Sort
O me´todo ShellSort pode ser considerado o refinamento do me´todo Insertion Sort. O que diferencia pelo fato
de no lugar de considerar o vetor ordenado, como u´nico segmento, considera va´rios segmentos sendo aplicado o
algoritmo de Insertion Sort emcada um desses segmentos.
O ShellSort permite trocas de registros que esta˜o distantes um do outro.
O tempo de execuc¸a˜o do algoritmo e´ sensı´vel a` ordem inicial do arquivo.
Analise de Desempenho
1. Melhor Caso: . . .
2. Caso Me´dio: . . .
3. Pior Caso: . . .
A complexidade depende do tamanho do salto escolhido. Existem teorema que mostram algumas complexida-
des para o Shellsort.
Teorema 1 1. Para saltos de 1, 3, 7, . . . , 2k − 1, o algoritmo tem complexidade O(n√n).
Teorema 1 2. Para saltos de 1, 2, 3, 4, 6, . . . , 2p3q , o algoritmo tem complexidade O(n(log n)2).
Figura 6. Shell Sort
2.6 Selection Sort
Selection Sort tem como sua lo´gica, selecionar um elemento e coloca-lo na sua posic¸a˜o correta. O Algoritmo
seleciona o menor elemento da sequencia, deste modo, sa˜o comparados n − 1 elemento, e em seguida n − 2, e
assim por diante, para ser colocado em seu devido lugar, e assim organizando-o a entrada.
Analise de Desempenho
1. Melhor Caso: O(n2)
2. Caso Me´dio: O(n2)
3. Pior Caso: O(n2)
Figura 7. Selection Sort
2.7 Heap Sort
O algoritmo Heap Sort tem o mesmo principio do Selection Sort, pore´m utiliza o heap para realizar a ordenac¸a˜o.
Analise de Desempenho
1. Melhor Caso: O(n log n2)
2. Caso Me´dio: O(n log n2)
3. Pior Caso: O(n log n2)
Figura 8. Heap Sort
2.8 Merge Sort
O algoritmo Merge Sort utiliza tambe´m o paradigma Divisa˜o e Conquista, por meio da divisa˜o, intercalac¸a˜o
e unia˜o dos n elementos existentes. Em outras palavras, a estrutura a ser reordenada sera´, de forma recursiva,
subdividida em estruturas menores ate´ que na˜o seja mais possı´vel fazeˆ-lo. Em seguida, os elementos sera˜o organi-
zados de modo que cada subestrutura ficara´ ordenada. Feito isso, as subestruturas menores (agora ordenadas) sera˜o
unidas, sendo seus elementos ordenados por meio de intercalac¸a˜o. O mesmo processo repete-se ate´ que todos os
elementos estejam unidos em uma u´nica estrutura organizada.
Analise de Desempenho
1. Melhor Caso: O(n log n2)
2. Caso Me´dio: O(n log n2)
3. Pior Caso: O(n log n2)
Figura 9. Merge Sort
3 Comparac¸o˜es e Discusso˜es
Comparando esses gra´ficos e´ possı´vel notar que os algoritmos testados realmente possui um comportamento
que segue de acordo com suas complexidades ditas anteriormente e sua eficieˆncia varia conforme o tamanho do
vetor utilizado e sua ordem inserida
1. Para os vetores aleato´rio temos que o bubble sort (normal e melhorado), selection e insertion gastam um
tempo maior enquanto os demais possui um tempo pouco significativo comparado com estes. [ver figura 10]
2. Para os vetores ordenado bubble, quick(pivoˆ inicial) e selection, tiveram o pior desempenho em comparac¸a˜o
com os outros.[ver figura 11]
3. Para os vetores inverso bubble(normal e melhorado), insertion, quick(inicial) e selection apresentam os
piores tempos.[ver figura 12]
Figura 10. Todos os algoritmos Aleato´rios
Figura 11. Todos os algoritmos Ordenados
Figura 12. Todos os algoritmos Inversos
Refereˆncias
[1] J. da Silva Nascimento, P. M. Mozzaquatro, and R. L. Antoniazzi. Ana´lise e comparac¸a˜o de algoritmos implementados em
java. Simpo´sio de Pesquisa e Desenvolvimento em Computac¸a˜o, 1(1), 2016.
[2] M. A. Guerine. Algoritmos de ordenac¸a˜o.
[3] J. E. Souza, J. V. G. Ricarte, and N. C. de Almeida Lima. Algoritmos de ordenac¸a˜o: Um estudo comparativo. Anais do
Encontro de Computac¸a˜o do Oeste Potiguar ECOP/UFERSA, 1, 2017.
[4] N. Ziviani et al. Projeto de algoritmos: com implementac¸o˜es em Pascal e C, volume 2. Thomson, 2004.
	Introdução
	Análise dos Algoritmos de Ordenação
	Bubble Sort
	Bubble Sort Melhorado
	Quick Sort
	QuickSort (Pivô Primeiro Elemento da Lista)
	Quick Sort (Pivô Elemento Central da Lista)
	Insertion Sort
	Shell Sort
	Selection Sort
	Heap Sort
	Merge Sort
	Comparações e Discussões