DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

Prévia do material em texto

UNIVERSIDADE PAULISTA
CIÊNCIA DA COMPUTAÇÃO
ANDRÉ BITTENCOURT	D424EG-8
DIEGO MARTINEK		D4921F-0
KEVEN GOMES	N206CH-7
LUCAS MESQUITA	N190FE-0
ATIVIDADE PRÁTICA SUPERVISIONADA
DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
SÃO PAULO
2018
ÍNDICE...............................................................................................................03
OBJETIVO DO TRABALHO........................................................................04
INTRODUÇÃO............................................................................................05
REFERENCIAL TEÓRICO..........................................................................07
 Bubble Sort...........................................................................................07
 Quick Sort.............................................................................................08
 Selection Sort........................................................................................11
DESENVOLVIMENTO.................................................................................12
Função preenche...................................................................................12
Função iguais.........................................................................................12
Função mostra.......................................................................................12
Método Bubble sort................................................................................13
Método Selection sort............................................................................13
Método Quick sort..................................................................................13
Função Main..........................................................................................13
RESULTADOS E DISCUSSÕES................................................................17
Gráficos individuais de cada método.....................................................17
Gráficos de comparação entre os três métodos....................................19
CONSIDERAÇÕES FINAIS........................................................................20
BIBLIOGRAFIA............................................................................................21
CÓDIGO FONTE.........................................................................................22
1. OBJETIVO DO TRABALHO
	O objetivo do trabalho é tratar sobre um conteúdo trabalhado na disciplina de Estrutura de Dados, esse trabalho tem como função apresentar o que são métodos de ordenação, apresentar os temas escolhidos pelo grupo, demostrar como funcionam e aplicá-los. Desenvolvendo um programa na linguagem C++, utilizando as técnicas e colocando em prática os algoritmos de ordenação aprendidos em laboratório. 
2. INTRODUÇÃO
	O objetivo de uma ordenação é de organizar tais elementos em uma sequência muitas vezes numéricas, alfabéticas, alfanuméricas entre outros padrões desejados pelo individuo organizador. Tornando assim mais eficiente, simples e viável tanto para o seu manuseio quanto para a recuperação de um eventual dado.
	Um dos exemplos clássicos de ordenação necessária em nosso cotidiano é a lista telefone no momento em buscar o número desejado ou na busca de um livro na biblioteca, ambos são organizados em tal ordenança que favoreça a praticidade na busca do desejado. Na lista telefônica é organizada pelo nome do contato, mas na biblioteca é feita por vários atributos como pelo título, gênero ou edição. 
	Na área de ciência da computação, à algoritmos para esse propósito. No básico funciona da seguinte forma: Á uma sequência de n itens ou elementos r[0], r[1], ... r[n-1]; assim a chave a[i] está associada em elemento r[i] e usualmente a chave é um campo do registro, logo os elementos estão classificados pela chave.
A ordenação tem por objetivo reorganizar as chaves de forma que obedeçam a uma regra. Se os elementos representam registros de um arquivo, sendo representado por uma lista sequencial em memória principal a ordenação é interna, mas se o arquivo estiver em memória secundária a ordenação é externa.
A ordenação é estável se preserva a ordem relativa das chaves iguais (senão, instável) ‏. E os algoritmos podem operar sobre o elemento ou sobre uma tabela de ponteiros, se registro é muito grande a ordenação é indireta, senão, os registros não são reorganizados e sem os índices, outro caso, as chaves tanto podem ficar armazenadas com os registros ou com os ponteiros.
Há exemplos de métodos que valem ser destacados. Citamos:
Métodos simples:
Insertion sort
Selection sort
Bubble sort
Comb sort
Métodos sofisticados:
Merge sort
Heapsort
Shell sort
Radix sort
Gnome sort
Counting sort
Bucket sort
Cocktail sort
Timsort
Quick sort
Métodos de pesquisa
Pesquisa binária
Busca linear
BogoBusca
	E nesse trabalho, será apresentado com mais detalhes e pesquisas os métodos Selection sort, Bubble sort e o Quick sort. Vale destacar que não existe um método universal melhor do que o outro, pois vale analisar as características dos dados e do problema em causa. Assim decide o melhor método para tal situação.
3. REFERENCIAL TEÓRICO:
3.1 Bubble Sort
Bubble Sort é um algoritmo de ordenação que pode ser aplicado em Arrays e Listas dinâmicas. Durante o processo de ordenação a posição atual é sempre comparada com a próxima posição. Quando o objetivo é ordenar em forma decrescente e a posição atual for maior que a posição posterior, é realizada a troca dos valores nessa posição. 
O mesmo é o caso quando o objetivo é ordenar em forma crescente, sendo a posição atual ser menor que a posição posterior como o diferencial entre as duas formas. E em ambas as formas caso o contrário aconteça, não é realizada a troca, apenas passa-se para o próximo par de comparações.
Por ser um método simples ele é mais usado para prática inicial e assim ajudar com a introdução aos algoritmos de ordenação. Por esse mesmo motivo que ele não é usado em situações com complexidade mediana ou alta, como por exemplo, a ordenação de uma lista com mais de 10 mil de números, nesse caso ele teria um desempenho de n elevado a segunda (sendo n o tamanho do vetor), somente quando há vetores quase ordenados que seu desempenho muda para n.
Exemplo: Vetor {5, 4, 2 ,1 ,3}
3.2 Quick Sort
O Quicksort, desenvolvido em 1960 por Tony Hoare, é um dos algoritmos de ordenação mais conhecidos. Por ser um dos mais eficientes é largamente utilizado em projetos de linguagens de programação. Ele utiliza o paradigma de programação Dividir para Conquistar ou divide and conquer. Esse paradigma é uma abordagem recursiva em que a entrada do algoritmo é ramificada múltiplas vezes a fim de quebrar o problema maior em problemas menores da mesma natureza. No caso do Quicksort o método partition() é responsável por implementar o paradigma.
Dado a sequência de entrada, o método particionador deve primeiramente escolher um elemento que chamaremos de pivô. Em seguida iterar sobre toda a sequência a fim de posicionar todos elementos menores do que esse pivô à sua esquerda. A escolha do pivô pode ser feita aleatoriamente, ser o primeiro elemento ou o último. Em nossa implementação utilizaremos o último elemento da sequência.
Imagine a seguinte sequência: <5, 1, 4, 2, 3>
O pivô dessa sequência será o número 3. Ao iterar, da esquerda para direita, em toda a sequência, toda vez que encontrarmos um elemento cujo valor seja menor do que nosso pivô iremos colocá-lo à esquerda do pivô.
Para saber qual elemento já trocamos, devemos manter uma variável i, que nos permite controlar quais elementos já foram trocados, da esquerda para direita. Ao final de toda a iteração da sequência, pegamos nosso pivô (último elemento) e trocamos com a posição atual da variável i.
Assim, temos que à esquerda da posição atual do nosso pivô, todos elementos são menores do que ele. Consequentemente, portermos iterado toda a sequência, todos os elementos à direita são maiores do que o pivô. Temos assim, a sequência particionada. 
É importante ressaltar que, tanto à esquerda quanto à direita, os elementos não estão completamente ordenados. Mas podemos afirmar com certeza que em relação ao pivô estão. Nesse momento podemos então chamar recursivamente a subsequência à esquerda e à direita até elas estejam completamente ordenadas.
Note que, ao chamarmos recursivamente o particionamento, cada subsequência terá novos pivôs, o que fará com que problemas maiores sejam quebrados em problemas menores de mesma natureza.
O método de particionamento tem um papel central na solução. Esse método percorre por completo o vetor a ser ordenado. Logo, temos que esse método tem complexidade de tempo na Ordem (n), onde n é tamanho do vetor. Ou seja, em um vetor de 10 posições, esse método fará 10 iterações O(n). Como o Quicksort chama o particionamento recursivamente reduzindo o problema em problemas menores, temos que essa recursão tem complexidade em O (log n). Assim, no caso médio, temos que o Quicksort como um todo tem complexidade na Ordem (n log n). Ou seja, n vezes log n.
A complexidade de espaço é de Ordem (log n). Uma vez que todas as operações são feitas in-place, ou seja, diretamente no vetor e que a cada particionamento temos um vetor menor a ser ordenado. Fazemos uso de uma variável auxiliar no método swap. No entanto é possível fazer a troca in-place sem uso de variável auxiliar/temporária. 
No pior caso, o Quicksort tem complexidade O (n²). Imagine um vetor que já esteja ordenado e uma implementação de particionamento que utilize o elemento mais à esquerda como pivô. Nesse cenário o algoritmo cairá em seu pior caso resultando em n² iterações.
Exemplo: Vetor {25, 57, 48, 37, 12, 92, 86,33}
3.3. Selection Sort
O método de ordenação por seleção (selection sort) é um algoritmo como próprio nome diz, de ordenação, que consiste em passar o menor valor do vetor para a primeira posição, depois o segundo menor elemento para a segunda posição e assim segui o processo com os demais valores até que o conjunto esteja completamente em ordem. 
Breve exemplo: Ordenando {9,2,6,3,5,7} usando ordenação por seleção.
4. DESENVOLVIMENTO
Neste capítulo abordaremos os estágios do processo de desenvolvimento do sistema computacional, realizado para a análise de performance dos algoritmos de ordenação de dados (Bubble Sort, Selection Sort e Quick Sort). O código fonte estará disponível no último capítulo deste trabalho.
O programa é composto por sete funções, que serão explicadas abaixo, e uma constante TAM onde se define um valor fixo que será armazenado na memória do computador e usado como tamanho dos vetores para o desenvolvimento do sistema.
4.1 Função preenche
Função, sem retorno, usada para preencher um vetor de com números inteiros de forma aleatória com tamanho TAM.
4.2 Função iguala
Função, sem retorno, que tem dois vetores inteiros como parâmetros de entrada, onde o vetor “vn” será igualado a um outro vetor, que neste caso será o vetor preenchido de forma aleatória. Criou-se essa função para que se pudesse igualar três vetores ao vetor preenchido de forma aleatória, sendo esses três vetores, idênticos, usados um para cada método de ordenação, assim garantindo a integridade na análise dos resultados obtidos a partir dos métodos.
4.3 Função mostra
Função que irá mostrar na tela todos os números de um vetor. Será usado principalmente para mostrar o vetor aleatório e depois os vetores ordenados.
4.4 Método Bubble sort
Função do método de ordenação bolha, que irá ordenar um dos vetores igualados e retornar o número de trocas que o método bolha realizou para ordenar o vetor.
4.5 Método Selection sort
Função do método de ordenação por seleção, que irá ordenar um dos vetores igualados e retornar o número de trocas que o método seleção realizou para ordenar o vetor.
4.6 Método Quick sort
Função do método de ordenação quick sort que irá ordenar um dos vetores igualados, de acordo com as explicações nos capítulos anteriores, e assim como os métodos já descritos irá retornar o número de trocas que o método realizou para ordenar o vetor.
4.7 Função Main
Função que define o início da execução do programa, nela foram declaradas as variáveis vetor, v1, v2 e v3 do tipo inteiro e de tamanho TAM, onde vetor será preenchido automaticamente e v1, v2 e v3 serão igualados a vetor. Também foram declaradas as variáveis troca1, troca2 e troca 3, do tipo inteiro para obter a quantidade de trocas que cada método de ordenação realizou, e as variáveis para obter o tempo de método para as ordenações, tempo1, tempo2 e tempo3 do tipo inteiro.
O tempo de cada método será obtido através da função “GetTickCount”, que é uma função disponível no Windows que retorna à quantidade de milissegundos desde a inicialização do Windows, assim foi declarado também as variáveis início e fim que irão receber a função GetTickCount, usando a variável início antes de chamar a função do método de ordenação e usar a variável fim após o uso do método teremos a variação da quantidade de milissegundos necessária para se obter o tempo de cada método.
Após a declaração de todas variáveis foram chamados a função preenche (para preencher de forma aleatória o vetor) e a função iguala para os vetores v1, v2 e v3.
Logo em seguida for chamada as funções dos métodos de ordenação (Bubble Sort, Selection Sort e Quick Sort), cada uma usando um vetor igualado, uma variável de tempo e uma de troca, para que pudesse ser feita as comparações entre os métodos.
Por fim foi utilizada a função “mostra” para mostrar o vetor preenchido aleatoriamente e os vetores ordenados, mostrados juntos com os dados de tempo e trocas de cada método de ordenação.
Logo abaixo segue uma imagem de exemplo do uso do programa com a constante TAM de tamanho 10.
Figura: Imagem retirada do programa DEV C++ 
5. RESULTADOS E DISCUSSÕES
A seguir serão apresentados e discutidos os dados obtidos pelo programa de análise de performance de algoritmos de ordenação de dados para vetores com os seguintes tamanhos: 1.000; 10.000; 50.000; 100.000; 250.000.
5.1 Gráficos individuais de cada método:
tempo x tamanho vetor			número de trocas x tamanho vetor
tempo x tamanho vetor			número de trocas x tamanho vetor
tempo x tamanho vetor			número de trocas x tamanho vetor
Pelos gráficos individuais de cada método podemos analisar que para os métodos Bolha e Seleção quanto maior o vetor, maior o tempo e o número de trocas realizada em uma forma estável. Agora quando analisamos o método Quick Sort podemos nota uma instabilidade em seu número de trocas, isso se deve à dependência do particionamento do vetor estar balanceado ou não.
5.2 Gráficos de comparação entre os três métodos:
Pelo gráfico tempo x tamanho do vetor, podemos analisar que os métodos bolha e seleção têm tempos muito parecidos, já o método quick sort apresenta um tempo muito menor que os outros.
Já no gráfico número de trocas x tamanho de vetor, vemos que o método quick sort mesmo tendo uma instabilidade na sua quantidade de trocas ainda obtém um ótimo resultados junto do método seleção, já o método bolha tem um número de trocas realizada bem maior que os outros.
6. CONSIDERAÇÕES FINAIS
No presente trabalho foram apresentados três dos métodos de ordenação mais conhecidos (Bubble Sort, Selection Sort e Quick Sort), foram explicados como funcionam e realizado um programa computacional para aplicar esses métodos coletando dados para uma análise de performance entre eles.
Através de gráficos feitos pelas informações obtidas pelo programa, podemos concluir que o método Quick Sort é o algoritmo mais eficiente entre os métodos estudados, sendo este um algoritmo recursivo que demanda uma pequena quantidade de memória adicional, obteve melhores resultados de tempo para processamento e menos trocas realizadas para a ordenação dos vetores em relação aos outros métodos,mesmo tendo seu desempenho instável devido a dependência do particionamento do vetor estar balanceado ou não.
7. BIBLIOGRAFIA:
EMBARCADOS. Algoritmos de Ordenação: Bubble Sort. Disponível em: https://www.embarcados.com.br/algoritmos-de-ordenacao-bubble-sort/
COISA DE PROGRAMADOR. Algoritmos de ordenação - O famoso Bubble Sort. Disponível em: https://www.coisadeprogramador.com.br/algoritmos-ordenacao-bubble-sort/
UNIVERSIDADE DO ALGARVES. Quick Sort. Disponível em: http://w3.ualg.pt/~hshah/ped/Aula%2014/Quick_final.html
DEPARTAMENTO DE CIÊNCIA DE COMPUTADORES FACULDADE DE CIÊNCIAS DA UNIVERSIDADE DO PORTO. Ordenação Quicksort. Disponível em: http://www.dcc.fc.up.pt/~pbv/aulas/progimp/teoricas/teorica19.html
PANTUZA. O Algoritmo De Ordenação Quicksort. Disponível em: https://blog.pantuza.com/artigos/o-algoritmo-de-ordenacao-quicksort
DEVMEDIA. Algoritmos de ordenação: análise e comparação. Disponível em: https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261
WIKIPEDIA. Algoritmo de ordenação. Disponível em: https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO DA UNIVERSIDADE DE SÃO PAULO. SCC-501 - Capítulo 4 Métodos de Ordenação. Disponível em: http://wiki.icmc.usp.br/images/b/b3/SCC501Cap4.pdf
INSTITUDO DE COMPUTAÇÃO DA UNIVERSIDADE FEDERAL FLUMINENSE. Algoritmos de Ordenação. Disponível em: http://www2.ic.uff.br/~boeres/slides_ed/ed4.pdf
8. CÓDIGO FONTE
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <string.h>
//DEFININDO TAMANHO QUE SERA USADO NOS VETORES: 1000 ; 10000 ; 50000 ; 100000 ; 250000
#define TAM 10 
//FUNCAO PARA PREENCHER OS VETORES
void preenche(int *vetor) {
	int i;
	for(i = 0; i < TAM; i++ ){
		vetor[i]=rand()%100;
	}
}
//FUNCAO QUE IRA IGUALAR UM VETOR A OUTRO, NO CASO IGUALAR OS VETORES USADOS PARA ORDENAR COM O VETOR PREENCHIDO
void iguala(int *vetor, int *vn) {
	int i;
	for(i = 0; i < TAM; i++ ){
		vn[i]=vetor[i];		
	}
}
//FUNCAO PARA MOSTRAR UM VETOR
void mostra(int *vetor) {
	int i;
	for( i = 0; i < TAM; i++ ){
		printf("%d \t",vetor[i]);
	}printf("\n");		
}
//FUNCAO DE ORDENACAO PELO METODO BOLHA
int bolha(int *vetor) {
	int i,j,aux,troca=0;
	for( i = 0; i < TAM-1; i++ ){		
		for(j = i + 1; j < TAM; j++){			
			if (vetor[i] > vetor[j]){
				aux = vetor[i];
				vetor[i] = vetor[j];
				vetor[j] = aux;
				troca=troca+1;
			}			
		}
	}
	return troca;
}
//FUNCAO DE ORDENACAO PELO SELECAO 
int selecao (int *vetor){
	int i,j,min,aux,troca=0;
	for( i = 0; i < TAM-1; i++ ){
		min = i;
		for( j = i + 1; j < TAM; j++ ){
			if ( vetor[j] < vetor[min] ){
				min = j;				
			}
		}
	aux=vetor[i];
	vetor[i]=vetor[min];
	vetor[min]=aux;	
	troca=troca+1;
	}
	return troca;
}
//FUNCAO DE ORDENACAO PELO METODO QuickSort
int quick (int *vetor,int inicio,int fim)
{
	int i, j, pivo, aux,troca=0;
	i=inicio;
	j=fim;
	pivo=vetor[(inicio+fim)/2];
	do
	{
		while(vetor[i]<pivo)
		i++;
		while(vetor[j]>pivo)
		j--;
		if(i<=j)
		{
			aux=vetor[i];
			vetor[i]=vetor[j];
			vetor[j]=aux;
			troca=troca+1;
			i++;
			j--;
		}
	}while(i<=j);
	if(inicio<j)
		quick(vetor,inicio,j);
	if(i<fim)
		quick(vetor,i,fim);
	return troca;
}
main() {
int vetor[TAM], v1[TAM], v2[TAM], v3[TAM]; 	//declarando variaveis VETORES
int inicio=0, fim=0, tempo1=0, tempo2=0, tempo3=0;	//declarando variaveis para obter o tempo das ordenacoes
int troca1=0, troca2=0, troca3=0;					//declarando variaveis para obter a qnt de trocas dos metodos
preenche(vetor);		//preenchedo vetor
iguala(vetor,v1);		//igualando v1 a vetor para ser usado no metodo bolha
iguala(vetor,v2);		//igualando v2 a vetor para ser usado no metodo selecao
iguala(vetor,v3);		//igualando v3 a vetor para ser usado no metodo QuickSort
// METODO BOLHA	
inicio = GetTickCount();
troca1=bolha(v1);
fim=GetTickCount();
tempo1=fim-inicio;
// METODO SELECTION
inicio = GetTickCount();
troca2=selecao(v2);
fim=GetTickCount();
tempo2=fim-inicio;
// METODO QuickSort
inicio = GetTickCount();
troca3=quick(v3,0,TAM-1);
fim=GetTickCount();
tempo3=fim-inicio;
printf("\nVetor Preenchido:\n");
mostra(vetor);
printf("\nVetor ordenado (METODO BOLHA):\n");
mostra(v1);
printf("\nVetor ordenado (METODO SELECTION):\n");
mostra(v2);
printf("\nVetor ordenado (METODO QuickSort):\n");
mostra(v3);
// MOSTRANDO RESULTADOS
printf("\n RESUMO para TAMANHO = %d \n\nMETODO\tTEMPO (miliseg)\tTROCAS\nBOLHA \t %d \t %d \nSELECAO \t %d \t %d \nQuickSort\t %d \t %d \n\n",TAM,tempo1,troca1,tempo2,troca2,tempo3,troca3);
system("pause");
}