Estrutura de dados - Ordenação e Busca em Vetor

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

*
*
Pesquisa e Ordenação de Vetor
*
*
Ordenação de Vetor
*
*
Ordenação
Rearranjo de um conjunto de dados de acordo com um critério específico (ordem).
Objetivo: facilitar a localização dos membros de um conjunto de dados
Ordenação de vetores: in loco
Métodos:
 Diretos
Sofisticados
Categorias do Métodos Diretos:
Por Troca (Permutação)
Por Seleção
Por Inserção
*
*
Ordenação por Troca
Fácil de entender e programar
Uma das menos eficientes
Idéia: 
percorrer a lista seqüencialmente várias vezes, comparando cada elemento com o seu sucessor e trocando os dois se não estiverem na ordem correta
	 coloca o maior na última posição, depois o 2o maior na penúltima... até o menor ficar na primeira
Algoritmos:
Bubble Sort
Shaker Sort
*
*
Bubble Sort (1)
*
*
Bubble Sort (1)
*
*
Bubble Sort (1)
*
*
Bubble Sort (1)
*
*
Bubble Sort (1)
void bubblesort1(int *v, int n)
{
	int aux, i, j;
	for (i=0; i<n-1; i++)
		for (j=0; j<n-1-i; j++)
		 if (v[j] > v[j+1]) {
			aux=v[j];
			v[j]=v[j+1];
			v[j+1]=aux;
		 }
}
/* controla o número de passagens */
/* controla cada passagem */
/* elementos fora de ordem trocar */
/* troca de elementos */
*
*
Bubble Sort
Aprimoramento do Bubble Sort 
Quando nenhuma troca for efetuada ao percorrer toda a lista 
	Lista está classificada: o algoritmo pode ser encerrado
*
*
Bubble Sort (2)
*
*
Bubble Sort (2)
*
*
Não ocorreram trocas 
Bubble Sort (2)
*
*
Bubble Sort (2)
Como fazer?
*
*
Bubble Sort (2)
void bubblesort2(v, n)
int *v, n;
{
	int aux, i, j, trocou=1;
	for (i=0; i<n-1 && trocou; i++) {
		trocou=0; /*inicialmente nenhuma troca foi feita */
		for (j=0; j<n-1-i; j++)
		 if (v[j] > v[j+1]) {
			trocou=1; /* houve troca */
			aux=v[j];
			v[j]=v[j+1];
			v[j+1]=aux;
		 }
	}
}
*
*
Ordenação por Seleção
Um dos algoritmos de sort mais simples: 
ache primeiro o menor elemento da lista e troque sua posição com o primeiro elemento 
ache o segundo menor elemento e troque sua posição com o segundo elemento
continue até que toda lista esteja ordenada
para cada i de 0 a n-2, troca o menor elemento da sub-lista que vai de i a N-1 com a[i]
*
*
Seleção Direta 
*
*
Seleção Direta (1)
void selectsort (int *v, int n) { 	
	int i, j, aux;
 	for (i=0; i< n-1; i++)
		for (j=i+1; j< n; j++)
		 if (v[j]<v[i]) {	/* troca */
 		aux = v[i];
 		v[i]=v[j];
 		v[j] = aux; 
 		 } 
}
3 trocas a cada vez que entra no if 
*
*
Seleção Direta
Três trocas a cada vez que entra no if
Solução:
Guardar o menor em outra variável e só fazer 2 trocas a cada rodada
*
*
Seleção Direta (2)
void selectsort2 (int *v, int n) { 	
	int i, j, me, ind;
 	for (i=0; i< n-1; i++) {
		me=v[i]; ind=i;
		for (j=i+1; j< n; j++)
		 if (v[j]<me) {
			me = v[j];
 		ind=j;
		 } 
 		v[ind] = v[i]; 
		v[i]=me;
	}
}
armazena em me o menor número do segmento v[i] a v[n-1]
troca o menor do segmento(me) com a primeira posição do segmento
*
*
Seleção Direta – Guardar Menor
*
*
Seleção Direta – Guardar Menor
*
*
Seleção Direta – Guardar Menor
*
*
Ordenação por Inserção
Ordena o conjunto inserindo elementos no segmento já ordenado do conjunto
Os elementos são conceitualmente divididos em um segmento de destino e um segmento fonte
A cada passo, iniciando-se pelo segundo, cada elemento do segmento fonte é transferindo para o segmento de destino na posição que mantenha a ordenação do segmento de destino
Método muito usado por jogadores de cartas
*
*
Inserção Direta
void insertsort (int *v, int n){
	int i,k,y;
	
	for (k=1; k<n; k++) {
	
		y=v[k];
	
		for (i=k-1; i>=0 && y<v[i]; i--)
			v[i+1]=v[i];
		
		v[i+1]=y;
	}
}
Inicialmente v[0] é o segmento ordenado; após cada rodada, o segmento de v[0] até v[k] estarão ordenados
inserção de v[k] no segmento ordenado
guarda em y o valor a ser inserido em ordem no segmento
desloca os elementos do segmento que são maiores do que y uma posição para baixo
insere y na posição correta, mantendo a ordem
*
*
Shell Sort
Refinamento da Inserção Direta
Conhecido também por Ordenação por Incrementos Decrescentes
Criado por D. L. Shell (1959)
Ordena segmentos separados do conjunto original
Segmentos contêm todo k-ésimo elemento do conjunto original (k incremento)
Todos os elementos que estiverem separados por intervalos de k posições serão agrupados e ordenados
*
*
Shell Sort
Depois que os k primeiros segmentos estiverem ordenados (geralmente por inserção simples), será escolhido um novo valor de k (menor do que o inicial) e o conjunto é novamente particionado em novos segmentos
Cada segmento é novamente ordenado e o processo se repete até que k chegue a 1, de modo que o segmento corresponda ao conjunto todo
Uma seqüência decrescente de incrementos é definida no início do processo, sendo que o último valor deve ser o 1
*
*
Shell Sort
Exemplo:
Considerando que k é 4:
segmento 1  v[0] v[4] v[8] ...
segmento 2  v[1] v[5] v[9] ...
segmento 3  v[2] v[6] v[10] ...
segmento 4  v[3] v[7] v[11] ...
o i-ésimo elemento do j-ésimo segmento é 
		v[(i-1)*k + j-1]
*
*
Shell Sort
Exemplo
Conjunto original: 25 57 48 37 12 92 86 33
Primeira rodada (k=4)
segmento 1  v[0] v[4]
segmento 2  v[1] v[5] 
segmento 3  v[2] v[6]
segmento 4  v[3] v[7]
Segunda rodada (k=2)
segmento 1  v[0] v[2] v[4] v[6]
segmento 2  v[1] v[3] v[5] v[7]
Terceira rodada (k=2)
segmento 1  v[0] v[1] v[2] v[3] v[4] v[5] v[6] v[7]
*
*
Shell Sort
37
12
92
86
33
1a rodada (k=4)
2a rodada (k=2)
25
57
48
37
12
92
86
33
25
57
48
33
25
92
86
37
12
57
48
37
48
57
86
92
12
25
44
3a rodada (k=1)
*
*
Shell Sort
Determinação dos incrementos:
Qualquer seqüência de incrementos é válida, contanto que o último seja 1
Resultados melhores com incrementos que não sejam potência de 2
Incrementos devem ser primos entre si, para garantir que as sucessivas rodadas combinem os segmentos de forma que ao final ele já esteja praticamente ordenado, evitando combinar cadeias entre as quais anteriormente não havia nenhuma interação
Sugestões de Knuth:
1, 4, 13, 40, 121, ... 
1, 3, 7, 15, 31, ...
*
*
Shell Sort
Algoritmo?
*
*
Shell Sort
void shellsort (int *v, int n, int *vinc, int ninc) {
	/* vinc: vetor de incrementos; ninc: no de incrementos */
	int i, j, k, inc, y; 
	for (i=0; i < ninc; i++) {
		inc=vinc[i]; /* tamanho do incremento da rodada*/
		for (j=inc; j<n; j++) {
		/* inserir v[j] na posição correta dentro de seu segmento*/
			y=v[j]; 
			for (k=j-inc; k>=0 && y<v[k]; k-=inc)
				v[k+inc]=v[k];
			v[k+inc]=y;
		}
	}
}
*
*
Análise dos Algoritmos
1) Bubble Sort (1)
Rodadas: n-1
Comparações por rodada: n-1
Trocas por rodada (no máximo): n-1
(depende da seqüência inicial dos dados, mas não excede o o no de comparações)
Total de comparações: 		(n-1)*(n-1)
							n2 - 2n + 1
Total de trocas (no máximo): (n-1)*(n-1)
							n2 - 2n + 1
*
*
Análise dos Algoritmos
1) Bubble Sort (1)
Desvantagens:
O(n2)
Lento
Vantagens: 
quando o vetor já está ordenado, é O(n)
pouco espaço adicional
*
*
Análise dos Algoritmos
2) Bubble Sort (2)
Comparações na rodada i: n-i
Total de comparações para k rodadas:
		(n-1) + (n-2) + ... + (n-k) = (2kn - k2 – k)/2
Desvantagens:
a fórmula geral continua sendo O(n2)
sobrecarga para tesar, inicializar e alterar a variável trocou
Vantagens: 
fator constante é menor do que o Bubbe Sort
Para um número médio de rodadas: O(n)
*
*
Análise dos Algoritmos
4) Seleção Direta
Total de comparações: 	
	(n-1)+(n-2)+...+2+1 = n*(n-1)/2 = (n2-n)/2
Total de trocas: sempre (n-1)
Vantagens: 
pouco espaço adicional
mais veloz do que Bubble Sort
Desvantagens:
no de comparações: O(n2)
quando está ordenado, continua O(n2)
*
*
Análise dos Algoritmos
5) Inserção Direta
Total de comparações: 	
	(n-1)+(n-2)+...+2+1 = n*(n-1)/2 = (n2-n)/2
Mínimo de comparações: (n-1)
Vantagens: 
geralmente melhor que Bubble Sort
quanto mais próximo da ordem classificada, mais eficiente
Desvantagens:
no de comparações: O(n2)
*
*
Análise dos Algoritmos
Inserção Direta x Seleção Direta
Seleção exige menos atribuições do que Inserção, mas requer mais comparações:
Seleção recomendada para poucos dados com registros grandes
Inserção recomendada para o inverso
Ambos mais eficientes do que Bubble Sort
Inserção melhor para dados quase ordenados ou aleatórios
Seleção melhor para dados em ordem invertida
*
*
Análise dos Algoritmos
6) Shell Sort
Total de comparações: 	
O(n log(n)) para uma seqüência apropriada de incrementos
para outras seqüências: O(n3/2)
Melhor do que as anteriores
Recomendada para conjuntos de tamanho médio: várias centenas de elementos
*
*
Análise dos Algoritmos
7) Inserção Binária
8) Quick Sort
9) Merge Sort (Fusão Direta)
*
*
Análise dos Algoritmos
*
*
Busca em Vetor
*
*
Busca Seqüencial
Busca em uma lista seqüencial 
não ordenada 
ordenada pelos seus valores
Problema: buscar pelo valor B em um conjunto de K elementos. A função retorna a posição de B na lista seqüencial, ou retorna -1 caso não o encontre.
*
*
 
int BuscaSeq (int *V, int B, int K){
	int p;
	for (p=0; p<K; p++)
		if (v[p]==B)
			return p;
	return -1;
}
Busca Seqüencial
*
*
Busca Seqüencial
Avaliação da Busca Seqüencial
Tamanho do vetor: n
Se o registro for 
o primeiro: uma comparação
o último: n comparações
na média: (n+1)/2
Comparações: O(n)
*
*
Busca Seqüencial em uma Lista Ordenada
Problema: buscar um valor NÃO existente em uma lista seqüencial ordenada com K elementos. 
 A lista precisa ser percorrida até o final
Solução: o tempo de busca neste caso pode ser reduzido significantemente devido à ordenação dos elementos da lista, mesmo para um conjunto de elementos grande.
*
*
Busca Seqüencial em uma Lista Ordenada
int BuscaSeqOrd (int *V, int B, int K){
	int p=0;
	while (p<K && B<V[p])
		p++;
	if (p<K) /* achou */
		return p;
	else
		return -1;
}
*
*
Busca Seqüencial em uma Lista Ordenada
Avaliação da Busca em Lista Ordenada quando o elemento não existe
Tamanho do vetor: n
Lista não ordenada: n comparações
Lista ordenada: n/2 comparações em média
*
*
Busca Binária
Busca baseada em "dividir para conquistar"
supõe que o conjunto está ordenado
divide um conjunto de elementos em duas partes
determina a qual dessas duas partes o valor pertence e se concentra nessa parte
usa índices do vetor para delimitar a parte sendo trabalhada
Algoritmo:
compare com o valor do elemento do meio 
se o valor comparado for menor, o elemento está na parte esquerda da lista; se maior, na parte direita
aplique o método recursivamente
*
*
Busca Binária
busca_binaria (int *V, int K, int B) { 	
	int ESQ, DIR, meio;
	 ESQ =0; DIR =K-1;
 	while (ESQ <= DIR) { 
	 	meio= (ESQ + DIR)/ 2;
		if (B== V[meio]) 
		 return meio;
		else
	 	 if (B < V[meio]) 
			 DIR = meio -1;
 	 else 
			 ESQ = meio +1;
 	};
 	return -1; 
}
*
*
Busca Binária
int BuscaBinRec (int* V, int B, int ESQ, int DIR){
	int meio;
	if (ESQ > DIR)
 		return -1;
 
	meio = (ESQ + DIR) / 2;
 if (B == V[meio])
 return meio;
 if (B < V[meio])
 return BuscaBinRec (V, B, ESQ, meio-1);
 else
 return BuscaBinRec (V, B, meio+1, DIR);
}
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
297
*
301
*
305
*
306
*
308
*
308