Algoritmia

ALGORITMOS DE BÚSQUEDA Y ORDENACIÓN
BÚSQUEDAS

1. Búsqueda Secuencial:

Consiste en recorrer la lista, desde el primer elemento hasta el último, comparando con el valor buscado
Devolverá:
Si la lista contiene el elemento = a su posición, si no lo contiene un valor de fallo (-1).

Opción 1: O(n)
Opción 2: Caso mejor (primera posición) O(1)
Caso medio y casopesor Orden (n)

Implementado en Pseudocódigo
Implementado en C
Opción 1

Función secuencial (T[1..n], valor)

inicio

posición0

para i1 hasta n hacer
inicio
si T[i]= valor entonces
posición  i
fin
return posición;
fin



int Secuencial(int *lista,
int elementos,int valor)
{
int i, posicion;
posicion=-1;

for(i=0;i j entoncesdevolver 0

si no
inicio
k  (i+j)/2
caso_de valor < T[k]: j  k-1
valor = T[k]: devolver k
valor > T[k]: i  k+1
devolver b_recursiva(T[i..j],valor)
fin

fin


int BRecursiva(int *lista,int i,
int j,int valor)
{
int k;
if (i> j)
return -1;
else
{
k=(i+j)/2;
if(valor if(valor == lista[k]) return k;
if(valor > lista[k]) i=k+1;
return BRecursiva(lista,i,j,valor);
}
}





ORDENACIÓN

3. Burbuja

Va comparando elementos adyacentes y los intercambia si están desordenados, de esta manera los valores más pequeños, van burbujeando hacia la parte superior de la lista y los más grandes se hunden hacia la parte inferior.Necesitamos dos bucles, uno recorre la lista indicando la posición a la que debe burbujear, el elemento más pequeño de la lista desordenada, y otro interno que por cada iteración del externo, recorre la lista desordenada y se encarga del burbujeo.

El algoritmo está en el orden (n2) para todos los casos





Implementado en Pseudocódigo
Implementado en C

procedimientoordenación_burbuja (T[1..n])
inicio
para i  1 hasta n - 1 hacer
inicio

para j  n - 1 hasta i (inc = -1) hacer
inicio
si T[j] > T[j + 1] entonces
intercambiar(T[j],T[j + 1])
fin

fin
fin
procedimiento intercambiar (ref T[x],
ref T[y])
inicio
temp T[x]
T[x] T[y]
T[y] Temp

fin

void Burbuja( int *lista, intelementos)
{
int i,j;
for(i=0;i=i;j--)
{
if(lista[j]>lista[j+1])
Intercambiar(lista,j,j+1);
}
}
}

void Intercambiar(int *lista,
int p, int i)
{
int aux;
aux=lista[p];
lista[p]=lista[i];
lista[i]=aux;
}}ÇÇÇÇÇÇÇÇÇÇÇÇÇÇÇÇ}


4. Selección

Busca el elemento más pequeño(orden ascendente) en la lista desordenadaque queda pendiente y lo coloca al final de la lista ordenada.
Al principio la lista ordenada está vacía, mientras que la lista desordenada contiene los elementos que se irán examinando para formar la ordenada.

Necesitamos dos bucles, uno externo que indica la posición a insertar de la lista ordenada, y otro interno, que con cada iteración del externo, recorre la lista desordenada y se encargade buscar el elemento más pequeño a insertar.

El algoritmo está en el orden (n2) para todos los casos

Implementado en Pseudocódigo
Implementado en C

procedimiento selección(T[1..n])
inicio
para i 1 hasta n -1 hacer
inicio
minj  i
minx  T[i]

para j  i+1 hasta n hacer
inicio
si T[j] < minx entonces
inicio
minj  jminx  T[j]
fin
fin

T[minj]  T[i]
T[i]  minx
fin
fin

void Seleccion( int *lista, int elementos)
{
int i,j,menor,posicion;

for(i=0;ivalor)
{
lista[j+1]= lista[j];
j--;
}
lista[j+1]=valor;
}
}





6.Inserción Binaria

Se trata de insertar cada elemento de una lista desordenada en la posición que le...

Leer documento completo

Regístrate para leer el documento completo.