Relatorio_ED

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.