Métodos de búsqueda

BÚSQUEDA.

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.Siendo el array de una dimensión o lista una estructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: búsqueda lineal y búsqueda binaria.

Búsqueda Secuencial: La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Búsqueda Binaria. La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.

Diferentes Métodos de ordenación

Método de ordenación Burbuja

void bubble(int *start, int *end) //Ordena un conjunto de números enteros de menor a mayor
{ short fin;
do
{ fin=0;
for (int *i=start;i!=*end;i++)
{
if (*i>*(i+1))
{ intercambia(i, i+1);
fin=1;
}
}
} while
(fin!=1);
}


http://seduca.uaemex.mx/SofEdu/Sim/MetOrd/metodos.html

Inserción Directa. (A,N)

La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenado. Este proceso se repite desde el segundo hasta el n-ésimo elemento.
El algoritmo es el siguiente.
1. Repetir con I desde 2 hasta N... Hacer Aux <-- A[I], K <-- I-1... 1.1
Repetir mientras (Aux <> 1).... Hacer A[K+1] <-- A[K] y K <-- K-1...
1.2 {Fin del ciclo del paso 1.1}... 1.3 Si A[K] lt;= Aux, entonces.......... A[K+1] <-- Aux........ sino........ A[K+1] <-- A[K] y A[K] <-- Aux... 1.4 {Fin del condicional del paso 1.3}2. {Fin del ciclo del paso 1}

Ordenamiento Radix

Ordenamiento de distribución por conteoUn problema que se presenta con frecuencia es el siguiente: "Ordenar un archivo con N registros cuyas llaves son enteros comprendidos entre 0 y M-1". SiM no es muy grande, se puede usar el algoritmo de distribución porconteo. La idea básica es contar el número de veces que serepite cada llave diferente y en una segunda pasada utilizar el conteo paraposicionar los registros en el archivo.

Mezcla

Ordenación por mezcla (Merg Sort).
Intercalación de archivos ó mezcla de archivos.Por intercalación de archivos se entiende la unión o fusión de dos o más archivos ordenados de acuerdo con un determinado campo en un solo archivo.

Monticulo

Ordenación por el método de heapsort
El método de ordenación heapsort es también conocido con el nombre "montículo" en el mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautió así. Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de este algoritmo consiste en lo siguiente:
Construir un montículo.
Eliminar la raíza del montículo en forma repetida.
Definición. un montículo se define como "Para todo nodo del árbol se debe cumplir que su valor de cualquiera de sus hijos".
Para representar un montículo en un arreglo lineal:
El nodo k se almacena en la posición k correspondiente del arreglo.
El hijo izquierda del nodo k, se almacena en la posición 2 * k.
El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
Inserción de un elemento en un montículo.
La inserción de un elemento en un motnículo se lleva a cabo de la siguiente manera:
Se inserta el elemento en la primera posición disponible.
Se verifica si su valor es mayor que el de su padre. Si se cumple está condición entonces se efectúa el intercambio. Sino se cumple está condición, entonces, el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo. Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.
Eliminación de un montículo.
El proceso para obtener los elementos ordenados se efectúa eliminando la raíz del montículo en forma repetida. Ahora bien, los pasos necesarios para lograr la eliminación de la raíz del montículo son los siguientes:
Se reemplaza la raíz con el elemento que ocupa la última posición del montículo .
Se verifica si el valor de la raíz es menor que el valor más grande de sus hijos. Si se cumple la condición entonces se efectúa el intercambio. Sino se cumple la condición entonces el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo.
Cabe aclarar que le paso 2 se aplica de manera recursiva y desde arriba hacia abajo.
El algoritmo es el siguiente.
Montículo (A,N).
{El algoritmo ordena los elementos del arreglo utilizando el método del montículo. A es un arreglo de N elementos}.
1. Llamar al algoritmo INSERTAMONTÍCULO con A y N.2. Llamar al algoritmo ELIMINAMONTÍCULO con Ay N.
Insertamontículo (A,N).
{El algoritmo inserta elementos en un montículo representando como arreglo. A es un arreglo de N elementos.}
1. Repetir con I desde 2 hasta N.. Hacer k <-- I y Band <-- Verdadero.. 1.1 Repetir mientras k > 1 y Band = Verdadero...... Hacer Band <-- Falso...... 1.1.1 Si A[k] A[parte entera (k entre 2)] entonces............ Aux <-- A[parte entera (k entre 2)]............ A[parte entera (k entre 2)] <-- A[k]............ Band <>QuickSort (se estima un 70%), es el único que garantiza que aún en el peor caso su tiempo de ejecución es proporcional a: (n * log n), 0 (n * log n).