Análise de Algoritmos de Ordenação Interna

Universidade Federal de Ouro Preto

Instituto de Ciências Exatas e Biológicas

Departamento de Computação

ALGORITMOS E ESTRUTURAS DE DADOS

Quinto Trabalho Prático

Johnnatan Messias Peixoto Afonso

Professor - David Menotti

Monitor - Kayran dos SantosMonitor - Pedro Ismar Silva Souto

Ouro Preto

4 de dezembro de 2009

Sumário

1 Introdução 1

1.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Especi�cação do problema . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Algoritmo e estruturas de dados 2

2.1 TAD - Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.1.1 Assinatura das funções . . . . . . . . . . . . . . . . . . . . . . 22.1.2 QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.1.3 QuickSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . 42.1.4 HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.5 HeapSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . 72.1.6 MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1.7 Mergesort Otimizado . . . . . . . . . . . . . . . . . . . . . . . 102.1.8 SelectSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.1.9 SelectSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . 112.1.10 InsertSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.1.11 InsertSort com o elemento Sentinela . . . . . . . . . . . . . . . 122.1.12 InsertSort Implementado através de Cursores . . . . . . . . . . 132.1.13 BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.14 BubbleSort com Troca . . . . . . . . . . . . . . . . . . . . . . 16

3 Grá�cos e Tabelas 18

3.1 Função QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.1.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.1.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 QuickSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.3.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 24

3.4 HeapSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.4.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.4.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.4.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5 MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.5.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.5.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.5.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 28

3.6 MergeSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.6.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.6.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.6.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 30

3.7 SelectSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2

3.7.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.7.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.7.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 33

3.8 SelectSort Otimizado . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.8.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.8.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.8.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 35

3.9 InsertSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.9.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.9.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.9.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 37

3.10 InsertSort com o elemento Sentinela . . . . . . . . . . . . . . . . . . . 383.10.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.10.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.10.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 39

3.11 InsertSort por Cursores . . . . . . . . . . . . . . . . . . . . . . . . . . 403.11.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.11.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.11.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 42

3.12 BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.12.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.12.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.12.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 44

3.13 BubbleSort com Troca . . . . . . . . . . . . . . . . . . . . . . . . . . 453.13.1 Atribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.13.2 Comparações . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.13.3 Tempo de Execução . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Análise de complexidade dos algoritmos 48

4.1 Sort.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.1 Função QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.2 HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.3 MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.4 SelectSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.5 InsertSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.6 BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 Testes 49

6 Conclusão 51

Lista de Programas

1 Assinaturas do Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 QuickSort-O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 HeapSort-O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3

6 MergeSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Mergesort-O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 SelectSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 SelectSort-O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1110 InsertSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1211 InsertSort-OS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1312 InsertSort-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1313 TAD TLista.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1314 Implementações do TLista.c . . . . . . . . . . . . . . . . . . . . . . . 1415 BubbleSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616 BubbleSort-T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4

1 Introdução

Esse trabalho consiste na análise dos algoritmos de ordenação para avaliar onúmero de comparações, bem como o número de atribuições e também o tempo"de relógio"que cada algoritmo em diferentes elementos e métodos de ordenação dosvetores:

• Random - Os elementos do vetor foram introduzidos de forma aleatória, ouseja, estando, portanto, desordenado;

• Sorted - Os elementos do vetor estão ordenados;

• Almost Sorted - Os elementos do vetor estão quase ordenados;

• Inverted - Os elementos do vetor estão de forma ordenada invertida.

Assim, para os testes de ordenação, foram utilizados os seguintes métodos de or-denação: QuickSort, QuickSort Otimizado, HeapSort, HeapSort Otimizado, Merge-Sort, Mergesort Otimizado, SelectSort, SelectSort Otimizado, InsertSort, InsertSortcom o elemento Sentinela, InsertSort implementado através de cursores, BubbleSorte BubbleSort com Troca.

1.1 Considerações iniciais

• Ambiente de desenvolvimento do código fonte: Microsoft Visual Studio 2008Professional.

• Linguagem utilizada: Linguagem C.

• Para os testes, utilizei um notebook rodando o Microsoft Windows 7 Profes-sional 64 bits, com a seguinte con�guração: Proc. Turion MK-36, 2GB RAM,portanto o tempo de "relógio"dos testes será diferente quando o programa forexecutado em outro computador com uma con�guração diferente da citadaanteriormente.

• Ambiente de desenvolvimento da documentação: TeXnicCenter 1.0 SRC-Editorde LATEX.

1.2 Especi�cação do problema

O objetivo deste trabalho é analisar algoritmos de ordenação por comparação esuas variações e otimizações. Essa análise será dividida em duas partes.

Na primeira, a análise será sobre os algoritmos de ordenação simples (de ordem decomplexidade O(n2) - i.e., BubbleSort, SelectSort, InsertSort e algumas variações).Você deverá implementar os três algoritmos citados e implementar variações dessesalgoritmos de forma que através de análises de experimentos você possa analisar:

• Se vale a pena inserir a veri�cação de ordenação (houve troca) no algoritmoBubbleSort;

• Se vale a pena usar o algoritmo InsertSort com elemento sentinela;

1

• Se vale a pena inserir uma veri�cação (Min == i) para evitar a troca, nométodo SelectSort.

A segunda parte será sobre os algoritmos de ordenação por comparação ditose�cientes, como MergeSort, HeapSort e QuickSort, que tem complexidade de tempode O( n log n ). São fornecidas implementações convencionais e versões otimizadas.Aproveite os algoritmos implementados por você e veri�que:

• Até que tamanho de entrada, vale a pena usar algoritmos O(n2) com relaçãoa algoritmos O(n log n).

2 Algoritmo e estruturas de dados

Foi selecionado o TAD, Tipo Abstrato de Dados, Sort.h para representar as im-plementações dos algoritmos de ordenação citados na introdução deste documento.

2.1 TAD - Sort

Para representar as implementações dos algoritmos de ordenação foi criado umTAD Sort.h

2.1.1 Assinatura das funções

Abaixo as assinaturas do Sort.h.

#include "Array . h"

//Funções de ordenação agrupadasvoid QuickSort (TArray∗ ,double∗ , double∗ ) ;

5 void QuickSortO (TArray∗ ,double∗ , double∗ ) ;

void HeapSort (TArray∗ ,double∗ , double∗ ) ;void HeapSortO (TArray∗ ,double∗ , double∗ ) ;

10 void MergeSort (TArray∗ ,double∗ , double∗ ) ;void MergeSortO (TArray∗ ,double∗ , double∗ ) ;

void BubbleSort (TArray∗ ,double∗ ,double∗ ) ;void BubbleSortT (TArray∗ ,double∗ ,double∗ ) ;

15

void Se l e c t So r t (TArray∗ ,double∗ ,double∗ ) ;void Se lectSortO (TArray∗ ,double∗ ,double∗ ) ;

void I n s e r t S o r t (TArray∗ ,double∗ ,double∗ ) ;20 void InsertSortOS (TArray∗ , double∗ , double∗ ) ;

Programa 1: Assinaturas do Sort

2.1.2 QuickSort

Esse método de ordenação tem por �nalidade dividir um problema em 2 sub-problemas de modo que facilite a resolução desses subproblemas e assim quandojuntar as soluções desses subproblemas teremos um problema maior solucionado,

2

isto é, ordenado. Esse algoritmo talvez seja o mais utilizado atualmente devido asua e�ciência em ordenação para um tamanho variável de elementos. Além disso,selecionamos um pivô, elemento para servir como base, ou seja, comparação com osoutros elementos para dividir os problemas, onde os elementos à esquerda do pivôsejam menores que os da direita. Obs.: Ele não é estável e majoritariamente suaordem de complexidade é O(nlog(n)).

// QuickSortvoid Par t i t i on ( int l e f t , int r i ght , int ∗ i , int ∗ j , TArray ∗pA, double ∗NAt,

double ∗NComp){

TItem pivot ,Aux ;5

∗ i=l e f t ;∗ j=r i gh t ;

(∗NComp)+=4;i f ( ( (pA−>Pos i t i on s [ l e f t ] . key > pA−>Pos i t i on s [ r i g h t ] . key ) && (pA−>

Pos i t i on s [ l e f t ] . key < pA−>Pos i t i on s [ ( r i g h t+l e f t ) / 2 ] . key ) ) | |10 ( (pA−>Pos i t i on s [ l e f t ] . key < pA−>Pos i t i on s [ r i g h t ] . key ) && (pA−>

Pos i t i on s [ l e f t ] . key > pA−>Pos i t i on s [ ( r i g h t+l e f t ) / 2 ] . key ) ) ){

p ivot = pA−>Pos i t i on s [ l e f t ] ; ( ∗NAt)++;}else

15 {(∗NComp)+=4;i f ( ( (pA−>Pos i t i on s [ l e f t ] . key < pA−>Pos i t i on s [ r i g h t ] . key ) && (pA−>

Pos i t i on s [ r i g h t ] . key < pA−>Pos i t i on s [ ( r i g h t+l e f t ) / 2 ] . key ) ) | |( (pA−>Pos i t i on s [ l e f t ] . key > pA−>Pos i t i on s [ r i g h t ] . key ) && (pA−>

Pos i t i on s [ r i g h t ] . key > pA−>Pos i t i on s [ ( r i g h t+l e f t ) / 2 ] . key ) ) ){

20 p ivot = pA−>Pos i t i on s [ r i g h t ] ; ( ∗NAt)++;}else

{p ivot = pA−>Pos i t i on s [ ( r i g h t+l e f t ) / 2 ] ; ( ∗NAt)++;

25 }}do

{while ( p ivot . key>pA−>Pos i t i on s [∗ i ] . key )

30 {(∗NComp)++;(∗ i )++;

}while ( p ivot . key<pA−>Pos i t i on s [∗ j ] . key )

35 {(∗NComp)++;(∗ j )−−;

}i f (∗ i<=∗j )

40 {Aux=pA−>Pos i t i on s [∗ i ] ; ( ∗NAt)++;pA−>Pos i t i on s [∗ i ]=pA−>Pos i t i on s [∗ j ] ; ( ∗NAt)++;pA−>Pos i t i on s [∗ j ]=Aux ; ( ∗NAt)++;(∗ i )++;

45 (∗ j )−−;}

3

}while (∗ i<=∗j ) ;}

50 void Sort ( int l e f t , int r i ght , TArray ∗pA, double ∗NAt, double ∗NComp){

int i , j ;Pa r t i t i on ( l e f t , r i ght , &i , &j ,pA,NAt ,NComp) ;i f ( l e f t <j )

55 Sort ( l e f t , j , pA,NAt ,NComp) ;i f ( i<r i gh t )

Sort ( i , r i ght ,pA,NAt ,NComp) ;}

60 void QuickSort (TArray ∗pA, double ∗NAt, double ∗NComp){

Sort (0 ,pA−>Size −1,pA,NAt ,NComp) ;}

Programa 2: QuickSort

2.1.3 QuickSort Otimizado

Para aperfeiçoar o QuickSort, só usamos o QuickSort para ordenar mais do que 20elementos, caso a quantidade de elementos seja menor, então chamamos o métodoSelectSort e ainda veri�camos se para que evite usar o maior elementos ou dosextremos como pivô. Assim haverá uma melhora signi�cativa no tempo de execução.

// QuickSortOvoid QuickSortO (TArray ∗pA, double ∗NAt, double ∗NComp){

int i , j ;5 TPilha Stack ;

TItemPAD l im i t s , l imitsAux ;int MaxStack = ( int ) ( 2 . ∗ ( l og ( ( f loat )pA−>Size ) / l og ( 2 . ) ) ) ;

FPVazia(&Stack , MaxStack ) ;10

l im i t s . l e f t = 0 ;l im i t s . r i g h t = pA−>Size −1;

while (1 )15 {

i f ( ( l im i t s . r i g h t − l im i t s . l e f t +1) > 20){

// Par t i t i onTItem pivot ,Aux ;

20 i=l im i t s . l e f t ; j=l im i t s . r i g h t ;(∗NComp)+=4;i f ( ( (pA−>Pos i t i on s [ l im i t s . l e f t ] . key > pA−>Pos i t i on s [ l im i t s . r i g h t

] . key ) && (pA−>Pos i t i on s [ l im i t s . l e f t ] . key < pA−>Pos i t i on s [ (l im i t s . r i g h t+l im i t s . l e f t ) / 2 ] . key ) ) | |

( (pA−>Pos i t i on s [ l im i t s . l e f t ] . key < pA−>Pos i t i on s [ l im i t s . r i g h t ] .key ) && (pA−>Pos i t i on s [ l im i t s . l e f t ] . key > pA−>Pos i t i on s [ (l im i t s . r i g h t+l im i t s . l e f t ) / 2 ] . key ) ) )

{25 p ivot = pA−>Pos i t i on s [ l im i t s . l e f t ] ; ( ∗NAt)++;

}

4

else

{(∗NComp)+=4;

30 i f ( ( (pA−>Pos i t i on s [ l im i t s . l e f t ] . key < pA−>Pos i t i on s [ l im i t s .r i g h t ] . key ) && (pA−>Pos i t i on s [ l im i t s . r i g h t ] . key < pA−>Pos i t i on s [ ( l im i t s . r i g h t+l im i t s . l e f t ) / 2 ] . key ) ) | |( (pA−>Pos i t i on s [ l im i t s . l e f t ] . key > pA−>Pos i t i on s [ l im i t s .

r i g h t ] . key ) && (pA−>Pos i t i on s [ l im i t s . r i g h t ] . key > pA−>Pos i t i on s [ ( l im i t s . r i g h t+l im i t s . l e f t ) / 2 ] . key ) ) )

{p ivot = pA−>Pos i t i on s [ l im i t s . r i g h t ] ; ( ∗NAt)++;

}35 else

{p ivot = pA−>Pos i t i on s [ ( l im i t s . r i g h t+l im i t s . l e f t ) / 2 ] ; ( ∗NAt)++;

}}

40

do

{while ( p ivot . key>pA−>Pos i t i on s [ i ] . key ){

45 (∗NComp)++;i++;

}while ( p ivot . key<pA−>Pos i t i on s [ j ] . key ){

50 (∗NComp)++;j−−;

}i f ( i<=j ){

55 Aux=pA−>Pos i t i on s [ i ] ; ( ∗NAt)++;pA−>Pos i t i on s [ i ]=pA−>Pos i t i on s [ j ] ; ( ∗NAt)++;pA−>Pos i t i on s [ j ]=Aux ; ( ∗NAt)++;i++;j−−;

60 }}while ( i<=j ) ;// Par t i t i on

i f ( l im i t s . l e f t < j )65 {

i f ( i < l im i t s . r i g h t ){

l imitsAux . l e f t = i ;l imitsAux . r i g h t = l im i t s . r i g h t ;

70 PEmpilha(&Stack ,& l imitsAux ) ;}

// l im i t s . l e f t = l im i t s . l e f t ;l im i t s . r i g h t = j ;

}75 else i f ( i < l im i t s . r i g h t )

{l im i t s . l e f t = i ;

// l im i t s . r i g h t = l im i t s . r i g h t ;}

80 else

5

{i f ( ! PEhVazia(&Stack ) )

PDesempilha(&Stack ,& l im i t s ) ;else

85 break ;}

}else

{90 // Se l e c t S o r t

int Min ;TItem aux ;for ( i = l im i t s . l e f t ; i < l im i t s . r i g h t ; i++){

95 Min = i ;for ( j = i + 1 ; j <= l im i t s . r i g h t ; j++){

(∗NComp)++;i f ( pA−>Pos i t i on s [ j ] . key < pA−>Pos i t i on s [Min ] . key )

100 Min = j ;}aux = pA−>Pos i t i on s [Min ] ; (∗NAt)++;pA−>Pos i t i on s [Min ] = pA−>Pos i t i on s [ i ] ; (∗NAt)++;pA−>Pos i t i on s [ i ] = aux ; (∗NAt)++;

105 }i f ( ! PEhVazia(&Stack ) )

PDesempilha(&Stack ,& l im i t s ) ;else

break ;110 }

}PLibera(&Stack ) ;

}

Programa 3: QuickSort-O

2.1.4 HeapSort

Baseia-se na construção de heaps que para a ordenação dos elementos, ondetrocando o elemento da posição inicial para a posição n, depois refazemos o heappara os próximos item até que os elementos estejam ordenados.

// HeapSortvoid RemakeHeap( int l e f t , int r i ght , TArray ∗pA, double ∗NAt, double ∗

NComp){

5 int i = l e f t , j ;TItem aux ;j = i ∗ 2 + 1 ;aux = pA−>Pos i t i on s [ i ] ; ( ∗NAt)++;while ( j <= r i gh t )

10 {i f ( j < r i gh t ){

(∗NComp)++;i f (pA−>Pos i t i on s [ j ] . key < pA−>Pos i t i on s [ j +1] . key )

6

15 j++;}(∗NComp)++;i f ( aux . key >= pA−>Pos i t i on s [ j ] . key )break ;

20 pA−>Pos i t i on s [ i ] = pA−>Pos i t i on s [ j ] ; ( ∗NAt)++;i = j ;j = i ∗ 2 + 1 ;

}pA−>Pos i t i on s [ i ] = aux ; ( ∗NAt)++;

25 }

void MakeHeap(TArray ∗pA, double ∗NAt, double ∗NComp){

int l e f t ;30 l e f t = pA−>Size / 2 ;

while ( l e f t >= 0){

RemakeHeap( l e f t , pA−>Size −1, pA,NAt , NComp) ;l e f t −−;

35 }}

void HeapSort (TArray ∗pA, double ∗NAt, double ∗NComp){

40 int l e f t , r i g h t ;TItem aux ;MakeHeap(pA,NAt ,NComp) ;l e f t = 0 ; r i g h t = pA−>Size −1;while ( r i g h t >= 0)

45 {aux = pA−>Pos i t i on s [ 0 ] ; ( ∗NAt)++;pA−>Pos i t i on s [ 0 ] = pA−>Pos i t i on s [ r i g h t ] ; ( ∗NAt)++;pA−>Pos i t i on s [ r i ght −−] = aux ; ( ∗NAt)++;RemakeHeap( l e f t , r i ght ,pA,NAt ,NComp) ;

50 }}

Programa 4: HeapSort

2.1.5 HeapSort Otimizado

Utiliza-se a versão não interativa, isto é, sem recursividade, para a ordenaçãodos elementos.

// HeapSortOvoid HeapSortO (TArray ∗pA, double ∗NAt, double ∗NComp){

int i , j ;5 int l e f t , r i g h t ;

TItem aux ;// MakeHeapl e f t = pA−>Size / 2 ;r i g h t = pA−>Size −1;

10 while ( l e f t >= 0){

// RemakeHeapi = l e f t ;

7

j = i ∗ 2 + 1 ;15 aux = pA−>Pos i t i on s [ i ] ; ( ∗NAt)++;

while ( j <= r i gh t ){

i f ( j < r i gh t ){

20 (∗NComp)++;i f (pA−>Pos i t i on s [ j ] . key < pA−>Pos i t i on s [ j +1] . key )j++;

}(∗NComp)++;

25 i f ( aux . key >= pA−>Pos i t i on s [ j ] . key )break ;

pA−>Pos i t i on s [ i ] = pA−>Pos i t i on s [ j ] ; ( ∗NAt)++;i = j ;j = i ∗ 2 + 1 ;

30 }pA−>Pos i t i on s [ i ] = aux ; ( ∗NAt)++;// RemakeHeapl e f t −−;

}35 // MakeHeap

l e f t = 0 ; r i g h t = pA−>Size −1;while ( r i g h t >= 0){

40 aux = pA−>Pos i t i on s [ 0 ] ; ( ∗NAt)++;pA−>Pos i t i on s [ 0 ] = pA−>Pos i t i on s [ r i g h t ] ; ( ∗NAt)++;pA−>Pos i t i on s [ r i ght −−] = aux ; ( ∗NAt)++;// RemakeHeapi = l e f t ;

45 j = i ∗ 2 + 1 ;aux = pA−>Pos i t i on s [ i ] ; ( ∗NAt)++;while ( j <= r i gh t ){

i f ( j < r i gh t )50 {

(∗NComp)++;i f (pA−>Pos i t i on s [ j ] . key < pA−>Pos i t i on s [ j +1] . key )j++;

}55 (∗NComp)++;

i f ( aux . key >= pA−>Pos i t i on s [ j ] . key )break ;

pA−>Pos i t i on s [ i ] = pA−>Pos i t i on s [ j ] ; ( ∗NAt)++;i = j ;

60 j = i ∗ 2 + 1 ;}pA−>Pos i t i on s [ i ] = aux ; ( ∗NAt)++;// RemakeHeap

}65 }

Programa 5: HeapSort-O

8

2.1.6 MergeSort

Consiste em dividir o problema em subproblemas, ou seja, em conjuntos, assimele ordena cada conjunto de maneira recursiva. Por �nal, ele junta os conjuntos numsó onde o novo conjunto maior está ordenado, isto é, o problema em ordenar umvetor está resolvido. Assim como o HeapSort, o MergeSort também é O(nlog(n)).

// MergeSortvoid Merge (TArray ∗pA, TArray ∗pAux , int i n i t 1 , int end1 , int i n i t 2 , int

end2 , double ∗NAt, double ∗NComp){

int i , j , k ;5 FreeArray (pAux) ;

A l l o ca t e (pAux , end2−i n i t 1 +1) ;Copy(pA, pAux , i n i t 1 , end2 ,NAt ,NComp) ;for ( i = 0 , j = end1−i n i t 1 +1, k = i n i t 1 ; k <= end2 ; k++){

10 i f ( i == end1−i n i t 1+1 ){

pA−>Pos i t i on s [ k ] = pAux−>Pos i t i on s [ j ++]; (∗NAt)++;continue ;

}15 i f ( j == end2−i n i t 2+end1−i n i t 1+2 )

{pA−>Pos i t i on s [ k ] = pAux−>Pos i t i on s [ i ++];(∗NAt)++;continue ;

}20 (∗NComp)++;

i f ( pAux−>Pos i t i on s [ i ] . key < pAux−>Pos i t i on s [ j ] . key ){

pA−>Pos i t i on s [ k ] = pAux−>Pos i t i on s [ i ++];(∗NAt)++;}

25 else

{pA−>Pos i t i on s [ k ] = pAux−>Pos i t i on s [ j ++];(∗NAt)++;

}}

30 FreeArray (pAux) ;}

void MSDivide (TArray ∗pA, TArray∗ pAux , int i n i t , int end , double ∗NAt,double ∗NComp)

{35 int mid ;

i f ( end == i n i t )return ;

mid = ( i n i t + end ) / 2 ;40 MSDivide (pA, pAux , i n i t , mid ,NAt ,NComp) ;

MSDivide (pA, pAux , mid+1, end ,NAt ,NComp) ;Merge (pA, pAux , i n i t , mid , mid+1, end ,NAt ,NComp) ;

}

45 void MergeSort (TArray ∗pA, double ∗NAt, double ∗NComp){

TArray∗ pAux ;pAux = (TArray∗) mal loc ( s izeof (TArray ) ) ;

9

50 Al l o ca t e (pAux ,pA−>Size ) ;MSDivide (pA, pAux , 0 ,pA−>Size −1,NAt ,NComp) ;FreeArray (pAux) ;

f r e e (pAux) ;55 }

Programa 6: MergeSort

2.1.7 Mergesort Otimizado

Utilizou-se a versão não interativa para a otimização deste algoritmo.

// MergeSortOvoid MergeSortO (TArray ∗pA, double ∗NAt, double ∗NComp){

TItem ∗VAux,∗pVAux ;5 int l1 , l2 , u1 , u2 , s i z e , n ;

int i , j , k ;

n = pA−>Size ;s i z e =1;

10 VAux = (TItem∗) mal loc ( s izeof (TItem) ∗n) ;while ( s i z e <n){

l 1 =0;k=0;

15 while ( l 1+s i z e < n ){

l 2=l1+s i z e ;u1=l2 −1;

20 i f ( l 2+s i z e−1<n)u2 = l2+s i z e −1;

else

u2 = n−1;// merge

25 for ( i = l 1 , j = l 2 ; i <= u1 && j <= u2 ; k++ ){

(∗NComp)++;i f (pA−>Pos i t i on s [ i ] . key<=pA−>Pos i t i on s [ j ] . key ){ VAux[ k ] = pA−>Pos i t i on s [ i ++]; (∗NAt)++;}

30 else

{ VAux[ k ] = pA−>Pos i t i on s [ j ++]; (∗NAt)++;}}for ( ; i <= u1 ; k++ ){ VAux[ k ] = pA−>Pos i t i on s [ i ++]; (∗NAt)++;}

35 for ( ; j <= u2 ; k++ ){ VAux[ k ] = pA−>Pos i t i on s [ j ++]; (∗NAt)++;}// incrementando l 1l 1=u2+1;

}40 for ( i = l 1 ; k < n ; i++ )

{ VAux[ k++] = pA−>Pos i t i on s [ i ] ; (∗NAt)++;}

// copiando temp em x// f o r ( i = 0 ; i < n ; i++)

45 // pA−>Pos i t i on s [ i ] = VAux [ i ] ;

10

pVAux = VAux;VAux = pA−>Pos i t i on s ;pA−>Pos i t i on s = pVAux ;

50 s i z e ∗=2;}f r e e (VAux) ;

}

Programa 7: Mergesort-O

2.1.8 SelectSort

Esse método possui ordem de complexidade de comparações O(n2) e realiza umatroca por vez, selecionando menor elemento e trazendo-o para a primeira posição dovetor.

Caso um determinado elemento numa posição seja menor que outro elemento naposição min, então será realizada a troca desses elementos a �m de tornar o vetorordenado.

// Se l e c t S o r tvoid Se l e c t So r t (TArray∗ pA, double∗ NAt, double∗ NComp){

int i , j , Min ;5 TItem aux ;

for ( i = 0 ; i < pA−>Size − 1 ; i++){

Min = i ;for ( j = i + 1 ; j < pA−>Size ; j++)

10 {(∗NComp)++;i f ( pA−>Pos i t i on s [ j ] . key < pA−>Pos i t i on s [Min ] . key ){

Min = j ;15 }

}aux = pA−>Pos i t i on s [Min ] ; (∗NAt)++;pA−>Pos i t i on s [Min ] = pA−>Pos i t i on s [ i ] ; (∗NAt)++;pA−>Pos i t i on s [ i ] = aux ; (∗NAt)++;

20 }}

Programa 8: SelectSort

2.1.9 SelectSort Otimizado

Para torná-lo mais e�ciente pois para fazer a troca antes veri�camos se o Min édiferente do i, caso seja verdadeira então realizamos a troca, uma vez que não eranecessário fazer essas operações quando o Min for igual ao i. Assim fazemos menosatribuições e consequentemente diminuímos o tempo de execução do programa, oque ajuda e muito para a ordenação de números grandes.

// Se l e c t S o r t Otimizadovoid Se lectSortO (TArray∗ pA, double∗ NAt, double∗ NComp){

11

int i , j , Min ;5 TItem aux ;

for ( i = 0 ; i < pA−>Size − 1 ; i++){

Min = i ;for ( j = i + 1 ; j < pA−>Size ; j++)

10 {(∗NComp)++;i f ( pA−>Pos i t i on s [ j ] . key < pA−>Pos i t i on s [Min ] . key ){

Min = j ;15 }

}i f ( i != Min){

(∗NComp)++;20 aux = pA−>Pos i t i on s [Min ] ; (∗NAt)++;

pA−>Pos i t i on s [Min ] = pA−>Pos i t i on s [ i ] ; (∗NAt)++;pA−>Pos i t i on s [ i ] = aux ; (∗NAt)++;

}}

25 }

Programa 9: SelectSort-O

2.1.10 InsertSort

Esse método percorre o vetor da esquerda para a direita, veri�cando os novoselementos se eles devem permanecer na mesma posição ou na anterior, e deixa oselementos da esquerda ordenados.

// In s e r t So r tvoid I n s e r t S o r t (TArray∗ pA, double∗ NAt, double∗ NComp){

int i , j ;5 TItem aux ;

for ( i = 1 ; i < pA−>Size ; i++){

aux = pA−>Pos i t i on s [ i ] ; (∗NAt)++;j = i − 1 ; (∗NAt)++;

10 while ( ( j >= 0 ) && ( aux . key < pA−>Pos i t i on s [ j ] . key ) ){(∗NComp)++;pA−>Pos i t i on s [ j + 1 ] = pA−>Pos i t i on s [ j ] ;

j−−; (∗NAt)++;15 }

pA−>Pos i t i on s [ j + 1 ] = aux ; (∗NAt)++;}

}

Programa 10: InsertSort

2.1.11 InsertSort com o elemento Sentinela

Para isso utiliza-se o Sentinela, um registro na posição 0 do vetor que quandoj=0 indicará o �m do loop, indicando que o vetor estará ordenado.

12

// In s e r t So r t Otimizado com Sen t ine l avoid InsertSortOS (TArray∗ pA, double∗ NAt, double∗ NComp){

int i , j ;5 TItem aux ;

for ( i = 2 ; i <= pA−>Size ; i++){aux = pA−>Pos i t i on s [ i ] ; (∗NAt)++;j = i − 1 ; (∗NAt)++;

10 i f ( aux . key<pA−>Pos i t i on s [ 0 ] . key ){

(∗NComp)++;pA−>Pos i t i on s [ 0 ] = aux ; /∗ s e n t i n e l a pr imeira pos ição pra

ind i ca r q eu chegue i no fim do ve to r ∗/}

15 while ( aux . key < pA−>Pos i t i on s [ j ] . key ){

(∗NComp)++;pA−>Pos i t i on s [ j +1] = pA−>Pos i t i on s [ j ] ; (∗NAt)++;

j−−; (∗NAt)++;20 }

pA−>Pos i t i on s [ j +1] = aux ; (∗NAt)++;}

}

Programa 11: InsertSort-OS

2.1.12 InsertSort Implementado através de Cursores

Para isso utiliza-se uma lista por cursores que são inteiros que representam asposições do arranjo, simulando os apontadores tradicionais.

// In s e r t So r t com Cursoresvoid Inse r tSor tC (TArray∗ pA, double∗ NAt, double∗ NComp){

int i , j , Min ;5

TLista pLi s ta ;FLVazia(&pLista ,pA−>Size ,NAt ,NComp) ;

for ( i =0; i<pA−>Size ; i++)10 LInsere (&pLista ,pA−>Pos i t i on s [ i ] ,NAt ,NComp) ;

LInsere (&pLista ,pA−>Pos i t i on s [ i ] ,NAt ,NComp) ;for ( i =0; pLi s ta . tamanho>0; i++)

LRPrimeiro(&pLista ,&pA−>Pos i t i on s [ i ] ,NAt ,NComp) ;

15 }

Programa 12: InsertSort-C

TAD da Lista por cursores

Para representar as implementações da lista por cursores foi criado um TADTLista.h bem como as assinaturas das funções:

typedef int Apontador ;

typedef int TChave ;

13

5 typedef struct TCelula {TItem Item ;Apontador pProx , pAnt ;

} TCelula ;

10 typedef struct TLista {TCelula ∗ Item ;Apontador TCelulaDisp , pPrimeiro , pUltimo ;int tamanho , n ;

} TLista ;15

void FLVazia ( TLista∗ , int , double∗ , double∗ ) ;int Tamanho( TLista∗ ) ;int LInsere ( TLista∗ , TItem pItem , double∗ , double∗ ) ;void LRPrimeiro ( TLista∗ pLista , TItem∗ , double∗ , double∗ ) ;

20 void LRUltimo ( TLista∗ pLista , TItem∗ , double∗ , double∗ ) ;

Programa 13: TAD TLista.h

Implementação das funções da lista por cursores

Abaixo as implementações das funções desse TAD TLista.h

void FLVazia ( TLista∗ pLista , int tam , double∗ NAt, double∗ NComp){

int i ;pLista−>Item = ( TCelula∗ ) mal loc ( s izeof ( TCelula ) ∗tam) ;

5 pLista−>tamanho = 0 ; (∗NAt)++;pLista−>pPrimeiro = −1; (∗NAt)++;pLista−>pUltimo = −1; (∗NAt)++;pLista−>TCelulaDisp = 0 ; (∗NAt)++;pLista−>n = tam ;

10 for ( i = 0 ; i < tam ; i++){

pLista−>Item [ i ] . pAnt = −1; (∗NAt)++;pLista−>Item [ i ] . pProx = i + 1 ; (∗NAt)++;(∗NComp)++;

15 }}int Tamanho( TLista∗ pLis ta ){

return ( pLista−>tamanho ) ;20 }

int LInsere ( TLista∗ pLista , TItem pItem , double∗ NAt, double∗ NComp){

int Pos , Disp , I nd i c e I n s e r c ao ;i f ( pLista−>tamanho == ( pLista−>n) )

25 return 0 ;(∗NComp)++;Disp = pLista−>TCelulaDisp ;pLista−>TCelulaDisp = pLista−>Item [ pLista−>TCelulaDisp ] . pProx ;pLista−>Item [ Disp ] . Item = pItem ;

30 pLista−>tamanho++; (∗NAt)++;i f ( pLista−>tamanho == 1){

pLista−>pPrimeiro = Disp ;pLista−>pUltimo = pLista−>pPrimeiro ;

35 pLista−>Item [ pLista−>pPrimeiro ] . pProx = −1;pLista−>Item [ pLista−>pPrimeiro ] . pAnt = −1;

14

return 1 ;}(∗NComp)++;

40 Pos = pLista−>pPrimeiro ;i f ( pItem . key < pLista−>Item [ Pos ] . Item . key ){

pLista−>Item [ Disp ] . pAnt = −1;pLista−>Item [ Disp ] . pProx = Pos ;

45 pLista−>Item [ Pos ] . pAnt = Disp ;pLista−>pPrimeiro = Disp ;return 1 ;

}(∗NComp)++;

50 I nd i c e I n s e r c a o = pLista−>Item [ Pos ] . pProx ;while ( I nd i c e I n s e r c a o != −1 && pLista−>Item [ Ind i c e I n s e r c ao ] . Item . key

< pItem . key ){Pos = Ind i c e I n s e r c a o ; (∗NAt)++;Ind i c e I n s e r c ao = pLista−>Item [ Pos ] . pProx ; (∗NAt)++;

55 (∗NComp)++;}

i f ( I nd i c e I n s e r c a o == −1){

pLista−>Item [ Disp ] . pAnt = Pos ; (∗NAt)++;60 pLista−>Item [ Disp ] . pProx = −1; (∗NAt)++;

pLista−>Item [ Pos ] . pProx = Disp ; (∗NAt)++;pLista−>pUltimo = Disp ; (∗NAt)++;return 1 ;

}65 (∗NComp)++;

pLista−>Item [ Disp ] . pAnt = Pos ; (∗NAt)++;pLista−>Item [ Disp ] . pProx = pLista−>Item [ Pos ] . pProx ; (∗NAt)++;pLista−>Item [ Pos ] . pProx = Disp ; (∗NAt)++;Pos = pLista−>Item [ Disp ] . pProx ; (∗NAt)++;

70 pLista−>Item [ Pos ] . pAnt = Disp ; (∗NAt)++;}void LRPrimeiro ( TLista∗ pLista , TItem∗ pItem , double∗ NAt, double∗ NComp){

Apontador ProxTmp ;75 i f ( pLista−>tamanho == 0)

return ;(∗NComp)++;∗pItem = pLista−>Item [ pLista−>pPrimeiro ] . Item ;ProxTmp = pLista−>Item [ pLista−>pPrimeiro ] . pProx ;

80 pLista−>Item [ pLista−>pPrimeiro ] . pProx = pLista−>TCelulaDisp ;pLista−>TCelulaDisp = pLista−>pPrimeiro ;pLista−>pPrimeiro = ProxTmp ; (∗NAt)++;i f ( pLista−>pPrimeiro < pLista−>n)

pLista−>Item [ pLista−>pPrimeiro ] . pAnt = −1;85 pLista−>tamanho−−; (∗NAt)++;

}void LRUltimo ( TLista∗ pLista , TItem∗ pItem , double∗ NAt, double∗ NComp){

Apontador AntTmp;90 i f ( pLista−>tamanho == 0)

return ;(∗NComp)++;∗pItem = pLista−>Item [ pLista−>pUltimo ] . Item ;

15

AntTmp = pLista−>Item [ pLista−>pUltimo ] . pAnt ;95 pLista−>Item [ pLista−>pUltimo ] . pProx = pLista−>TCelulaDisp ;

pLista−>TCelulaDisp = pLista−>pUltimo ;pLista−>pUltimo = AntTmp; (∗NAt)++;i f ( (unsigned int ) pLista−>pUltimo < pLista−>n)pLista−>Item [ pLista−>pUltimo ] . pProx = −1; (∗NAt)++;

100 pLista−>tamanho−−; (∗NAt)++;}

Programa 14: Implementações do TLista.c

2.1.13 BubbleSort

Esse método tem um altíssimo custo quando utilizado para ordenar vetores naforma invertida que é O(n2).

Agora, como o próprio nome sugere, esse método vai "borbulhando"pelo vetor atéque os elementos estejam ordenados. Neste algoritmo ele compara uma determinadaposição com a anterior, caso a anterior seja maior, ele troca as posição de modo queo vetor seja ordenado.

//Bubb leSortvoid BubbleSort (TArray∗ pA, double∗ NAt, double∗ NComp){

int i , j ;5 TItem aux ;

for ( i =0; i<pA−>Size −1; i++){

for ( j =1; j<pA−>Size−i ; j++){

10 (∗NComp)++;i f (pA−>Pos i t i on s [ j ] . key<pA−>Pos i t i on s [ j −1] . key ){

aux = pA−>Pos i t i on s [ j ] ; (∗NAt)++;pA−>Pos i t i on s [ j ]=pA−>Pos i t i on s [ j −1] ; (∗NAt)++;

15 pA−>Pos i t i on s [ j−1]=aux ; (∗NAt)++;}

}}

}

Programa 15: BubbleSort

2.1.14 BubbleSort com Troca

Uma maneira plausível de otimizar o método de ordenação BubbleSort é criaruma variável para receber 0 ou 1, onde 1 signi�ca que foi realizado uma troca e0 que não foi realizado nenhuma troca durante o loop indicando que o vetor estáordenado, assim evita percorrer o todo vetor quando o mesmo já está ordenado.

//Bubb leSort com Trocavoid BubbleSortT (TArray∗ pA, double∗ NAt, double∗ NComp){

int i , j , t r oca ;5 TItem aux ;

for ( i =0; i<pA−>Size −1; i++ ){

16

t roca =0; (∗NAt)++;for ( j =1; j<pA−>Size−i ; j++)

10 {(∗NComp)++;i f (pA−>Pos i t i on s [ j ] . key<pA−>Pos i t i on s [ j −1] . key ){aux=pA−>Pos i t i on s [ j ] ;

15 pA−>Pos i t i on s [ j ]=pA−>Pos i t i on s [ j −1] ; (∗NAt)++;pA−>Pos i t i on s [ j−1]=aux ; (∗NAt)++;t roca =1; (∗NAt)++;}

}20 i f ( t roca == 0)

{(∗NComp)++;break ;

}25 }

}

Programa 16: BubbleSort-T

17

3 Grá�cos e Tabelas

Abaixo os grá�cos e tabelas de cada método de ordenação divididas em Atribuições,Comparações e Tempo de Execução:

3.1 Função QuickSort

3.1.1 Atribuições

Realiza uma quantidade de atribuições bastante interessante exceto no modorandom que obteve aproximadamente 12,4 milhões de comparações.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 1: Atribuições

18

3.1.2 Comparações

Nota-se pelo grá�co e pelas informações contidas na tabela que esse método re-aliza bastantes comparações, mas mesmo assim, veremos que é um método bastantee�ciente de ordenação devido ao tempo de execução.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 2: Comparações

3.1.3 Tempo de Execução

Esse método de ordenação tem um excelente resultado sobre o tempo de execuçãodo algoritmo o que prova o motivo pelo qual é um dos mais utilizado atualmente,demonstrando, portanto, sua e�ciência em resolver esse tipo de problema.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

19

Figura 3: Tempo de Execução

3.2 QuickSort Otimizado

3.2.1 Atribuições

Quando levado em consideração o número de atribuições não houve uma difer-ença signi�cativa, para perceber isso basta analisar os grá�cos e veremos o mesmocontinua praticamente estável, mas é claro com algumas distinções.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

20

Figura 4: Atribuições

3.2.2 Comparações

Para o número de comparações veri�ca-se que se tornou praticamente reta quandoobservado cada quantidade de elementos separadamente, demonstrando que o númerode comparações nos diferentes modos cresce proporcionalmente de acordo com aquantidade de elementos.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 5: Comparações

21

3.2.3 Tempo de Execução

Ainda obtivemos um resultado impressionante nesse método otimizado, levandoum menor tempo de execução do algoritmo quando comparado com o método nor-mal, exceto no modem random com uma quantidade de elementos inferior 1.000.000(ummilhão) de elementos.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

Figura 6: Tempo de Execução

22

3.3 HeapSort

3.3.1 Atribuições

Para o número de atribuições no HeapSort, permanece praticamente o mesmoquando comparado com o HeapSort Otimizado.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 7: Atribuições

23

3.3.2 Comparações

Para o número de comparações no HeapSort, também permanece praticamenteo mesmo quando comparado com o HeapSort Otimizado.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 8: Comparações

3.3.3 Tempo de Execução

É impressionante o tempo que o HeapSort levou para ordenar os 1.000.000(ummilhão) de vetores, o que demonstra que esse método é muito e�ciente para resoluçãodesse tipo de problema quando a quantidade de elementos é maior.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

24

Figura 9: Tempo de Execução

3.4 HeapSort Otimizado

3.4.1 Atribuições

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 10: Atribuições

3.4.2 Comparações

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

25

Figura 11: Comparações

3.4.3 Tempo de Execução

Quando levado em consideração o tempo de execução veri�ca-se que realmente houveuma melhora no HeapSort Otimizado, ou seja, se gasta um tempo menor para aresolução do problema, entretanto não é tão signi�cativa.Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

Figura 12: Tempo de Execução

26

3.5 MergeSort

3.5.1 Atribuições

Esse método realiza independentemente da quantidade de elementos no vetor omesmo número de atribuições o que demonstra que para a análise do número deatribuições, a quantidade de elementos não é signi�cativa, isto é, não depende daquantidade de elementos pois será a mesma.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 13: Atribuições

27

3.5.2 Comparações

Quando levado em consideração o número de comparações, então a quantidadede elementos deve sim ser levada em consideração, uma vez que varia de acordo como número de elementos.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 14: Comparações

3.5.3 Tempo de Execução

Com relação ao tempo de execução, esse é um método interessante se seu usarcomo podemos observar no grá�co.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

28

Figura 15: Tempo de Execução

3.6 MergeSort Otimizado

3.6.1 Atribuições

Nesse método MergeSort Otimizado obtemos uma melhora no número de atribuiçõesquando comparado ao MergSort, mas ainda sim continua o mesmo número deatribuições independentemente do número de elementos.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 16: Atribuições

29

3.6.2 Comparações

Para o Método MergeSort Otimizado com relação ao número de comparações,não obtivemos uma melhora signi�cativa, observando-se, portando, que o grá�cocontinua praticamente estável.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 17: Comparações

3.6.3 Tempo de Execução

Com relação ao tempo de execução nota-se, pelo grá�co e pelas análises realizadouma melhora signi�cativa, uma vez que por exemplo, para ordenar 1.000.000(ummilhão) de vetores no modo normal, gastou-se aproximadamente 37,2 segundos eno método otimizado aproximadamente 0.56 segundo, o que demonstra uma ótimamelhora e bastante signi�cativa com relação ao tempo de execução desse algoritmo.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

30

Figura 18: Tempo de Execução

3.7 SelectSort

3.7.1 Atribuições

O número de atribuições independe da quantidade de elementos, por isso veri�-camos o grá�co como sendo uma única linha, onde os resultados são os mesmos, emantendo constate para cada quantidade de�nida de elementos.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

31

Figura 19: Atribuições

3.7.2 Comparações

O número de comparações desse método cresce proporcionalmente de acordocom a quantidade de elementos analisados, mantendo constate para cada quantidadede�nida de elementos.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 20: Comparações

32

3.7.3 Tempo de Execução

Com relação ao tempo de execução, esse não é um método ideal para se utilizarpara elementos superiores a 1.000(mil) uma vez que há um acréscimo bastante sig-ni�cativo no tempo de execução do algoritmo o que demonstra ser não viável a suautilização pra essa �nalidade.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

Figura 21: Tempo de Execução

33

3.8 SelectSort Otimizado

3.8.1 Atribuições

Para atribuições houve uma melhora signi�cativa quando se utiliza o métodootimizado, exceto pelo modo random que obteve uma pequena diferença. Ainda,podemos observar que não houve nenhuma atribuição quando o vetor estiver orde-nado, o que não acontecia no método normal.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 22: Atribuições

34

3.8.2 Comparações

Para o número de comparações não houve resultados signi�cativos, uma vez quecontinuou praticamente o mesmo, mas é claro, usou-se mais comparações, comopodemos observar no grá�co abaixo.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 23: Comparações

3.8.3 Tempo de Execução

Sobre o tempo de execução do algoritmo só obteve uma melhora nos modossorted(ordenado) e no inverted(invertido), já nos outros, houve um acréscimo notempo, o que não foi conveniente a otimização quando formos pegar um vetor emmodo almost sorted(quase ordenado) ou em modo random(aleatório).

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

35

Figura 24: Tempo de Execução

3.9 InsertSort

3.9.1 Atribuições

Esse método realiza muitas atribuições como podemos observar no grá�co e natabela, o que não pode ser um método muito e�ciente quando levado em consideraçãoo número de atribuições.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 25: Atribuições

36

3.9.2 Comparações

Para comparações, ainda sim realiza muitas comparações quando veri�cado nográ�co, exceto quando o vetor estiver ordenado, pois dessa maneira não realizanenhuma comparação.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 26: Comparações

3.9.3 Tempo de Execução

Ainda sim leva um tempo considerável para ordenar muitos elementos, o que,dependendo da quantidade de elementos, não seria recomendável utilizar esse métodode ordenação.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

37

Figura 27: Tempo de Execução

3.10 InsertSort com o elemento Sentinela

3.10.1 Atribuições

Devido o elemento sentinela, fazemos ainda mais atribuições quando comparadoao método sem o sentinela. Ainda sim não houve uma diferença signi�cativa pois ográ�co continua estável.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 28: Atribuições

38

3.10.2 Comparações

Para o número de comparações, o resultado é praticamente o mesmo da análisede atribuições, o grá�co continua estável e não houve uma diferença brusca nosdados.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 29: Comparações

3.10.3 Tempo de Execução

Ainda não obtivemos um diferencial tão signi�cativo com relação ao tempo deexecução desse método com o elemento sentinela, continuando o grá�co estável e comalgumas diferenças no tempo, o que varia de acordo com a quantidade de elementos.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

39

Figura 30: Tempo de Execução

3.11 InsertSort por Cursores

3.11.1 Atribuições

Esse método realiza a mesma quantidade de comparações para todos os métodos,sendo mais precisamente a mesma igual à quantidade de elementos ordenados.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

40

Figura 31: Atribuições

3.11.2 Comparações

Para comparações, ainda sim realiza muitas comparações quando veri�cado nográ�co, exceto quando o vetor estiver invertido, pois dessa maneira realiza umamenor quantidade de comparações.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 32: Comparações

41

3.11.3 Tempo de Execução

Ainda sim leva um tempo considerável para ordenar muitos elementos, excetoquando o vetor estiver invertido, o que, dependendo da quantidade de elementos,não seria recomendável utilizar esse método de ordenação.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

Figura 33: Tempo de Execução

42

3.12 BubbleSort

3.12.1 Atribuições

Para o BubbleSort, veri�ca-se que esse método realiza o mesmo número de com-parações independentemente da forma com que os elementos estão ordenados novetor, portando as linhas do grá�co se coincidem como vemos no grá�co de com-parações.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

Figura 34: Atribuições

43

3.12.2 Comparações

Quando levado em consideração o número de atribuições, párea cada caso tere-mos valores distintos utilizando o método BubbleSort como é veri�cado no grá�co.Ainda, para quando o vetor estiver ordenado, fazemos 0 atribuições.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 35: Comparações

3.12.3 Tempo de Execução

Para uma grande quantidade de elementos esse não é um método adequado paraordenar vetores, uma vez que para ordenar 100.000(cem mil) vetores requer muitotempo para realizar a tarefa, mas para números pequenos é adequado.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

44

Figura 36: Tempo de Execução

3.13 BubbleSort com Troca

3.13.1 Atribuições

Para atribuições, veri�ca-se que não houve uma melhora signi�cativa, pois osgrá�cos de com e sem troca são bem parecidos e os dados são bem próximos, portantose for levado em consideração o número de atribuições não fará muita diferença emutilizar o método com ou sem troca.

Grá�co e Tabela de Atribuições, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de atribuições realizadas para ordená-los.

45

Figura 37: Atribuições

3.13.2 Comparações

Devido a veri�cação no loop se houve ou não troca, veri�ca-se que esse métodoé mais e�ciente do que o BubbleSort convencional, então, o método com elementotroca é mais e�ciente. Assim, quando comparado em números de comparações,veri�camos pelo grá�co que esse método faz menos comparações do que o métodosem a troca.

Grá�co e Tabela de Comparações, onde abaixo do grá�co tem a quantidade deelementos bem como a quantidade de comparações realizadas para ordená-los.

Figura 38: Comparações

46

3.13.3 Tempo de Execução

Sobre o tempo de execução, veri�ca-se que houve uma melhora signi�cativa comrelação ao método sem troca, exceto para o modo random, entretanto, ainda é viávelutilizar o método com troca, pois como podemos observar pelo grá�co, esse métodorequer menos tempo para a resolução do problema proposto.

Grá�co e Tabela do Tempo de Execução, onde abaixo do grá�co tem a quantidadede elementos bem como o tempo de execução para realizado para ordená-los.

Figura 39: Tempo de Execução

47

4 Análise de complexidade dos algoritmos

Levado em consideração o número de comparações.

4.1 Sort.h

4.1.1 Função QuickSort

No pior caso tem ordem de complexidade O(n2) quando o pivô selecionado for omaior elemento do vetor ou caso ele esteja no extremo do vetor.

4.1.2 HeapSort

No pior, tanto para qualquer, caso tem ordem de complexidade (n.lg(n)).

4.1.3 MergeSort

No pior, tanto para qualquer, caso tem ordem de complexidade (n.lg(n)).

4.1.4 SelectSort

Decido aos dois loops, um i partindo de 0 até pA->Size-1 e o outro j partindode i+1 indo até pA->Size. Possui ordem de complexidade O(n2).

f(n) =n−2∑i=0

(n− i− 1) = (n2 − n)/2 (1)

4.1.5 InsertSort

No pior caso, o número de comparações é C(n) = (2+1 + 2+2 + ... + 2+n-1)= (n2+3n-4)/2, portanto possui ordem de complexidade O(n2).

4.1.6 BubbleSort

Devido aos dois loops, um i partindo de 0 até pA->Size-1 e o outro j partindode 1 indo até pA->Size-i. Possui ordem de complexidade O(n2).

f(n) =n−2∑i=0

(n− i− 1) = (n2 − n)/2 (2)

48

5 Testes

Teste para veri�car se os vetores foram corretamente ordenados:

Figura 40: Teste de Ordenação

49

Análise de ordenação:

Figura 41: Análise de Ordenação

50

6 Conclusão

Veri�ca-se que para cada situação e o modo com que o vetor está ordenado,bem como a quantidade de elementos, cada método é muito útil para a resoluçãode problemas de ordenação, demonstrando que para cada caso é viável utilizar ummétodo especí�co de ordenação. Ainda pude aprender a analisar os algoritmos deforma a juntar dados sobre ele, isto é, coletar informações importantes sobre o seufuncionamento e armazenar em grá�co e tabela de forma que seja mais interativaa avaliação para que qualquer pessoa com o mínimo de relacionamento na área dacomputação possa entender, pelo menos, e identi�car qual é o melhor método emdeterminada situação, assim facilitando o seu trabalho na explicação desses proble-mas a uma determinada pessoa e é claro, obtive mais maturidade nos métodos deordenação bem como a melhor compreensão sobre esses tipos de problemas.

Referências

[1] David Menotti Algoritmos e Estruturas de Dados I: Ordenação I SelectSort,InsertSort, BubbleSort. http://www.decom.ufop.br/prof/menotti/aedI092/slides/aula14-Ordenacao.ppt, visitado em 14/11/2009.

[2] David Menotti Algoritmos e Estruturas de Dados I: Ordenação IIIQuickSort. http://www.decom.ufop.br/prof/menotti/aedI092/slides/

aula16-QuickSort.ppt, visitado em 14/11/2009.

[3] David Menotti Algoritmos e Estruturas de Dados I: OrdenaçãoIV HeapSort. http://www.decom.ufop.br/prof/menotti/aedI092/slides/

aula17-HeapSort.ppt, visitado em 14/11/2009.

[4] David Menotti Algoritmos e Estruturas de Dados I: Ordenação VMergeSort. http://www.decom.ufop.br/prof/menotti/aedI092/slides/

aula18-MergeSort.ppt, visitado em 14/11/2009.

[5] David Menotti Algoritmos e Estruturas de Dados I: Filas. http://

www.decom.ufop.br/prof/menotti/aedI092/slides/aula12-Fila.ppt, visi-tado em 14/11/2009.

51