Metodos de ordenação

Prévia do material em texto

�PAGE �102�
S. Sandri, J. Stolfi, L.Velho
Trabalho de Algoritmos e Estruturas de Dados II
Vinícius Barbosa Honório, Pedro Avelar Pereira Américo.
1. Introdução
Neste trabalho dicutiremos sobre os três metodos de ordenação Quicksorte, Shellsort, Mergesort onde explicaremos o funcionamento de cada um deles asim como sua complexidade, vantagens e desvantagens e também uma comparação entre os metodos.
2. Quicksort
O Quicksort é um metodo de ordenação rápido e eficiente criado pelo Hoare em 1960, e é o algoritmo de ordenação mais rápido que se conhece para uma ampla variedade de situações e provavelmente um dos mais utilizados.
O metodo de ordenação Quicksort funciona da seguinte forma:
A estratégia consiste em rearranjar os conjuntos de modo que um determinado conjunto de dados, sao independentemente separados de um lado esquerdo todos elementos cujos estes elementos sejam maiores que um determinado valor pivo e do lado direito, todos os elementos que sejam menores que este valor pivo e os conjuntos são reagrupados para produzir uma solução final.
O fato de estarem separados pelo pivo em maior e menor que os conjuntos de dados facilita muito o trabalho de ordenação.
O algoritmo para separar os conjuntos consiste em escolher um determinado pivo X, percorre-lo a partir da esquerda ate que o Vetor[i] >= X; depois percorrer a partir da direita ate que Vetor[i]<= X; depois trocar o Vetor[i] com Vetor[j] e continuar o processo ate que os apontadores i e j se cruzem. No final o Vetor[direita,equerda] é separado de forma que os itens de Vetor[esquerda], Vetor[esquerda+1],...,Vetor[i] são menores ou iguais a X e o os elementos do Vetor[i],Vetor[i+1],...,Vetor[direita] são maiores ou iguais a X.
As principais vantagens do método de ordenação Quicksort são :
Melhor opção para ordenar vetores grandes.
Muito rapido pois o laço interno é simples.
As desvantagens sao:
Não é um metodo estavel, nao conhecemos forma eficiente para tornar o Quicksort estavel.
Outra desvantagem é como escolher o pivo.
Implementaçao no Codigo C :
int divide(int vetor[], int esq, int dir){
	int aux;
	int cont=esq;
	int i;
	for(i=esq+1; i<=dir; i++){
		
		if(vetor[i]<vetor[esq]){
			cont++;
			
			aux=vetor[i];
			vetor[i]=vetor[cont];
			vetor[cont]=aux;
		}
	}
	aux=vetor[esq];
	vetor[esq]=vetor[cont];
	vetor[cont]=aux;
	
	return cont;
}
void quick(int vetor[],int esq, int dir){
	int pos;
	if(esq<dir){
		pos=divide(vetor,esq,dir);
		quick(vetor, esq,pos-1);
		quick(vetor,pos+1,dir);
	}
}
2.1 Mergesort
O Mergesort ou tambem chamado “ordenação por mistura” foi proposto por John Von Neumann em 1945. Ainda que exista uma discussão se realmente foi Von Neumann quem criou o metodo as evidencias nao entram em discussao visto que ele fez varias contribuições fascinantes, quem realmente atribuiu a ele a criação do metodo veio de knuth quando publicou no seu livro ‘Arte de Programação’. O Mergesort é um tipo de ordenação de vetores que utiliza um algoritmo do tipo dividir-para-conquistar. A ideia consiste na divisao dos problemas em varios sub problemas atraves da recursividade que é implementado dividindo uma sequencia original em pares de dados, ordena-as e depois as agrupa em sequencias de quatro elementos e assim por diante ate que toda a sequencia é divida em apenas duas partes.
Dividimos a tecnica em tres partes: Divisão, conquista e combinação. A divisao consiste em dividir o problema maior em problemas menore e os menores sao novamente divididos de sucessivamente de maneira recursiva. A conquista é o resultado do problema calculado quando o problema é pequeno o suficiente e a Combinação sao os resultados dos problemas menores combinados ate que seja obtida a soluçao do problema maior.
As vantagens do metodo de ordenação Mergesort é que ele é de facil implementação, indicado para aplicações que tem restrição de tempo, possivel de ser transformado em estavel tomando certos cuidados na implementação.
A desvantagen do Mergesort é que utiliza funções recursivas, por ser recursivo existe um gasto extra de memoria, o algoritmo cria uma copia do vetor para cada nivel da chamada recursiva fazendo um uso maior da memoria.
Implementaçao no Codigo C :
#include <stdio.h>
#include <stdlib.h>
typedef int TChave;
typedef struct {
	TChave Chave;
} TItem;
TItem *Aloca(int n)
{
	return ((n > 0) ? ((TItem *) malloc(n * sizeof(TItem))) : (NULL));
}
int Carrega(TItem **A)
{
	int i, n;
	printf ("Digite o numero de elementos do vetor depois insira os valores : \n\n",n);
	scanf("%d", &n);
	(*A) = Aloca(n);
	for (i = 0; i < n ; i++)
		scanf("%d", &(*A)[i].Chave);
	return n;
}
void Libera(TItem **A)
{
	if ((*A) != NULL) {
		free(*A);
		(*A) = NULL;
	}
}
void Imprime(TItem *A, int n)
{
	int i;
	if (n > 0) {
		printf("%d", A[0].Chave);
		for (i = 1; i < n; i++)
			printf(" %d", A[i].Chave);
		printf("\n");
	}
}
void mergeSort_intercala(TItem *A, int p, int q, int r)
{
 int i, j, k;
 TItem *B;
 B = (TItem *) malloc((r - p + 1) * sizeof(TItem));
 for(i = p; i <= q; i++)
 B[i - p] = A[i];
 for(j = q + 1; j <= r; j++)
 B[r + q + 1 - j - p] = A[j];
 i = p;
 j = r;
 for(k = p; k <= r; k++)
 if(B[i - p].Chave <= B[j - p].Chave) {
 A[k] = B[i - p];
 i = i + 1;
 } else {
 A[k] = B[j - p];
 j = j - 1;
 }
 free(B);
}
void mergeSort_ordena(TItem *A, int p, int r)
{
 int q;
 if(p < r)
 {
 q = (p + r) / 2;
 mergeSort_ordena(A, p, q);
 mergeSort_ordena(A, q + 1, r);
 mergeSort_intercala(A, p, q, r);
 }
}
void mergeSort(TItem *A, int n)
{
 mergeSort_ordena(A, 0, n-1);
}
int main()
{
	TItem *A;
	int n;
	n = Carrega(&A);
	mergeSort(A, n);
	Imprime(A, n);
	Libera(&A);
	return 0;
}
2.2. Shellsort
Proposto por Shell, o “Shellsort” pode ser visto como uma extensão dos algoritmos de ordenação por seleção. A idéia é verificar o primeiro número da sequência e compará-lo ao “h-ésimo”, se este for menor, eles são trocados. Para encontrar o valor de “h” no inicio do algoritmo é utilizado a formula recursiva de: h=h*3+1 || h<n. Esse valor é então dividido por 3, e começasse a verificação.
As vantagens da ordenação por Shellsort sao:
Otima opção para arquivos de tamanho moderado e sua implementação é simples e requer uma quantidade de codigo relativamente pequena.
As desvantagens são:
O tempo de execução do algoritmo é sensivel à ordem inical do arquivo e assim como Quicksort é um metodo não estavel.
4. References
http://homepages.dcc.ufmg.br/~cunha/teaching/20121/aeds2/quicksort.pdf
https://pt.wikipedia.org/wiki/Merge_sort
Cormen, T. H., Leiserson & Rivest, R. L., Stein, C algoritmos: teoria e prática, 
Terceira Edição, Editora Campus, 2012.
Ziviani, N. Projeto de Algoritmos: com implementações em Pascal e C. Terceira Edição, 
Cengage Lenarning, 2010.
Proceedings of the XII SIBGRAPI (October 1999) 101-104
Proceedings of the XII SIBGRAPI (October 1999)