Algoritmos de Ordenação

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
IF672 - Algoritmos e Estruturas de Dados CIn - UFPE
if672.ufpe@gmail.com
*
*
Ordenação
Ordenar é dispor os elementos em ordem ascendente ou descendente.
Dados n números, arranjá-los em ordem crescente.
Sortings:
 Heapsort
 	Quicksort
 	Mergesort
*
*
Heapsort
Ordenação de um conjunto de elementos com um heap.
Primeiro passo: construção do heap.
Selecionamos e posicionamos o maior elemento do conjunto, trocando o primeiro com o último elemento.
Decrementamos o tamanho do heap.
Rearranjamos o heap.
Continua com as sucessivas trocas do primeiro com o último elemento e rearranjos do heap.
*
*
Heapsort
Após tudo isso, o array é visto como contendo um heap mais a parte da solução.
Então, o uso da estrutura heap permite que:
O elemento máximo do conjunto seja determinado e corretamente posicionado no vetor em tempo constante, trocando o primeiro elemento do heap com o último.
Número de trocas de elementos proporcional à altura da árvore.
*
*
Heapsort
*
*
Heapsort
*
*
Heapsort
*
*
Heapsort
*
*
Heapsort
*
*
Heapsort
*
*
Heapsort
Chamada:
Implementação:
heapsort(array, array.length);
void heapsort (int array[], int n) {
	constroiHeap (array, n);
	int tamanhoDoHeap = n;
	for(int i = n-1; i>0; i--) {
 troca (array[0], array[i]);
 --tamanhoDoHeap;
	 heapfy (array,tamanhoDoHeap,0);
 }
}
*
*
Quicksort
Ordenação simples de implementar em linguagens com recursão.
Método “dividir para conquistar”.
Particiona o arquivo em duas partes, ordenando as partes independentes.
*
*
Quicksort
Dividir para Conquistar
Dividir:
	Particione o array em dois subarrays ao redor de um pivô x de forma que elementos no subarray inferior ≤x≤ elmentos no subarray superior.
Obs: a posição do elementos iguais à chave deve ser especificada, dependendo do objetivo da implementação.
*
*
Quicksort
Escolha um elemento (pivô) e coloque-o no início da lista.
Varra o array a partir da esquerda até encontrar um elemento que seja maior que o pivô e pela direita até encontrar um elemento menor que o pivô.
Os dois devem ser trocados de lugar.
Quando os ponteiros se cruzam, troque o pivô com o elemento mais a esquerda do array.
*
*
Quicksort: Exemplo Particiona
*
*
Quicksort: Exemplo Particiona
*
*
Quicksort: Exemplo Particiona
*
*
Quicksort: Exemplo Particiona
*
*
Quicksort: Exemplo Particiona
*
*
Quicksort: Exemplo Particiona
*
*
Quicksort
Função Particiona
Implementação:
int particiona (int array[], int i, int f) {
	int a = i+1; int b = f; int pivo = array[i];
	while(a <= b) {
		while(a<=f && array[a]<pivo) a++;
		while(array[b]>pivo) b--;
		if(a < b) troca (array[a], array[b]);
	}
	troca(array[b], array[i]); return b;
}
*
*
Quicksort
Chamada:
Implementação:
void quicksort (int array[], int i, int f) { if (i < f) {
	int p = particiona (array, i, f);
 quicksort (array, i, p-1);
	quicksort (array, p+1, f);
 }
}
quicksort(array, 0, array.length-1);
*
*
Quicksort
Considerações finais
 Quicksort é um ótimo algoritmo de ordenação de propósito geral.
 Quicksort é normalmente mais rápido que o Mergesort, mas no pior caso tem custo O(n²).
*
*
Mergesort
Algoritmo particular de ordenação.
Método “dividir para conquistar”.
Divide o array no meio.
Ordena cada metade com Mergesort novamente.
Junta (merge) as partes já ordenadas.
Problema: necessita de um espaço igual ao dobro do tamanho da lista a ser ordenada.
*
*
Mergesort
82
36
70
72
25
11
44
10
*
*
Mergesort
82
36
70
72
25
11
44
10
*
*
Mergesort
Chamada:
Implementação:
void mergesort(int array[], int i, int f) {
 if (i < f) {
	int mid = (i+f)/2;
 mergesort (array, i, mid);
 mergesort (array, mid+1, f);
	intercala (array, i, mid, f);
 }
mergesort(array, 0, array.length-1);
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Função Merge/Intercala
Divisão da direita
Divisão da esquerda
a
b
*
*
Mergesort
Implementação Merge/Intercala
void intercala (int array[], int left, int mid, int right) { 	int i = left;
	int j = mid + 1;
	int k = left - 1;
	while (i <= mid && j <= right) {
		k++;
		if (array[i] <= array[j]) {
			temp[k] = array[i];
			i++;
		} else {
			temp[k] = array[j];
			j++;
		}
	}
//...}
*
*
Mergesort
Implementação Merge/Intercala
void intercala (int array[], int left, int mid, int right) { 	while (i <= mid) {
		temp[k] = array[i]; i++; k++;
	}
	while (j <= right) {
		temp[k] = array[j]; j++; k++;
	}
}
*
*
Relembrando:Busca Binária
Busca eficiente feita em um array ordenado.
A busca é iniciada pelo elemento central. Se o elemento procurado for menor, procura-se novamente na primeira metade, caso contrário, na segunda.
*
*
Relembrando:Busca Binária
Busca bem sucedida: número 8
*
*
Relembrando:Busca Binária
Busca mal sucedida: número 28
*
*
Relembrando:Busca Binária
Chamada:
Implementação:
int bs(int array[], int i, int f, int x) { int mid = (i+f)/2;
 if (x == array[mid]) // caso base 1 (encontrado) return mid; else if (i >= f) // caso base 2 (não existe) return –1;
 else if (x < array[mid]) // caso indutivo return bs(array, i, mid-1, x) else return bs(array, mid+1, f, x) }
bs(array, 0, array.length-1, x);
*
*
IF672 - Algoritmos e Estruturas de Dados CIn - UFPE
if672.ufpe@gmail.com
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*