View
64
Download
37
Category
Preview:
DESCRIPTION
Este relatório apresenta uma comparação no tempo de execução dos algoritmos de ordenação InsertionSort, QuickSort, MergeSort e CountingSort. Segue também os códigos de cada algoritmo em java.
Citation preview
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
050001000015000200002500030000350001000020000400006000080000100000tempo de execuo (milissegundos)tamanho (elementos)Insertion SortQuick SortMerge SortCounting Sort
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
Recommended