Analise Experimental e Assintotica de Algoritmos de Ordenacao

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 em