Universidade Federal do Par

Faculdade de Cincia da Computao

Disciplina: Projetos de Algoritmos II

RELATRIO:

PROJETOS DE ALGORITMOS II

Belm - 2013

1.1 Introduo:

Em diversas aplicaes, os dados devem ser armazenados obedecendo a uma determinada ordem. Alguns algoritmos podem explorar a ordenao dos dados para operar de maneira mais eficiente, do ponto de vista de desempenho computacional. Para obtermos os dados ordenados, temos basicamente duas alternativas: ou inserimos os elementos na estrutura de dados respeitando a ordenao (dizemos que a ordenao garantida por construo), ou, a partir de um conjunto de dados j criado, aplicamos um algoritmo para ordenar seus elementos.

Este relatrio apresenta quatro algoritmos de ordenao que podem ser empregados em aplicaes computacionais. importante ter disposio algoritmos de ordenao eficientes tanto em termos de tempo (devem ser rpidos) como em termos de espao (devem ocupar pouca memria durante a execuo). Vamos descrever os algoritmos considerando o seguinte cenrio: a entrada um vetor cujos elementos precisam ser ordenados; a sada o mesmo vetor com seus elementos na ordem especificada; o espao que pode ser utilizado apenas o espao do prprio vetor.

Os algoritmos de ordenao que sero analisados quando ao seu desempenho sero:

Insertion Sort Este algoritmo considerado um dos mais simples, ele percorre um vetor de elementos da esquerda para a direita e a medida que avana vai deixando os elementos mais a esquerda ordenados.

Quick Sort um mtodo de ordenao muito rpido e eficiente. Ele adota a estratgia de diviso e conquista. A estratgia consiste em rearranjar as chaves de modo que as chaves menores precedem as chaves maiores. Em seguida, o Quick Sort ordena as duas sublistas de chaves menores e maiores recursivamente at que a lista completa se encontre ordenada.

Merge Sort Sua ideia bsica consiste em dividir o problema em vrios subproblemas para serem resolvidos atravs da recursividade. Aps todos os subproblemas terem sido resolvidos ocorre a conquista, que a unio das resolues desses subproblemas.

Counting Sort - A ordenao por contagem pressupe que cada um dos n elementos do vetor de entrada um inteiro entre 1 e k (k representa o maior inteiro presente no vetor). A idia bsica determinar, para cada elemento de entrada x, o numero de elementos menores ou iguais a x. Com essa informao possvel determinar exatamente onde o elemento x ser inserido.

1.2 Objetivo:

O objetivo deste trabalho compreender, dentre os vrios algoritmos de ordenao existentes, o funcionamento de cada um dos quatro algoritmos de ordenao selecionados e analisar o desempenho dos mesmos. A anlise ser feita atravs de simulaes dos algoritmos para a execuo de cada conjunto de elementos.

1.3 Materiais Utilizados:

Para as simulaes foram utilizados os software e hardware listados abaixo:

Cdigos desenvolvidos na linguagem Java e compilados no NetBeans IDE verso 8.0.

Computador: Intel Core 2 Duo 2,4 GHz, 2 GB de RAM, Sistema Operacional Windows XP SP2.

Resumo do Experimento:

No experimento, foi desenvolvida uma aplicao que consiste em ordenar vetores atravs dos mtodos Insertion Sort, Quick Sort, Merge Sort e Counting Sort gerando um vetor aleatrio com elementos repetidos.

Para medir o desempenho dos algoritmos, a cada simulao foram geradas dez sequncias de inteiros aleatrios, variando de 0 at o valor mximo de elementos do vetor, calculando todos os tempos de ordenao, sabendo assim seu tempo mdio de ordenao para cada tamanho de vetor.

Os tempos mostrados so tempos de CPU, medidos em milissegundos.

1.5 Resultados:

Essa seo apresenta o tempo de execuo das simulaes referentes aos algoritmos testados. A aplicao gerou os seguintes tempos:

Insertion Sort:

Tempo de ordenao dos vetores de 10.000 elementos, pelo algoritmo Insertion Sort, em milissegundos:

Simulao 1: 841

Simulao 2: 843

Simulao 3: 907

Simulao 4: 837

Simulao 5: 815

Simulao 6: 777

Simulao 7: 795

Simulao 8: 999

Simulao 9: 815

Simulao 10: 830

O tempo mdio de ordenao foi de: 846 milissegundos.

Tempo de ordenao dos vetores de 20.000 elementos, pelo algoritmo Insertion Sort, em milissegundos:

Simulao 1: 1521

Simulao 2: 1619

Simulao 3: 1527

Simulao 4: 1598

Simulao 5: 1916

Simulao 6: 1665

Simulao 7: 1656

Simulao 8: 1583

Simulao 9: 1533

Simulao 10: 1754

O tempo mdio de ordenao foi de: 1637 milissegundos.

Tempo de ordenao dos vetores de 40.000 elementos, pelo algoritmo Insertion Sort, em milissegundos:

Simulao 1: 3161

Simulao 2: 3794

Simulao 3: 3376

Simulao 4: 4075

Simulao 5: 4665

Simulao 6: 3446

Simulao 7: 3650

Simulao 8: 3338

Simulao 9: 3557

Simulao 10: 3560

O tempo mdio de ordenao foi de: 3662 milissegundos.

Tempo de ordenao dos vetores de 60.000 elementos, pelo algoritmo Insertion Sort, em milissegundos:

Simulao 1: 5630

Simulao 2: 5382

Simulao 3: 5424

Simulao 4: 5521

Simulao 5: 5962

Simulao 6: 6247

Simulao 7: 5213

Simulao 8: 5584

Simulao 9: 5449

Simulao 10: 5341

O tempo mdio de ordenao foi de: 5575 milissegundos.

Tempo de ordenao dos vetores de 80.000 elementos, pelo algoritmo Insertion Sort, em milissegundos:

Simulao 1: 8960

Simulao 2: 8506

Simulao 3: 8389

Simulao 4: 8300

Simulao 5: 8625

Simulao 6: 8025

Simulao 7: 7423

Simulao 8: 7360

Simulao 9: 8350

Simulao 10: 8282

O tempo mdio de ordenao foi de: 8222 milissegundos.

Tempo de ordenao dos vetores de 100.000 elementos, pelo algoritmo Insertion Sort, em milissegundos:

Simulao 1: 9897

Simulao 2: 9590

Simulao 3: 9475

Simulao 4: 9334

Simulao 5: 9756

Simulao 6: 9633

Simulao 7: 9768

Simulao 8: 9517

Simulao 9: 10300

Simulao 10: 9752

O tempo mdio de ordenao foi de: 9702 milissegundos.

Quick Sort:

Tempo de ordenao dos vetores de 10.000 elementos, pelo algoritmo Quick Sort, em milissegundos:

Simulao 1: 802

Simulao 2: 797

Simulao 3: 800

Simulao 4: 784

Simulao 5: 702

Simulao 6: 714

Simulao 7: 750

Simulao 8: 733

Simulao 9: 721

Simulao 10: 723

O tempo mdio de ordenao foi de: 752 milissegundos.

Tempo de ordenao dos vetores 20.000 elementos, pelo algoritmo Quick Sort, em milissegundos:

Simulao 1: 1477

Simulao 2: 1651

Simulao 3: 1708

Simulao 4: 1406

Simulao 5: 1449

Simulao 6: 1674

Simulao 7: 1431

Simulao 8: 1467

Simulao 9: 1460

Simulao 10: 1370

O tempo mdio de ordenao foi de: 1509 milissegundos.

Tempo de ordenao dos vetores de 40.000 elementos, pelo algoritmo Quick Sort,

em milissegundos:

Simulao 1: 2837

Simulao 2: 3033

Simulao 3: 3084

Simulao 4: 3130

Simulao 5: 3108

Simulao 6: 2923

Simulao 7: 3033

Simulao 8: 2878

Simulao 9: 2925

Simulao 10: 2969

O tempo mdio de ordenao foi de: 2992 milissegundos.

Tempo de ordenao dos vetores de 60.000 elementos, pelo algoritmo Quick Sort,

em milissegundos:

Simulao 1: 4439

Simulao 2: 4403

Simulao 3: 4609

Simulao 4: 4365

Simulao 5: 4471

Simulao 6: 4582

Simulao 7: 4836

Simulao 8: 4463

Simulao 9: 4555

Simulao 10: 4554

O tempo mdio de ordenao foi de: 4527 milissegundos.

Tempo de ordenao dos vetores de 80.000 elementos, pelo algoritmo Quick Sort,

em milissegundos:

Simulao 1: 6104

Simulao 2: 5948

Simulao 3: 6124

Simulao 4: 5971

Simulao 5: 6071

Simulao 6: 6136

Simulao 7: 6115

Simulao 8: 6087

Simulao 9: 6253

Simulao 10: 6328

O tempo mdio de ordenao foi de: 6113 milissegundos.

Tempo de ordenao dos vetores de 100.000 elementos, pelo algoritmo Quick Sort, em milissegundos:

Simulao 1: 7660

Simulao 2: 7611

Simulao 3: 7644

Simulao 4: 7797

Simulao 5: 7455

Simulao 6: 7880

Simulao 7: 7693

Simulao 8: 7510

Simulao 9: 7777

Simulao 10: 7904

O tempo mdio de ordenao foi de: 7693 milissegundos.

Merge Sort:

Tempo de ordenao dos vetores de 10.000 elementos, pelo algoritmo Merge Sort, em milissegundos:

Simulao 1: 990

Simulao 2: 1025

Simulao 3: 953

Simulao 4: 1019

Simulao 5: 1157

Simulao 6: 967

Simulao 7: 1021

Simulao 8: 1160

Simulao 9: 943

Simulao 10: 1026

O tempo mdio de ordenao foi de: 1026 milissegundos.

Tempo de ordenao dos vetores de 20.000 elementos, pelo algoritmo Merge Sort, em milissegundos:

Simulao 1: 2599

Simulao 2: 2685

Simulao 3: 2605

Simulao 4: 2609

Simulao 5: 2566

Simulao 6: 2335

Simulao 7: 2236

Simulao 8: 2283

Simulao 9: 2211

Simulao 10: 2272

O tempo mdio de ordenao foi de: 2440 milissegundos.

Tempo de ordenao dos vetores de 40.000 elementos, pelo algoritmo Merge Sort, em milissegundos:

Simulao 1: 6263

Simulao 2: 6043

Simulao 3: 6316

Simulao 4: 6378

Simulao 5: 6932

Simulao 6: 9598

Simulao 7: 6649

Simulao 8: 6397

Simulao 9: 6433

Simulao 10: 6411

O tempo mdio de ordenao foi de: 6442 milissegundos.

Tempo de ordenao dos vetores de 60.000 elementos, pelo algoritmo Merge Sort, em milissegundos:

Simulao 1: 11909

Simulao 2: 11685

Simulao 3: 11839

Simulao 4: 11949

Simulao 5: 12131

Simulao 6: 12518

Simulao 7: 11576

Simulao 8: 11928

Simulao 9: 11610

Simulao 10: 11657

O tempo mdio de ordenao foi de: 11880 milissegundos.

Tempo de ordenao dos vetores de 80.000 elementos, pelo algoritmo Merge Sort, em milissegundos:

Simulao 1: 19164

Simulao 2: 18879

Simulao 3: 19727

Simulao 4: 19211

Simulao 5: 19554

Simulao 6: 19598

Simulao 7: 19009

Simulao 8: 19966

Simulao 9: 19189

Simulao 10: 19443

O tempo mdio de ordenao foi de: 19374 milissegundos.

Tempo de ordenao dos vetores de 100.000 elementos, pelo algoritmo Merge Sort, em milissegundos:

Simulao 1: 30437

Simulao 2: 29591

Simulao 3: 30006

Simulao 4: 30408

Simulao 5: 30776

Simulao 6: 30372

Simulao 7: 29916

Simulao 8: 30499

Simulao 9: 30004

Simulao 10: 30276

O tempo mdio de ordenao foi de: 30228 milissegundos.

Counting Sort:

Tempo de ordenao dos vetores de 10.000 elementos, pelo algoritmo Counting Sort, em milissegundos:

Simulao 1: 713

Simulao 2: 765

Simulao 3: 791

Simulao 4: 810

Simulao 5: 846

Simulao 6: 801

Simulao 7: 778

Simulao 8: 866

Simulao 9: 790

Simulao 10: 784

O tempo mdio de ordenao foi de: 794 milissegundos.

Tempo de ordenao dos vetores de 20.000 elementos, pelo algoritmo Counting Sort, em milissegundos:

Simulao 1: 1546

Simulao 2: 1549

Simulao 3: 1526

Simulao 4: 1515

Simulao 5: 1867

Simulao 6: 1563

Simulao 7: 1479

Simulao 8: 1663

Simulao 9: 1569

Simulao 10: 1654

O tempo mdio de ordenao foi de: 1593 milissegundos.

Tempo de ordenao dos vetores de 40.000 elementos, pelo algoritmo Counting Sort, em milissegundos:

Simulao 1: 3253

Simulao 2: 3152

Simulao 3: 3049

Simulao 4: 3041

Simulao 5: 3018

Simulao 6: 3026

Simulao 7: 3063

Simulao 8: 2953

Simulao 9: 2979

Simulao 10: 2967

O tempo mdio de ordenao foi de: 2980 milissegundos.

Tempo de ordenao dos vetores de 60.000 elementos, pelo algoritmo Counting Sort, em milissegundos:

Simulao 1: 4749

Simulao 2: 4996

Simulao 3: 4886

Simulao 4: 4632

Simulao 5: 4609

Simulao 6: 4900

Simulao 7: 5001

Simulao 8: 4992

Simulao 9: 4831

Simulao 10: 5120

O tempo mdio de ordenao foi de: 4871 milissegundos.

Tempo de ordenao dos vetores de 80.000 elementos, pelo algoritmo Counting Sort, em milissegundos:

Simulao 1: 6407

Simulao 2: 6349

Simulao 3: 6329

Simulao 4: 6498

Simulao 5: 6349

Simulao 6: 6359

Simulao 7: 6531

Simulao 8: 6428

Simulao 9: 6616

Simulao 10: 6282

O tempo mdio de ordenao foi de: 6414 milissegundos.

Tempo de ordenao dos vetores de 100.000 elementos, pelo algoritmo Counting Sort, em milissegundos:

Simulao 1: 8141

Simulao 2: 8105

Simulao 3: 8083

Simulao 4: 8389

Simulao 5: 7862

Simulao 6: 8247

Simulao 7: 8141

Simulao 8: 7989

Simulao 9: 8220

Simulao 10: 8496

O tempo mdio de ordenao foi de: 8163 milissegundos.

A figura 01 mostra o grfico comparativo dos quatro algoritmos com os resultados obtidos nas simulaes, com tamanho em funo do tempo de processamento real. Em uma anlise rpida, pode-se perceber que o algoritmo de ordenao Merge Sort possui o pior desempenho e que o Quick Sort apresentou o melhor desempenho.

050001000015000200002500030000350001000020000400006000080000100000tempo de execuo (milissegundos)tamanho (elementos)Insertion SortQuick SortMerge SortCounting Sort

Grf11000010000100001000020000200002000020000400004000040000400006000060000600006000080000800008000080000100000100000100000100000

Insertion Sort

Quick Sort

Merge Sort

Counting Sort

tamanho (elementos)

tempo de execuo (milissegundos)

845

752

1026

794

1637

1509

2440

1593

3662

2992

6442

2980

5575

4527

11880

4871

8222

6113

19374

6415

9702

7693

30228

8163

Plan1Insertion SortQuick SortMerge SortCounting Sort1000084575210267942000016371509244015934000036622992644229806000055754527118804871800008222611319374641510000097027693302288163Para redimensionar o intervalo de dados do grfico, arraste o canto inferior direito do intervalo.

Plan2

050001000015000200002500030000350001000020000400006000080000100000tempo de execuo (milissegundos)tamanho (elementos)Insertion SortQuick SortMerge SortCounting Sort

Grf11000010000100001000020000200002000020000400004000040000400006000060000600006000080000800008000080000100000100000100000100000

Insertion Sort

Quick Sort

Merge Sort

Counting Sort

tamanho (elementos)

tempo de execuo (milissegundos)

845

752

1026

794

1637

1509

2440

1593

3662

2992

6442

2980

5575

4527

11880

4871

8222

6113

19374

6415

9702

7693

30228

8163

Plan1Insertion SortQuick SortMerge SortCounting Sort1000084575210267942000016371509244015934000036622992644229806000055754527118804871800008222611319374641510000097027693302288163Para redimensionar o intervalo de dados do grfico, arraste o canto inferior direito do intervalo.

Plan2

0

5000

10000

15000

20000

25000

30000

35000

10000

20000

40000

60000

80000

100000

t

e

m

p

o

d

e

e

x

e

c

u

o

(

m

i

l

i

s

s

e

g

u

n

d

o

s

)

tamanho (elementos)

Insertion Sort

Quick Sort

Merge Sort

Counting Sort

Figura 01

Grfico comparativo dos algoritmos de ordenao. Tamanho em funo do Tempo.

1.6 Rotinas Utilizadas

Nessa sesso so apresentados os mtodos utilizados nos algoritmos de ordenao da aplicao.

Rotina de ordenao Insertion Sort:

public static void main(String[] args) {

long tempoInicio = System.currentTimeMillis();

Random rand = new Random();

int x[] = new int[10000]; //gera um vetor com elementos aleatrios

int i, j, eleito;

for (i = 0; i < x.length; i++) {

x[i] = rand.nextInt(10000);

}

for (i = 1; i = 0 && x[j] > eleito) {

x[j + 1] = x[j]; //troca de posio

j = j - 1;

}

x[j + 1] = eleito; //escreve na nova posio

}

//imprime o vetor ordenado

for (i = 0; i < x.length; i++) {

System.out.println((i + 1) + " nmero: " + x[i]);

}

//imprime o tempo de execuo

System.out.println("\nTempo Total: "+(System.currentTimeMillis()-tempoInicio)+" milisegundos.");

}

}

Rotina de ordenao Quick Sort:

public static void quicksort(int vet[], int ini, int fim) {

int meio;

if (ini < fim) {

meio = partition(vet, ini, fim);

quicksort(vet, ini, meio);

quicksort(vet, meio + 1, fim);

}

}

public static int partition(int vet[], int ini, int fim) {

int pivo, topo, i;

pivo = vet[ini];

topo = ini;

for (i = ini + 1; i