ANALISE DE PERFORMANCE

Prévia do material em texto

UNIVERSIDADE PAULISTA – UNIP 
 
 
 
 
 
 
 
FELIPE CUNHA SANTOS / C7625F-2 
KAIO DA FONSECA GONÇALVES DA SILVA / C5347A-3 
LUCAS BRITTO DA SILVA / C75FCF-1 
WILLIAN COSTA BARBOSA / C59285-4 
 
 
 
 
 
 
 
 
 
 
 
 
 
DESENVOLVIMENTO DE SISTEMA: 
ANÁLISE DE PERFORMANCE DE ALGORITMO DE ORDENAÇÃO DE DADOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SÃO PAULO 
2016 
 
 
FELIPE CUNHA SANTOS / C7625F-2 
KAIO DA FONSECA GONÇALVES DA SILVA / C5347A-3 
LUCAS BRITTO DA SILVA / C75FCF-1 
WILLIAN COSTA BARBOSA / C59285-4 
 
 
 
 
 
 
 
 
 
 
DESENVOLVIMENTO DE SISTEMA: 
ANÁLISE DE PERFORMANCE DE ALGORITMO DE ORDENAÇÃO DE DADOS 
 
 
 
 
 
 
 
 
 
 
Atividade prática supervisionada 
apresentada ao curso Ciência da 
Computação, para a obtenção de nota na 
mesma. 
 
 
Orientador: Prof. Cesar 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SÃO PAULO 
2016 
 
 
 
SUMÁRIO 
1 DESENVOLVIMENTO ................................................................................ 5 
2 RESULTADOS ........................................................................................... 7 
2.1 Análise individual por método .............................................................. 7 
 2.1.1 Análise Insertion Sort ....................................................................... 8 
 2.1.2 Análise Bubble Sort ......................................................................... 9 
 2.1.3 Análise Selection Sort ...................................................................... 9 
 2.1.4 Análise Shake Sort ........................................................................ 10 
 2.1.5 Análise Quick Sort ......................................................................... 11 
 2.1.6 Análise Merge Sort ........................................................................ 11 
 2.1.7 Análise Heap Sort .......................................................................... 12 
2.2 Comparação entre os métodos em diferentes vetores .................... 13 
 2.2.1 Vetor de 100 posições ................................................................... 13 
 2.2.2 Vetor de 1.000 posições ................................................................ 14 
 2.2.3 Vetor de 5.000 posições ................................................................ 15 
 2.2.4 Vetor de 10.000 posições .............................................................. 16 
 2.2.5 Vetor de 100.000 posições ............................................................ 17 
 2.2.6 Vetor de 500.000 posições ............................................................ 18 
 2.2.7 Vetor de 1.000.000 posições ......................................................... 19 
 2.2.8 Vetor de 5.000.000 posições ......................................................... 20 
3 CONCLUSÃO ........................................................................................... 21 
FICHAS DE ATIVIDADE ................................................................................ 23 
 
ANEXO A - Software utilizado para análise de performance .......................... 25 
 
 
 
 
4 
 
5 
 
1 DESENVOLVIMENTO 
 
O software funciona de maneira simples. O algoritmo pede ao usuário o 
tamanho do vetor que deverá ser ordenado, logo em seguida um "vetor pai" é criado 
e preenchido com números aleatórios. 
Para evitar problemas com falta de memória e para que todos os métodos 
sejam analisados com o mesmo vetor, a cada método que será executado, um 
"vetor filho" é criado e os valores do "vetor pai" são transferidos para ele de forma 
que se torne uma copia. 
Os algoritmos de ordenação são executados um de cada vez, de modo que 
antes de iniciar, um "vetor filho" é alocado e recebe os valores do "vetor pai", e após 
ser executado, contadores internos retornam o numero de interações realizadas 
durante o processo de ordenação, e logo em seguida o "vetor filho" é desalocado da 
memória dando espaço ao próximo "vetor filho" a ser criado para o próximo método 
de ordenação. 
Os valores retornados pelo contadores serão utilizados para o a criação de 
gráficos que indicam a performance do algoritmos ao longo dos diferentes tamanhos 
de vetores. 
 
 
6 
 
7 
 
2 RESULTADOS 
 
 Para a realização das análises, trabalharemos em cima de vetores aleatórios 
iguais para todos o métodos, e foram estipulados os seguintes tamanhos de vetores: 
100; 1.000; 5.000; 10.000; 100.000; 500.000; 1.000.000; 5.000.000. 
 
Tabela 1 - Interações 
 
Fonte: própria (2016). 
 
 Devemos ter em mente que quanto menor o número de interações, mais 
eficiente é o algoritmo para o determinado caso. 
 
2.1 Análise individual por método 
 
 Os métodos O(n²) devem ter o comportamento parecido com o do gráfico 1, 
onde "n" é igual ao número de elementos do vetor. 
 
Gráfico 1 - n² 
 
Fonte: própria (2016). 
8 
 
 No gráfico 1 podemos perceber que por ser uma função quadratica, os 
números crescem tão rápido que a escala não consegue mostrar todo o 
comportamento no gráfico. 
 Os métodos O(n*log n) devem ter o comportamento parecido com o do gráfico 
2, onde "n" é igual ao número de elementos do vetor. 
 
Gráfico 2 - n*log n 
 
Fonte: própria(2016). 
 
 No gráfico 2 podemos perceber que por ser uma função linear multiplicada 
por uma função logarítmica, os números crescem de forma mais lenta que no gráfico 
1, fazendo com que a escala consiga mostrar ainda mais detalhes do seu 
comportamento no gráfico. 
 
2.1.1 Análise Insertion Sort 
 
 O método Insertion Sort possui notação O(n²) em casos médios e deve ter o 
comportamento parecido com o gráfico 1. 
 O número de interações realizadas pelo algoritmo nos da origem ao gráfico 3. 
 
 
 
 
 
9 
 
Gráfico 3 - Insertion Sort 
 
Fonte: própria(2016). 
 
 2.1.2 Análise Bubble Sort 
 
 O método Buble Sort possui notação O(n²) em casos médios. 
 O número de interações realizadas pelo algoritmo nos da origem ao gráfico 4. 
 
Gráfico 4 - Bubble Sort 
 
Fonte: própria(2016). 
 
2.1.3 Análise Selection Sort 
 
 O método Selection Sort possui notação O(n²) em casos médios e deve ter o 
comportamento parecido com o gráfico 1. 
10 
 
 O número de interações realizadas pelo algoritmo nos da origem ao gráfico 5. 
 
Gráfico 5 - Selection Sort 
 
Fonte: própria(2016). 
 
2.1.4 Análise Shake Sort 
 
 O método Shake Sort possui notação O(n²) em casos médios e deve ter o 
comportamento parecido com o gráfico 1. 
 O número de interações realizadas pelo algoritmo nos da origem ao gráfico 6. 
 
Gráfico 6 - Shake Sort 
 
Fonte: própria(2016). 
 
 
11 
 
2.1.5 Análise Quick Sort 
 
 O método Quick Sort possui notação O(n*log n) em casos médios e deve ter o 
comportamento parecido com o gráfico 2. 
 O número de interações realizadas pelo algoritmo nos da origem ao gráfico 7. 
 
Gráfico 7 - Quick Sort 
 
Fonte: própria(2016). 
 
2.1.6 Análise Merge Sort 
 
 O método Merge Sort possui notação O(n*log n) em casos médios e deve ter 
o comportamento parecido com o gráfico 2. 
 O número de interações realizadas pelo algoritmo nos da origem ao gráfico 8. 
 
 
 
 
 
 
 
 
 
 
12 
 
Gráfico 8 - Merge Sort 
 
 Fonte: própria(2016). 
 
2.1.7 Análise Heap Sort 
 
 O método Heap Sort possui notação O(n*log n) em casos médios e deve ter o 
comportamento parecido com o gráfico 2. 
 O número de interações realizadaspelo algoritmo nos da origem ao gráfico 9. 
 
Gráfico 9 - Heap Sort 
 
 Fonte: própria(2016). 
 
 
 
 
13 
 
2.2 Comparação entre os métodos em diferentes vetores 
 
2.2.1 Vetor de 100 posições 
 
Gráfico 10 - 100 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
14 
 
2.2.2 Vetor de 1.000 posições 
 
Gráfico 11 - 1.000 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
 
 
15 
 
2.2.3 Vetor de 5.000 posições 
 
Gráfico 12 - 5.000 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
 
 
16 
 
2.2.4 Vetor de 10.000 posições 
 
Gráfico 13 - 10.000 
 
Fonte: própria(2016). 
 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
 
17 
 
2.2.5 Vetor de 100.000 posições 
 
Gráfico 14 - 100.000 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
 
 
18 
 
2.2.6 Vetor de 500.000 posições 
 
Gráfico 15 - 500.000 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
 
 
19 
 
2.2.7 Vetor de 1.000.000 posições 
 
Gráfico 16 - 1.000.000 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
 
 
 
 
 
 
 
 
 
 
 
 
20 
 
2.2.8 Vetor de 5.000.000 posições 
 
Gráfico 17 - 5.000.000 
 
Fonte: própria(2016). 
 
Método com melhor desempenho: Heap Sort. 
Método com pior desempenho: Selection Sort. 
 
21 
 
3 CONCLUSÃO 
 
• O método Heap Sort obteve o melhor desempenho em todos os casos; 
• O método Selection Sort obteve o pior desempenho em todos os 
casos; 
• Através de análises feitas em outros computadores, os métodos Merge 
Sort e Selection Sort mantiveram os números de interações constantes 
independente do cenário; 
• Os métodos O(n*log n) tiveram um desempenho muito superiores aos 
O(n²) em todos os casos; 
• Entre os métodos O(n²) o Insertion Sort foi o melhor em todos os 
casos; 
 
22 
 
23 
 
FICHAS DE ATIVIDADE 
 
Imagem 1 - ficha Felipe 
 
Fonte: própria (2016). 
 
 
Imagem 2 - ficha Kaio 
 
Fonte: própria (2016). 
 
 
24 
 
Imagem 3 - ficha Lucas 
Fonte: própria (2016). 
 
 
Imagem 4 - ficha Willian 
 
Fonte: própria (2016). 
25 
 
ANEXO A - Software utilizado para análise de performance. 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
 
void insertion(int *v, int tam){ 
 int aux, i, j; 
 unsigned long long c1=0; 
 
 for (i=1; i<tam; i++){ 
 aux=v[i]; 
 j=i-1; 
 while ((j>=0) && (aux<v[j])){ 
 v[j+1] = v[j]; 
 j--; 
 c1++; 
 } 
 v[j+1]=aux; 
 c1++; 
 } 
 printf("\n\ncontador = %llu", c1); 
 
} 
 
void bubble(int *v, int tam){ 
 int aux, troca, i, j; 
 unsigned long long c1=0; 
 
 j=tam-1; 
 do { 
 troca=0; 
 for (i=0; i<j; i++){ 
 if (v[i]>v[i+1]){ 
26 
 
 aux=v[i]; 
 v[i]=v[i+1]; 
 v[i+1]=aux; 
 troca=1; 
 } 
 c1++; 
 } 
 j--; 
 c1++; 
 }while (troca); 
 
 printf("\n\ncontador = %llu", c1); 
} 
 
void selection(int *v, int tam){ 
 int menor,posmenor, i, j; 
 unsigned long long c1=0; 
 
 for (i=0; i<tam; i++){ 
 menor=v[i]; posmenor=i; 
 for (j=i+1; j<tam; j++){ 
 if (v[j]<menor){ 
 menor=v[j]; 
 posmenor=j; 
 } 
 c1++; 
 } 
 v[posmenor]=v[i]; 
 v[i]=menor; 
 c1++; 
 } 
 printf("\n\ncontador = %llu", c1); 
 
} 
27 
 
 
void shake(int *v, int tam){ 
 int j,k,l,r, aux; 
 unsigned long long c1=0; 
 
 l=1; 
 r= k=tam-1; 
 do { 
 for (j=r; j>=l; j--){ 
 if (v[j-1]>v[j]){ 
 aux=v[j-1]; 
 v[j-1] = v[j]; 
 v[j] = aux; 
 k=j; 
 } 
 c1++; 
 } 
 l= k+1; 
 for (j=l; j<=r; j++){ 
 if (v[j-1]>v[j]){ 
 aux=v[j-1]; 
 v[j-1] = v[j]; 
 v[j] = aux; 
 k=j; 
 } 
 c1++; 
 } 
 r=k-1; 
 c1++; 
 } while (l<=r); 
 
 printf("\n\ncontador = %llu", c1); 
 
} 
28 
 
 
unsigned long long c1=0, c2=0, c3=0; 
 
int particao (int *vet, int e, int d){ 
 int v, i, j, t; 
 
 v = vet[d]; i = e -1; j = d; 
 do { 
 do{ 
 i = i+1; 
 c1++; 
 }while ((vet[i] < v) && (i< d)); 
 
 do{ 
 j = j-1; 
 c1++; 
 }while ((vet[j] > v) && (j > 0)); 
 
 t=vet[i]; vet[i]=vet[j]; vet[j]=t; 
 c1++; 
 }while (j > i); 
 
 vet[j] = vet[i]; 
 vet[i] = vet[d]; 
 vet[d] = t; 
 
 return i; 
} 
 
void quick(int *v, int e, int d){ 
 int i; 
 c1++; 
 
 if (d >e){ 
29 
 
 i = particao (v, e, d); 
 quick(v, e, i-1); 
 quick(v, i+1, d); 
 } 
 
} 
 
void intercala(int e, int meio, int d, int *v){ 
 int i, j, k, *w; 
 
 w=(int *)malloc((d-e)*sizeof(int)); 
 
 i=e; j=meio; k=0; 
 while (i<meio && j<d){ 
 if (v[i] < v[j]){ 
 w[k] = v[i]; 
 k++; 
 i++; 
 } 
 else{ 
 w[k] = v[j]; 
 k++; 
 j++; 
 } 
 c2++; 
 } 
 
 while (i<meio){ 
 w[k]=v[i]; 
 k++; 
 i++; 
 c2++; 
 } 
 while (j<d){ 
30 
 
 w[k]=v[j]; 
 k++; 
 j++; 
 c2++; 
 } 
 for (i=e; i<d; ++i){ 
 v[i]=w[i-e]; 
 c2++; 
 } 
 
 free(w); 
 
} 
 
 
void merge(int e, int d, int *v){ 
 int meio; 
 c2++; 
 
 if (e<d-1) { 
 meio= (e+d)/2; 
 merge(e, meio, v); 
 merge(meio, d, v); 
 intercala(e, meio, d, v); 
 } 
 
} 
 
void peneira(int p, int m, int *v){ 
 int x = v[p]; 
 while (2*p <= m) { 
 c3++; 
 int f = 2*p; 
 if (f < m && v[f] < v[f+1]){ 
31 
 
 ++f; 
 } 
 if (x >= v[f]){ 
 break; 
 } 
 v[p] = v[f]; p = f; 
 } 
 v[p] = x; 
 
} 
 
void heap(int n, int *v){ 
 int p, m, x; 
 for (p = n/2; p >= 1; --p) { 
 peneira (p, n, v); 
 c3++; 
 } 
 for (m = n; m >= 2; --m) { 
 x = v[1]; 
 v[1] = v[m]; 
 v[m] = x; 
 peneira (1, m-1, v); 
 c3++; 
 } 
 
} 
 
int main(int argc, char *argv[]){ 
 
 int tam, i, *v; 
 printf("Digite o tamanho do vetor: "); 
 scanf("%d", &tam); 
 
 v=(int *) malloc(tam*sizeof(int)); 
32 
 
 
 system("CLS"); 
 
 for (i=0; i<tam; i++){ 
 v[i]=rand()%100000000; 
 } 
 
 int *v1, *v2, *v3, *v4, *v5, *v6, *v7; 
 
printf("INSERTION SORT"); 
v1=(int *) malloc(tam*sizeof(int)); 
for (i=0; i<tam; i++){ 
 v1[i]=v[i]; 
 } 
 printf("\n\nvetor trasferido"); 
 insertion(v1, tam); 
 printf("\n\nvetor ordenado"); 
 free(v1); 
 
printf("\n\n\n\nBUBBLE SORT"); 
v2=(int *) malloc(tam*sizeof(int)); 
for (i=0; i<tam; i++){ 
 v2[i]=v[i]; 
 } 
 printf("\n\nvetor trasferido"); 
 bubble(v2, tam); 
 printf("\n\nvetor ordenado"); 
 free(v2); 
 
printf("\n\n\n\nSELECTION SORT"); 
v3=(int *) malloc(tam*sizeof(int));for (i=0; i<tam; i++){ 
 v3[i]=v[i]; 
 } 
33 
 
 printf("\n\nvetor trasferido"); 
 selection(v3, tam); 
 printf("\n\nvetor ordenado"); 
 free(v3); 
 
printf("\n\n\n\nSHAKE SORT"); 
v4=(int *) malloc(tam*sizeof(int)); 
for (i=0; i<tam; i++){ 
 v4[i]=v[i]; 
 } 
 printf("\n\nvetor trasferido"); 
 shake(v4, tam); 
 printf("\n\nvetor ordenado"); 
 free(v4); 
 
printf("\n\n\n\nQUICK SORT"); 
v5=(int *) malloc(tam*sizeof(int)); 
for (i=0; i<tam; i++){ 
 v5[i]=v[i]; 
 } 
 printf("\n\nvetor trasferido"); 
 quick(v5, 0, tam-1); 
 printf("\n\ncontador = %llu", c1-1); 
 printf("\n\nvetor ordenado"); 
 free(v5); 
 
printf("\n\n\n\nMERGE SORT"); 
v6=(int *) malloc(tam*sizeof(int)); 
for (i=0; i<tam; i++){ 
 v6[i]=v[i]; 
 } 
 printf("\n\nvetor trasferido"); 
 merge(0, tam, v6); 
 printf("\n\ncontador = %llu", c2-1); 
34 
 
 printf("\n\nvetor ordenado"); 
 free(v6); 
 
printf("\n\n\n\nHEAP SORT"); 
v7=(int *) malloc(tam*sizeof(int)); 
for (i=0; i<tam; i++){ 
 v7[i]=v[i]; 
 } 
 printf("\n\nvetor trasferido"); 
 heap(tam-1, v7); 
 printf("\n\ncontador = %llu", c3); 
 printf("\n\nvetor ordenado"); 
 free(v7); 
 
 printf("\n\n\nPERFORMANCE ANALIZADA!!!"); 
 getch(); 
}