• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Guest tsenart

Algoritmos de Pesquisa e Ordenação

2 mensagens neste tópico

Olá pessoal!

Vou postar uns Algoritmos de Pesquisa e Ordenação em C sendo que este é um tópico que ainda não vi no forum e penso ser importante.

Pesquisa

int PesquisaSequencial (int seq[], unsigned int inicio, unsigned int fim, int valor)
{
unsigned int IndActual;

for (IndActual = inicio; IndActual <= fim; IndActual++)
	if (seq[indActual] == valor)
		return IndActual;

return -1;
}


int PesquisaSequencialOrdenada (int seq[], unsigned int inicio, unsigned int fim, int valor)
{
unsigned int IndActual;

for (IndActual = inicio; IndActual <= fim; IndActual++)
	if (seq[indActual] >= valor)
		break;

if (IndActual != fim && seq[indActual] == valor)
	return IndActual;
else 
	return -1;
}


unsigned int PesquisaMaiorElemento (int seq[], unsigned int inicio, unsigned int fim)
{
unsigned int IndMaior = inicio, IndActual;

for (IndActual = inicio+1; IndActual <= fim; IndActual++)
	if (seq[indActual] > seq[indMaior])
		IndMaior = IndActual;

return IndMaior;
}


unsigned int PesquisaMenorElemento (int seq[], unsigned int inicio, unsigned int fim)
{
unsigned int IndMenor = inicio, IndActual;

for (IndActual = inicio+1; IndActual <= fim; IndActual++)
	if (seq[indActual] < seq[indMenor])
		IndMenor = IndActual;

return IndMenor;
}


int FirstFit (int seq[], unsigned int inicio, unsigned int fim, int valor)
{
unsigned int IndActual;

for (IndActual = inicio; IndActual <= fim; IndActual++)
	if (seq[indActual] <= valor)
		return IndActual;

return -1;
}


int BestFit (int seq[], unsigned int inicio, unsigned int fim, int valor)
{
unsigned int IndActual, IndMelhor;

IndMelhor = FirstFit (seq, inicio, fim, valor);
if (IndMelhor == -1) return -1;

for (IndActual = IndMelhor+1; IndActual <= fim; IndActual++)
	if (seq[indActual] > seq[indMelhor] && seq[indActual] <= valor)
		IndMelhor = IndActual;

return IndMelhor;
}


int WorstFit (int seq[], unsigned int inicio, unsigned int fim, int valor)
{
unsigned int IndActual, IndPior;

IndPior = FirstFit (seq, inicio, fim, valor)
if (IndPior == -1) return -1;

for (IndActual = IndPior+1; IndActual <= fim; IndActual++)
	if (seq[indActual] < seq[indPior])
		IndPior = IndActual;

return IndPior;
}


int PesquisaBinaria (int seq[], unsigned int inicio, unsigned int fim, int valor)
{
unsigned int Minimo = inicio, Maximo = fim, Medio;

while (Minimo <= Maximo)
{
	Medio = (Minimo + Maximo) /2;  //Calculo da posicao media

	if (seq[Medio] == valor)
		return Medio;          //Pesquisa com sucesso

	if (seq[Medio] > valor) Maximo = Medio-1;  //Actualizacao dos limites do intervalo de pesquisa
	else Minimo = Medio+1;
}

return -1;  //Pesquisa sem sucesso
}

Ordenação

void Troca (int *x, int *y)
{
int Temp;

Temp = *x;
*x = *y;
*y = Temp;
}


void OrdenacaoSequencial (int seq[], unsigned int n_elementos)
{
unsigned int IndI, IndJ;

for (IndI = 0; IndI < n_elementos-1; IndI++)
	for (IndJ = IndI+1; IndJ < n_elementos; IndJ++)
		if (seq[indI] > seq[indJ])
			Troca (&seq[indI], &seq[indJ]);
}


void BubbleSort (int seq[], unsigned int n_elementos)
{
unsigned int Ind, IndInicial, NTrocas;

IndInicial = 1; //Inicializar o limite superior de ordenacao

do
{
	NTrocas = 0; //Inicializar o contador de trocas
	for (Ind = n_elementos-1; Ind >= IndInicial; Ind--)
		if (seq[ind-1] > seq[ind])
		{
			Troca (&seq[ind], &seq[ind-1]); //Trocas os elementos
			NTrocas++; //Actualizar o numero de trocas efectuadas
		}
	IndActual++; //Actualizar o limite superior de ordenacao
} while (NTrocas && IndInicial < n_elementos);
}


void InsertionSort (int seq[], unsigned int n_elementos)
{
unsigned int IndI, IndD;
int Temp;

for (IndI = 1; IndI < n_elementos; IndI++)
{
	Temp = seq[indI]; //Copiar o elemento a ordenar

	for (IndD = IndI; IndD  > 0 && seq[indI-1] > Temp; IndD--) //Deslocar os elementos atras dele que lhe sao maiores
		seq[indD] = seq[indD-1];

	seq[indD] = Temp; //Inserir o elemento a ordenar na posicao
}
}


void MergeListSort (int seqA[], unsigned int n_elementosA, \
	    int seqB[], unsigned int n_elementosB, \
	    int seqC[], unsigned int *n_elementosC)
{
unsigned int IndI = 0, IndJ = 0, IndK = 0, IndC;

//Copiar o elemento da sequencia A ou o elemento da sequencia B
while (IndI < n_elementosA && IndJ < n_elementosB)
	if (seqA[indI] < seqB[indJ])
		seqC[indK++] = seqA[indI++];
	else seqC[indK++] = seqB[indJ++];

if (IndI < n_elementosA)
	for (IndC = IndI; IndC < n_elementosA; IndC++)
		seqC[indK++] = seqA[indC];
//Copiar os restantes elementos da sequencia A
else for (IndC =IndJ; IndC < n_elementosB; IndC++)
		seqC[indK++] = seqB[indC];
//Copiar os restantes elementos da sequencia B 

*n_elementosC = IndK; //Numero de elementos da sequencia C
}

Fonte-> Introdução à programação usando C de António Manuel Adrego da Rocha

Adaptado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora