APS - Ordenação

Prévia do material em texto

XV
INTRODUÇÃO
Um tipo de algoritmo muito usado na resolução de problemas computacionais são os algoritmos de ordenação, que servem para ordenar ou organizar uma lista de números ou palavras de acordo com a sua necessidade. Os principais algoritmos de ordenação atualmente são:
Bubblesort
Ou ordenação por flutuação por bolha, é o mais simples algoritmo de ordenação. Sua ideia é de percorrer o vetor diversas vezes, a cada passagem fazendo com que os valores ‘borbulhem’ para o topo o maior elemento da sequência. Essa movimentação lembra a forma como bolhas em um tanque de água procuram o seu próprio nível, e é dai que vem o nome do algoritmo.
É um algoritmo lento para ordenar grandes números de elementos, mas muito eficiente com poucos.
Complexidade:
· Adaptativo: O(n) comparações e trocas se o algoritmo estiver parcialmente ordenado.
· Pior caso: O(n²), Caso médio: O(n²) e Melhor caso: O(n).
Selectionsort
‘Ordenação por seleção’ é um algoritmo baseado em se passar sempre o menor valor do vetor para a primeira posição, depois o de segundo valor para a segunda posição e assim por diante, com os (n-1) elementos restantes até os últimos dois elementos. Este algoritmo é bom para trabalhar com até, pelo menos, 10.000 elementos, visto sua simplicidade de implementação.
Complexidade:
· Pior caso: O(n²); Caso médio: O(n²); Melhor caso: O(n).
Heapsort
O heapsort é um método de ordenação cujo princípio de funcionamento é o mesmo utilizado para a ordenação por seleção (selectionsort). Seleciona o maior item do vetor e o troca com o item que está na primeira posição. Repetindo a operação com os n-1 itens restantes, depois com os n-2 itens e assim sucessivamente.
Utiliza um “heap binário’ para manter o próximo elemento a ser selecionado – arvore binária mantida na forma de vetor – o heap é gerado e mantido no próprio vetor a ser ordenado.
Complexidade:
· Pior caso: O(n log n); Caso médio: O(n log n); Melhor caso O(n log n).
Insertionsort
Ou ordenação por inserção é o método que percorre um vetor de elementos da esquerda para a direita e à medida que avança vai ordenando os elementos à esquerda. O funcionamento do algoritmo é bem simples, consiste em a cada passo a partir do segundo elemento selecionar o próximo item da sequência e coloca-lo no local apropriado de acordo com o critério de ordenação.
Este é geralmente utilizado para ordenar um pequeno número de valores, onde se faz muito eficiente.
Complexidade:
· Pior caso: O(n²); Caso Médio: O(n²); Melhor caso: O(n).
 E dentre eles estão os algoritmos de ordenação Quicksort e Mergesort que serão abordados de forma mais ampla em seguida neste trabalho.
REFERENCIAL TEÓRICO
Os algoritmos de ordenação escolhidos pelo próprio orientador do projeto para o desenvolvimento do trabalho foram:
1. Quicksort
Método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rápido. Foi publicado em 1962 após uma série de refinamentos.
O quicksort adota a estratégia de “divisão e conquista”. A estratégia consiste em rearranjar as chaves de modo que as chaves “menores” precedam as chaves “maiores”. Em seguida o quicksort ordena as duas sub listas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são:
· Escolha um elemento da lista, denominado “pivô”;
· Particiona: rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub listas não ordenadas;
· Partição: recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores;
O caso da base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
A escolha do pivô e os passos ‘Particiona’ podem ser feitos de diferentes formas e a escolha de uma implementação específica afeta fortemente a performance do algoritmo.
O quicksort é um algoritmo de ordenação por comparação não estável.
2. Mergesort
Criado em 1945 pelo matemático americano John Von Neumann. O mergesort, ou ordenação por mistura, é um outro exemplo de algoritmo de ordenação por comparação do tipo “dividir para conquistar”.
Sua ideia básica consiste em “dividir” (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e “conquistar” (após todos os subproblemas terem sidos resolvidos ocorre a conquista que é a união das resoluções dos subproblemas). Como o algoritmo mergesort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas.
Os três passos úteis dos algoritmos de divisão e conquista que se aplicam ao mergesort são:
· Dividir: calcula o ponto médio do sub arranjo, o que demora um tempo constante O(1);
· Conquistar: recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com 2T(n/2) para o tempo de execução;
· Combinar: unir o sub arranjos em um único conjunto ordenado, que leva o tempo O(n).
É possível implementar o mergesort utilizando somente um vetor auxiliar ao longo de toda a execução, tomando assim a complexidade de espaço adicional igual a O(n log n).
É um algoritmo estável na maioria das implementações em que elas podem ser iterativas ou recursivas.
3. Shellsort
Criado por Donald Shell em 1959, com a ideia de dividir um grande vetor de dados em vetores menores, ordenando-os e fazendo isso novamente para ter um único vetor praticamente ordenado e então trabalhar em cima dele.
O método é uma extensão do algoritmo de ordenação por inserção (Insertsort). Ele permite a troca de registros distantes um do outro, diferente do algoritmo de ordenação por inserção. A complexidade do algoritmo é desconhecida, ninguém ainda foi capaz de encontrar uma ‘fórmula fechada’ para a sua função de complexidade.
Principais características:
· Shellsort se baseia em uma variável chamada de “incremento”, que é dado por h e ao decorrer da execução do algoritmo, é decrementada até 1.
· O algoritmo compara elementos distantes em um vetor, em vez de comparar os adjacentes.
· A ordenação é realizada várias vezes, usando uma sequência de valores do “incremento de shell” (h1, h2, ..., hn) onde começando por hn selecionamos apenas os valores que estão no hn elementos distantes um do outro. Então ordenamos estes elementos com o Insertsort.
O método não é estável.
DESENVOLVIMENTO
No desenvolvimento do sistema computacional foi utilizado um laptop da fabricante Samsung com processador Intel® Core™ i3 – 5005U CPU @ 2.00GHz, RAM de 4.00 GB, sistema operacional Windows 10 Home Single Language baseado em x64. O principal software utilizado no processo foi o ambiente de desenvolvimento integrado livre Dev-C++ x64 na versão 5.11, que utiliza os compiladores do projeto GNU para compilar programas para o sistema operacional Microsoft Windows.
O principal livro utilizado e recomendo pelo orientador do projeto foi “Projetos de Algoritmos com implementação em Pascal e C” do autor brasileiro Nivio Ziviani.
A linguagem utilizada foi a linguagem de programação C++.
Algoritmos de Ordenação
1. Quicksort
O algoritmo de ordenação de Quicksort possui dois métodos: o método principal quicksort e o método “particiona”. O método quicksort declara a variável inteira do pivô e verifica if (início < fim) se a posição ‘inicio’ for menor que a posição ‘fim’, o pivô separa os dados em duas partições pivô=particiona (V, início, fim) e ordena as partições com o pivô na posiçãomaior e menor.
Anexo 1 – Método quicksort
O método particiona determina o pivô e repete while (início < fim) enquanto a posição de início for menor que a posição fim e enquanto o elemento o vetor[fim] for igual ou menor que o pivô, diminuímos a posição início. Se for menor ou igual ao vetor[inicio] aumentamos a posição início.
2. Mergesort
O algoritmo de Mergesort possui um método que verifica se o fim é maior que o início if (fim > início) e determina a metade do arranjo de números. Divido na metade, passando como parâmetro o arranjo da posição inicial para a metade seguinte que passa o parâmetro desde a posição da metade anterior até a posição final. For (i=l+1; i>início; i--) passamos pelo vetor ‘cortado’ atribuindo os elementos a uma correção temporária, for (j=l; j<fim; j++) atribuímos o elemento na posição correta e por assim for (k=início; k<=fim; k++) determinando qual é o menor elemento e caso contrário mudando para a posição anterior.
Anexo 2 – Método mergesort
3. Shellsort
O algoritmo de Shellsort é o mais simples de todos já que é apenas uma extensão para outros algoritmos. Possui um laço while (k > 0) enquanto k for maior que 0 percorre os números aleatórios criados na condição for e acrescenta em outro laço while ((j >= k) && (V[j=k] > aux)) contanto que j seja maior ou igual a k e o vetor de j-k maior que o auxiliar e atribui os elementos na sua posição correta.
Anexo 3 – Método shellsort
Obtenção de Dados
Nos foi orientado que fizéssemos o projeto com 100 mil números aleatórios. Utilizamos para a obtenção dos números das ordenações a da função srand (time (NULL)) e em seguida guardamos os números aleatórios em um vetor.
Anexo 4 – Código gerador de números aleatórios
Srand (time (NULL)) faz uso do relógio interno do computador para controlar a escolha da “semente”. Como o tempo está mudando continuamente, a semente está sempre mudando.
As imagens abaixo ilustram os valores de antes e depois da ordenação realizada por cada algoritmo:
Anexo 5 – Quicksort não ordenado
Anexo 6 – Quicksort ordenado
Anexo 7 – Mergesort não ordenado
Anexo 8 – Mergesort ordenado
Anexo 9 – Shellsort não ordenado
Anexo 10 – Shellsort ordenado
RESULTADOS
Os cenários testados neste projeto foram de 5 mil, 10 mil e 100 mil números aleatórios, gerando os seguintes resultados:
1. Quicksort
Gráfico 1 – Tempo de execução do Quicksort
Tabela 1 – Tempo de execução do Quicksort
Vantagens:
· É extremamente eficiente para ordenar arquivos de dados
· Necessita apenas de uma pequena pilha como memória auxiliar
· Requer cerca de n log n comparações em média para ordenar n itens
Desvantagens:
· Tem um pior caso O(n²) comparações
· Sua implementação é muito delicada e difícil, um pequeno erro pode levar a efeitos inesperados para algumas entradas de dados
2. Mergesort
Gráfico 2 – Tempo de execução do Mergesort
Tabela 2 – Tempo de execução do Mergesort
Vantagens:
· Fácil implementação
· Indicado para aplicações que tem restrição de tempo
· Pior caso: O (n log n)
Desvantagens:
· Utiliza memória auxiliar
· Mais lento que o Quicksort no caso médio
3. Shellsort
Gráfico 3 – Tempo de execução do Shellsort
Tabela 3 – Tempo de execução do Shellsort
Vantagens:
· Shellsort é uma ótima opção para arquivos de tamanho moderado
· Sua implementação é simples e requer uma quantidade de código pequena
Desvantagens:
· O tempo de execução do algoritmo é sensível a ordem inicial do arquivo
CONSIDERAÇÕES FINAIS
Este trabalho levantou os conceitos, aplicações e usos dos algoritmos de ordenação, mas especificamente, estudados os algoritmos mergesort, quicksort e shellsort. Existem n algoritmos de ordenação, para tanto foi feita uma revisão sobre ordenação, pesquisa de dados, estrutura de dados, tipos de dados, algoritmos mais conhecidos e da linguagem de programação C.
A partir dos três algoritmos citados anteriormente, foi realizado uma banca de testes com cinco cenários distintos: 5.000, 10.000 e 100 mil dados em um programa desenvolvido na linguagem C, demonstrando a capacidade de cada algoritmo em cada cenário.
Diante de tudo que foi apresentado, conclui-se que a ordenação é um conceito totalmente necessário e importante nos meios de manipulação de informação que utilizamos hoje, já que há um crescente aumento na busca e atualização das mesmas. Dependendo do ambiente, algumas técnicas de ordenação se sobressaem em relação a outras, mas se o proprietário desejar ter uma velocidade de ordenação elevada terá que investir no ambiente em que a técnica de ordenação irá atual.
Não existe melhor técnica de ordenação, cada uma será excelente no ambiente certo. Não é porque o quicksort demonstrou melhor desempenho que ele seja o melhor de todos em qualquer cenário. Vale ressaltar os riscos de os dados não serem aleatórios e a escolha equivocada do pivô o deixa com O(n) e vimos que O(n²) é o pior desempenho de todos, consumindo muita memória RAM e levando mais tempo para ordenar dados em excesso. Então vale uma análise deligada para determinar qual algoritmo será implementado.
REFERÊNCIAS BIBLIOGRÁFICAS 
ZIVIANI, Nivio. Projetos de Algoritmos: com implementações em Pascal e C. 2004 
FERREIRA, Fernando. Algoritmos de Ordenação. 29 de Janeiro de 2011. <Disponível em: codigoecafe.com>
VIANA, Daniel. Conheça os principais algoritmos de ordenação. 26 de Dezembro de 2016. <Disponível em: www.treinaweb.com.br>
OLIVEIRA, Bernando. Estruturas de Dados I. 10 de Maio. <Disponível em: cadernogeek.wordpress.com>
CÓDIGO FONTE
1.Quicksort
#include <stdio.h>
#include <stdlib.h> 
#include <time.h> //para usar o tempo em srand
void quicksort (int V[], int inicio, int fim);
int particiona (int V[], int inicio, int fim);
int main() {
	int i, V[5000]; //definição das variáveis contador e vetor
	
	srand(time(NULL)); //usamos um argumento como parâmetro para gerar números aleatórios
	for (i=0; i<5000; i++) //geramos os números aleátorios e os guardamos num vetor
	 V[i] = rand()%5000;
	 
	printf("Numeros Gerados: "); // imprime o vetor com os numeros gerados
	for (i=0; i<5000; i++)
	 printf("%i ", V[i]);
	 printf("\n");
	 
	quicksort (V, 0, 5000-1); // ordena o vetor a partir do método quicksort
	 
	printf("Numeros Ordenados: "); // imprime o vetor com os numeros agora ordenados
	for (i=0; i<5000; i++)
	 printf("%i ", V[i]);
	 printf("\n");
	
	system("pause");
 system("cls");
 main();
	
	system("pause"); 
	return EXIT_SUCCESS;
}
void quicksort (int V[], int inicio, int fim){ //método quicksort
	int pivo; // váriavel intira para o pivô
	
	if (inicio < fim){ // Se a posição 'inicio' for menor que fim
		pivo = particiona (V, inicio, fim); // Separa os dados em duas partições
		quicksort (V, inicio, pivo); //ordenamos o pivô para a posição mais alta
		quicksort (V, pivo+1, fim); //ordenamos o menor pivô com o parametro pivô+1
	}
}
int particiona (int V[], int inicio, int fim){
	int pivo, aux; 
	
	pivo = V[inicio]; //determinamos o pivô
	
	while (inicio < fim){ // repete - enquando a posição inicio for menor que fim
		while ((inicio < fim) && (V[fim] >= pivo)) -- fim; // enquando a posição inicio for menor que fim e o elemento na posição e pelo menos igual ou menor que o pivo diminuimos a posição inicio
		aux = V[inicio];
		V[inicio] = V[fim];
		V[fim] = aux;
		
	while ((inicio < fim) && (V[inicio] <= pivo)) ++ inicio; // enquando a posição inicio for menor que a posição fim e o elemento no vetor inicio for menor ou igual ao vetor aumentamos a posição inicio
	 aux = V[inicio]; // mudamos as posições dos elementos nas posições inicio e fim
	 V[inicio] = V[fim];
	 V[fim] = aux;
	}
	return inicio;
}
2.Mergesort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void mergesort (int inicio, int V[], int fim);
int main(){
	int i, V[100000];
	
	srand(time(NULL));
	for (i=0; i<100000; i++)
	 V[i] = rand()%100000;
	
	printf("Numeros Gerados: ");
	for (i=0; i<100000; i++)
	 printf("%i ", V[i]);
	 printf("\n");
	 
	mergesort (0, V, 100000-1);
	
	printf("Numeros Ordenados: ");
	for (i=0; i<100000;i++)
	 printf("%i ", V[i]);
	 printf("\n");
	 
	system("pause");
	return EXIT_SUCCESS;
}
void mergesort (int inicio, int V[], int fim){ // método mergesort
	int i, j, k, l, Va[100000];
	
	if (fim > inicio){ // verifica até quando o vetor chega no final
		l = (inicio + fim) / 2; // Determinamos a metade do arranjo de numeros
		
	mergesort (inicio, V, l); // Cortamos ao meio, passando como parâmetro o arranjo da posição inicial para a metade seguinte
	mergesort (l+1, V, fim); // Cortamos passando por parâmetro o arranjo desde a posição da metade anterior até a possição final da metade atual
	
	for (i=l+1; i>inicio; i--) // passamos pelo vetor cortado
	 Va[i-1] = V[i-1]; // atribuimos os elementos a uma correção temporária
	 
	for (j=l; j<fim; j++)
	 Va[fim + l - j] = V[j+1]; // atribuimos o elemento na posição correta
	 
	for (k=inicio; k<=fim; k++) // "andamos e designamos" para determinar qual é o menor elemento
	 if (Va[i] < Va[j])
	 V[k] = Va[i++];
	 else // caso contrário, mude para a posição anterior
	 V[k] = Va[j--];
	}
}
3.Shellsort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
	int i, j, k, aux, V[100000];
	srand (time(NULL)); // Utilizamos um argumento para gerar numeros aleatorios
	for (i=0; i<100000; i++) //Geramos os numeros aleatórios no vetor
	 V[i] = rand()%100000; //numeros aleatórios de 0 a 100.000
	
	printf("Numeros gerados: "); // imprime o vetor de numeros aleatórios gerados
 for (i=0; i<100000; i++)
 printf("%i ", V[i]);
 printf("\n");
 
 k = 100000/2; // método shellshort
 while (k > 0){ //contando que k seja maior que 0 
 	for (i=0; i<100000; i++){
 		j=i;
 		aux = V[i];
 		while ((j >= k) && (V[j-k] > aux)){ // contanto que j seja maior ou igual a k e vetor de j-k maior que o auxiliar
 			V[j] = V[j-k];
 			j = j-k;
			}
			V[j] = aux;
		}
		k /= 2;
	}
	printf("Numeros Ordenados: "); // imprime o vetor de numeros agora ordenados
	for (i=0; i<100000; i++)
	 printf ("%i ", V[i]);
	 printf("\n");
	
	system("pause");
	return EXIT_SUCCESS;
}