Estruturas de Dados - T.332

Capítulo 9
Ordenação

9.1 Introdução
9.2 Quicksort   
9.1 Introdução à Ordenação
•	A noção de um conjunto de dados ordenados é de considerável importância na nossa vida quotidiana e por conseguinte também em computação
•	Exemplos:
•	Listas telefônicas,
•	Listas de clientes de uma empresa,
•	Listas de peças em um catálogo,
•	etc.
•	Algoritmos eficientes para ordenar grandes quantidades de dados são de extrema importância.
•	Já vimos:
•	Algoritmos simples e ineficientes, árvores
9.1.1 Conceitos básicos em Ordenação
•	Arquivo
•	Um arquivo r de tamanho n é uma seqüência de n ítens r[0], r[1], r[n-1].
•	Cada ítem em um arquivo é chamado registro.
•	Um arquivo é classificado por chave
•	se para cada registro r[i] existe um  uma parte de r[i], k[i] chamada chave de classificação.
•	se i<j implicar que k[i] precede k[j] de acordo com algum critério qualquer predefinido
•	Exemplo:
•	Em um catálogo telefônico o arquivo é o próprio catálogo,
•	Um registro é uma entrada com nome, nº e endereço
•	O nome é a chave.
9.1.1 Conceitos básicos em Ordenação
•	Localização de Execução:
•	Ordenação interna é aquela realizada na memória principal do computador.
•	Ordenação externa é aquela, onde os registros podem estar em uma memória auxiliar (arquivo em disco).
•	Estabilidade:
•	Uma técnica de ordenação é chamada estável se, para todos os registros i e j, dado que k[i] é igual a k[j]; 

se r[i] precede r[j] no arquivo original, 

então r[i] precederá r[j] no arquivo classificado.
Uma ordenação pode ocorrer sobre os próprios registros ou sobre uma tabela auxiliar de ponteiros.
•	Classificação direta é uma ordenação onde um arquivo é ordenado diretamente, sendo os registros movidos de uma posição física para outra.
b) Classificação por endereços é uma ordenação onde somente uma tabela de ponteiros é ordenada, os registros em si não são tocados.
9.1.2 Critérios para Selecionar uma Ordenação
•	Eficiência no Tempo
•	Se um arquivo é pequeno (ex.: 20 registros) técnicas sofisticadas podem ser piores
•	Algoritmos complexos, módulos grandes
•	Nº de vezes que a ordenação será executada
•	Se vamos classificar um conjunto de dados, mesmo grande, só uma vez, pode ser mais interessante implementar um algoritmo simples.
•	Um programa que executa ordenações repetidamente deve ser eficiente.
•	Esforço de programação não deve ser uma desculpa para a utilização de um algoritmo inadequado. Um sistema ineficiente não vai vender.
•	Eficiência de Espaço
•	A técnica que escolhi é compatível com as características de hardware do ambiente para o qual a estou destinando?
9.1.2.1 Aspectos da Eficiência de Tempo
•	O critério básico para a determinação da eficiência de tempo de um algoritmo não é a somente sua complexidade assintótica
•	Operações críticas:
•	Operação crítica é uma operação básica no processo de ordenação. Ex.: a comparação de duas chaves ou o deslocamento de um registro de uma posição de memória para outra.
•	Um algoritmo que executa todas as operações críticas na memória será geralmente mais rápido, do que outro que executa algumas em memória secundária (disco).
9.2 Quicksort
•	A ordenação por troca de partição ou quicksort é provavelmente o algoritmo de ordenação mais utilizado.
•	Divide and Conquer
•	Complexidade média O(n log n)
•	Vantagens:
•	Simples de implementar
•	Bastante bem compreendido.
•	Extensas análises matemáticas de seu comportamento já foram feitas
•	Desvantagens:
•	Complexidade pode ser O(n2) no pior caso, em que o arquivo está ordenado ou ordenado em ordem inversa.
•	Diferentes versões “melhoradas” existem.
Algoritmo Básico
•	Quicksort trabalha particionando um arquivo em duas partes e então as ordenando separadamente.
•	Pode ser definido recursivamente:
quicksort (tipoInfo : a[], inteiro : esq, dir)
	inteiro i;
	início
		se dir > esq então
			i <- particione(a, esq, dir);
			quicksort(a, esq, i-1);
			quicksort(a, i+1, dir);
		fim se
	fim
•	Os parâmetros dir e esq delimitam os subarquivos dentro do arquivo original, dentro dos quais a ordenação ocorre. 
•	A chamada inicial pode ser feita com quicksort(a, 1, N);
•	O ponto crucial é o algoritmo de partição.
Particionamento em Quicksort
•	O procedimento de particionamento deve rearranjar o arquivo de maneira que as seguintes condições valham:
(i). 	o elemento a[i] está em seu lugar final no arquivo para um i dado,
(ii). 	nenhum dos elementos em a[esq],…,a[i-1] são maiores do que a[i],
(iii).	 nenhum dos elementos em a[i+1],…,a[dir] são menores do que a[i].
Exemplo
•	Ordenação do vetor inicial 25 57 48 37 12 92 86 33.
•	Se o primeiro elemento (25) for colocado na sua posição “correta”, teremos: 12 25 57 48 37 92 86 33. 
Neste ponto:
•	todos os elementos abaixo de 25 serão menores e
•	todos os elementos acima de 25 serão maiores que 25.
•	Como 25 está na sua posição final, o problema foi decomposto na ordenação dos subvetores: (12) e (57 48 37 92 86 33).
•	O subvetor (12) já está classificado.
•	Agora o vetor pode ser visualizado: 12 25 (57 48 37 92 86 33).
•	Repetir o processo para a[2]…a[7] resulta em:
 12 25 (48 37 33) 57 (92 86)

•	Se continuarmos particionando 
12 25 (48 37 33) 57 (92 86),
teremos:
12 25 (37 33) 48 57 (92 86)
12 25 (33) 37 48 57 (92 86)
12 25 33 37 48 57 (92 86)
12 25 33 37 48 57 (86) 92 
12 25 33 37 48 57 86 92

Visão da Recursividade do Quicksort como Árvore:
Método para o Particionamento
•	Considere x=a[limInf] como o elemento cuja posição final é a procurada.
•	Usar sempre o primeiro é só um artifício p/facilitar a implementação.
•	Dois ponteiros alto e baixo são incializados como os limites máximo e mínimo do subvetor que vamos analisar. 
•	Em qualquer ponto da execução, todo elemento acima de alto é maior do que x e todo elemento abaixo de baixo é menor do que x.
•	Os dois ponteiros alto e baixo são movidos um em direção ao outro da seguinte forma:
1. Incremente baixo em uma posição até que a[baixo] > x.
2. Decremente alto em uma posição até que a[alto] <= x.
3. Se a alto > baixo , troque a[baixo] por a[alto].
•	O processo é repetido até que a condição descrita em 3. falhe (quando 
alto <= baixo ). Neste ponto a[alto]será trocado por a[limInf],cuja posição final era procurada, e alto é retornado em i.
Algoritmo de Particionamento
inteiro partição(tipoInfo : a[], inteiro : limInf, limSup)
	variáveis
		tipoInfo : x, temp; inteiro : baixo, alto;
	início
		x <- a[limInf]; alto <- limSup; baixo <- limInf;
		enquanto (baixo < alto) faça
			enquanto (a[baixo] <= x E baixo < limSup) faça
				incremente baixo;		/* Sobe no arquivo */
			enquanto (a[alto] > x) faça
				decremente alto;		/* Desce no arquivo */ 
			se (baixo < alto) então	/* Troca */
				temp <- a[baixo];
				a[baixo] <- a[alto];
				a[alto] <- temp;
			fim se
		fim enquanto
		a[limInf] <- a[alto];
		a[alto] <- x;
		retorne alto;
	fim
Comentários sobre o Quicksort
Para evitar o pior caso e casos “ruins” onde elementos estão em grupos ordenados pode-se utilizar uma estratégia probabilística:
•	Selecione, ao invés do primeiro elemento para ser a, um elemento aleatório. Critérios:
•	Seleção totalmente randômica: selecione qualquer elemento do subvetor usando um gerador de números aleatórios.
•	Desvantagem: tempo de processamento extra para o gerador.
•	Seleção pseudorandômica: selecione um elemento do subvetor com base em um cálculo qualquer baseado em valores que você tem à mão (alto, baixo, chave do primeiro)
•	Seleção média: pegue ao invés do elemento inicial, sempre o do meio.
Todos estes métodos melhoram a performance média.
9.3 HeapSort
•	O HeapSort, também chamado de Classificação por Monte ou Ordenação com Árvore-Heap é um método de ordenação que utiliza uma árvore-heap como estrutura intermediária para efetuar a ordenação.
•	Vantagens:
•	O pior caso é O(n log n). Os outros são um pouco, porém muito  pouco, melhores.
•	HeapSort é mais estável que Quicksort.
•	Desvantagens:
•	Construir a árvore-heap pode consumir muita memória.
•	Em suma: 
•	Para dados “bem bagunçados” o Quicksort é mais vantajoso por ser mais “econômico”.
•	Para dados “imprevisíveis”, pode ser mais vantajoso por ser 
previsível em termos de tempo de execução.
9.3.1 Preâmbulo: Árvore Heap
•	Def.: Uma árvore-heap, também chamada de monte é uma árvore binária por níveis, onde o nodo pai de uma subárvore sempre é maior que todos os seus descendentes.
•	Exemplo:
9.3.2 Método em HeapSort
É um método em três estágios:
•	Primeiramente criamos uma visão sobre o arquivo como árvore binária por níveis.
•	Iterativamente:
•	Reestruturamos o arquivo para para que se transforme em um monte.
•	Na terceira etapa geramos a seqüência de saída retirando a raiz do monte e reestruturando o monte para que retorne a satisfazer a condição-heap.
Visão do arquivo x1,…xn por Níveis:
Árvore-Heap a partir do Arquivo 
(26 5 77 1 61 11 59 15 48 19)
Algoritmo HeapSort
heapsort( tipoInfo : a[], inteiro : n)
	variáveis
		inteiro 	:	i;
		tipoInfo	:	temp;
	início
		para I de (n div 2) até 1 passo -1 faça
			ajuste(a, I, n);	/* Converta a em um heap */
		fim para
		para I de (n-1) até 1 passo -1 faça
			temp <- a[I+1];
			a[I+1] <- a[1];	/* Supõe posição inicial = 1 */
			a[1] <- temp;
			ajuste(a,1,I);	/* Restabeleça o heap */
		fim para
	fim
Algoritmo do Ajuste
ajuste( tipoInfo : a[], inteiro : i, n)
	variáveis
		inteiro 	:	j;
		tipoInfo	:	aAux;
	início
		aAux <- a[1]		/* Supõe posição inicial = 1 */
		j <- 2*i;
		enquanto j <= n faça
			se j < n E a[j] < a[j+1] então
				incremente j;
			fim se
			se aAux >= a[j] então
				retorne
			fim se
			a[j div 2] <- a[j]; j <- 2*j;
		fim enquanto
		a[j div 2] <- aAux;
	fim
9.4 Exercícios
•	Execute o algoritmo de particionamento no papel para o exemplo de arquivo dado no exemplo de QuickSort.
•	Execute o algoritmo do HeapSort sobre o mesmo exemplo. Mostre o arquivo a cada iteração do ajuste.
•	Escolha e implemente em C++ um dos dois algoritmos dados.
•	A implementação deve ser capaz de ler  um arquivo contendo uma série de números reais, um por linha.
•	A implementação deverá ser capaz de escrever em um arquivo o tempo necessário para ordenar os dados, no mesmo formato pedido para a árvore. 
•	Diferença: serão fornecidos diversos arquivos. O tempo deverá ser escrito sempre no fim de um arquivo só.