Métodos de Ordenação - Métodos Simples

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

Fundamentos da Compuação Inteligente
*
Métodos de Ordenação
EDII 2010.1
Fundamentos da Compuação Inteligente
Fundamentos da Compuação Inteligente
*
*
Métodos de Ordenação
Ordenação corresponde ao processo de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente
Tem como objetivo facilitar a recuperação dos itens do conjunto
Recuperação de nomes em um lista telefônica
Atividade relevante e fundamental em processamento de dados, sobretudo aqueles armazenados em arquivos
Fundamentos da Compuação Inteligente
*
*
Ordenação
Num processo de ordenação escolhe-se uma determinada chave (campo) comum da massa de dados sobre o qual o processo acontecerá
Registros são usados para representar os elementos a serem ordenados
	 struct TipoItem { 		 TipoChave chave;     	 //outras declarações desejadas...     	 };
Os demais campos dos registros, em geral não influenciam no processo de ordenação
Fundamentos da Compuação Inteligente
*
*
Processo de Ordenação
Sejam os itens a1, a2, . . . , an.
Ordenar consiste em permutar estes itens em uma ordem:
ak1 , ak2 , . . . , akn
tal que, dada uma função de ordenação f , tem se a seguinte relação:
f (ak1 ) ≤ f (ak2 ) ≤ . . . ≤ f (akn )
Função de ordenação é definida sobre o campo chave.
Qualquer tipo sobre o qual exista uma regra de ordenação bem definida pode ser utilizado omo chave
Fundamentos da Compuação Inteligente
*
*
Classificação – 
Quanto à Estabilidade
Métodos Instáveis: a ordem relativa dos itens com chaves iguais é alterada durante o processo de ordenação
Métodos Estáveis: se a ordem relativa dos itens com chaves iguais mantém-se inalterada durante o processo
Alguns dos métodos de ordenação mais eficientes não são estáveis
Fundamentos da Compuação Inteligente
*
*
Estabilidade - Exemplo
Estável:
Instável:
Fundamentos da Compuação Inteligente
*
*
Classificação: 
Quanto ao conjunto de registros
Ordenação Interna: o conjunto de registros cabe todo em na memória principal 
Ordenação Externa: o conjunto de registros não cabe completamente em memória principal, e deve ser armazenado em memória auxiliar.
Alguns autores utilizam ordenação de vetores (ordenação interna) e ordenação de registros (ordenação externa)
Fundamentos da Compuação Inteligente
*
Ordenação Interna
Fundamentos da Compuação Inteligente
Fundamentos da Compuação Inteligente
*
*
Ordenação Interna
Medidas de complexidade levam em conta:
O número de comparação entre as chaves
O número de trocas entre os itens
São classificados em dois tipos:
Métodos Simples: mais recomendados para conjuntos pequenos de dados. Usam mais comparações, mas produzem códigos menores e mais simples;
Métodos Eficientes ou Sofisticados: adequados para conjuntos maiores de dados. Usam menos comparações, porém produzem códigos mais complexos e com muitos detalhes.
Fundamentos da Compuação Inteligente
*
*
Alguns Algoritmos de 
Ordenação Interna
Ordenação por Seleção (Selection Sort)
Ordenação por Inserção (Insertion Sort)
Ordenação por Seleção e Troca (Bubble Sort)
Ordenação por Inserção através de incrementos decrescentes (ShellSort)
Ordenação por Particionamento (QuickSort)
Ordenação de Árvores (HeapSort)
Fundamentos da Compuação Inteligente
*
Ordenação Interna
Métodos Simples
Fundamentos da Compuação Inteligente
Fundamentos da Compuação Inteligente
*
Selection Sort
Ordenação por Seleção
Fundamentos da Compuação Inteligente
Fundamentos da Compuação Inteligente
*
*
Ordenação por Seleção 
(Selection Sort)
Um dos algoritmos mais simples
Mais recomendado para conjuntos pequenos
Procedimento:
Selecione o menor item do conjunto e troque-o com o item que está na posição i
Repita essas operações com os demais itens até que reste apenas um elemento
Fundamentos da Compuação Inteligente
*
*
Ordenação por Seleção 
(Selection Sort)
Chaves Iniciais:
i=1:
i=2:
i=3:
i=4:
i=5:
Fundamentos da Compuação Inteligente
*
*
Ordenação por Seleção
void SelectionSort(int vet[10])
{
 int i, j, min, aux;
	for(i=0;i<10;i++)
	{
		min = i; //Posição a ser ordenada
		for(j=i+1;j<10;j++)
		{
			if (vet[j] < vet[min])
			{
				min = j; //Posição a ser trocada
			}
		}
		aux = vet[min];
		vet[min] = vet[i];
		vet[i] = aux;
	}
}
		
Troca
Fundamentos da Compuação Inteligente
*
*
Ordenação por Seleção 
(Selection Sort)
Desvantagens
O fato de o conjunto já estar ordenado não ajuda em nada (o número de comparações continua o mesmo)
O algoritmo não é estável, isto é, os registros com chaves iguais nem sempre irão manter a mesma posição relativa de antes do início da ordenação
Fundamentos da Compuação Inteligente
*
Insertion Sort
Ordenação por Inserção
Fundamentos da Compuação Inteligente
Fundamentos da Compuação Inteligente
*
*
Ordenação por Inserção 
(Insertion Sort)
Também um algoritmo simples
Procedimento
Os elementos são divididos em uma seqüência de destino a1, ..., ai-1 e em uma seqüência fonte ai, ..., an.
Em cada passo, a partir de i =2, o i-ésimo item da seqüência fonte é retirado e transferido para a seqüência destino sendo inserido na posição adequada
Fundamentos da Compuação Inteligente
*
*
Ordenação por Inserção (Insertion Sort)
A
O
R
D
E
N
6
2
3
4
5
1
Chaves Iniciais
O
R
A
O
R
D
E
N
i = 2
Fundamentos da Compuação Inteligente
*
*
Ordenação por Inserção (Insertion Sort)
A inserção do item em uma posição adequada na seqüência de destino é realizada com a movimentação das chaves maiores para a direita e então é feita a inserção do item na posição vazia
Vantagens:
O número mínimo de comparações e movimentos ocorre quando os itens já estão originalmente ordenados
O número máximo ocorre quando os itens estão originalmente em ordem reversa, o que indica um comportamento natural para o algoritmo
Fundamentos da Compuação Inteligente
*
*
Ordenação por Inserção
void InsertSort(int v[10])
{
 int i, j, key;
 for(j = 0; j < 10; j++)
 {
 key = v[j];
 for(i = j - 1; (i >= 0) && (v[i] > key); i--) // Valores menores movidos para cima
 {
 v[i+1] = v[i];
 }
 v[i+1] = key; //Pondo a chave em sua localização correta
 }
}
Fundamentos da Compuação Inteligente
*
*
Ordenação por Seleção e Troca (Bubblesort)
Um dos algoritmos mais simples
Princípio:
As chaves Item[1].Chave e Item[2].Chave são comparadas e trocadas se estiverem fora de ordem;
Repete-se o processo de comparação e troca com Item[2] e Item[3], Item[3] e Item[4], ...
Por que Bolha?
Se o vetor a ser ordenado for colocado na vertical, com Item[n] em cima e Item[1] embaixo, durante cada passo o menor elemento “sobe” até encontrar um elemento maior ainda, como se uma bolha subisse dentro de um tubo de acordo com sua densidade
Fundamentos da Compuação Inteligente
*
*
Ordenação pelo Método da Bolha
i = 1
i = 4
i = 6
i = 7
Chaves Iniciais
i = 3
i = 2
i = 5
i = 8
Fundamentos da Compuação Inteligente
*
*
Implementação: Ordenação pelo Método da Bolha
void BubbleSort(int L[10])
{
	int i,j, aux;
	for(i=0;i<10;i++)
	{
	 for(j=i+1;j<10;j++)
	 {
	 if(L[i] > L[j])
 	 {
 aux=L[i];
		 L[i]=L[j];
		 L[j]=aux;
		 }
	 }
 }
}
Fundamentos da Compuação Inteligente
*
*
Ordenação pelo Método da Bolha
Note que no exemplo, as três últimas iterações não afetam a ordem do vetor; assim o algoritmo pode ser melhorado!
Técnica óbvia: manter uma indicação para saber se houve ou não troca na última iteração: se não houve, o vetor já está ordenado
Fundamentos da Compuação Inteligente
*
*
Observações
Método extremamente lento: só faz comparações entre posições adjacentes
É o método mais ineficiente entre os simples
Melhor caso: vetor já ordenado
Pior caso: vetor de entrada em ordem reversa
Cada passo aproveita muito pouco do que foi “descoberto” em relação à ordem das chaves no passo anterior (exibe informações redundantes)