INTRODUCCION
La búsqueda es una operación que tiene como objeto la localización de un elemento dentro de la estructura de datos con la que estamos trabajando.
Un algoritmo de búsqueda es una técnica para encontrar un valor dentro de la estructura, determinado como campo clave o llave.
La búsqueda termina.- con éxito, si encuentra la llave dentro de la estructura, sin éxito, pues no encuentra la llave dentro de la estructura.
El método de búsqueda a aplicar depende de si la lista esta ordenada o desordenada.
En base a esto, los algoritmos de búsqueda se clasifican en:
Internos.- aquellos que aplican a estructuras de datos como arreglos, tablas, listas ,etc.
Externos.- aquellos que aplican a archivos que se encuentran en dispositivos electrónicos.
También se pueden clasificar de acuerdo a si los datos se encuentran en orden o desordenados:
Secuencial o Lineal
Binaria o directa
BUSQUEDA SECUENCIAL
Es la forma mas simple de los métodos de búsqueda.
Consiste en reconocer y examinar cada uno de los elementos de la Lista o Arreglo, hasta encontrar el o los elementos buscados, o hasta haber recorrido todos los elementos de la lista.
Se define como el proceso de determinar el elemento, o su posición, que cumple con una condición; comparando con cada uno de los elementos en forma secuencial.
Se recomienda utilizar cuando el arreglo o lista no esta ordenado.
CODIFICACION EN C++:
1 int busq_lineal(int N, int array[],int elemento)
BUSQUEDA BINARIA
Es el método mas eficiente de búsqueda en una lista ordenada.
Básicamente el valor se compara con el elemento intermedio de la lista.
Sin son iguales, la búsqueda termina exitosamente; en caso contrario, debe buscarse en la mitad superior o inferior de la lista, repitiendo el proceso anterior.
Si recorre la lista y no ubica el valor, entonces no tiene éxito.
Consiste en dividir la lista original en dos listas más pequeñas.
·El consumo de recursos (memoria) es menor.
·Mayor eficiencia y velocidad de procesamiento.
·Posibilidad de dividir el trabajo en varios procesadores.
Se elige un elemento cualquiera (aunque en general se suele utilizar el que se encuentra en medio de la lista) que nos servirá como pivote.
Luego se recorre toda la lista, con el objeto de colocar los elementos más pequeños que el pivote a la izquierda del mismo, y los mayores a la derecha.
Las implementaciones más eficientes realizan esta tarea a la vez, recorriendo simultáneamente la lista en ambas direcciones e intercambiando entre sí cada par de elementos “descolocados” que se encuentran a su paso.
Culminada esta etapa tenemos un grupo de elementos menores que el pivote, el pivote, y otro grupo compuesto por números mayores a él.
En este punto es donde juega un papel importante la recursividad: si cada uno de esos grupos vuelve a dividirse en dos y se aplica lo explicado anteriormente de forma recursiva, tenemos resuelto el problema. Lo mejor de todo es que el tamaño de las sublistas -y por ende el tiempo que se necesita para procesarlas- es cada vez menor.
En cada nivel el tamaño de las sublistas la mitad del anterior, lo que permite ordenar una lista de 1024 elementos en 10 “pasadas”, y una de más de un millón en solo 20.
Este algoritmo es fuertemente dependiente de la “suerte” que hayamos tenido al elegir el elemento pivote.
Si somos tan burros como para elegir un elemento que se encuentre en uno de los extremos de la lista, habremos dividido el problema en dos partes muy dispares (una con solo un elemento, ya ordenada, y otra casi del mismo tamaño que la original, desordenada) y el algoritmo no será tan eficiente.
Programa en C
1 int pivotar (int v[],int izq,int der)
2 {
3 int posicionPivote =(izq + der)/2;
4 int valorPivote = v[posicionPivote];
5 int indiceAlmacenamiento;
6 swap (v, posicionPivote, der);//Se situal pivote al final del vector
A continuacion les muestro un video que encontre en youtuube, en el cual se muestra una danza que ejemplifica el procedimiento del mezcla.
Análisis de eficiencia
Trabaja con una lista auxiliar, lo cual consume memoria y obviamente trabajo extra al copiar las listas.
MONTICULO
Algoritmo de ordenación recursivo.
Es no estable.
Su complejidad es de O(nlogn).
Se basa en una propiedad de los montículos, en la que, la cima contiene el menor elemento (o el mayor) de todos los almacenados en el.
Heap.- significa cola de prioridades.
Descripcion
Consiste en almacenar todos los elementos de la lista en un heap (árbol), y luego extraer el nodo que queda como raíz del árbol (cima).
Se realiza en sucesivas iteraciones, obteniendo así la lista ordenada.
Se mapea un árbol binario de tal forma en el arreglo que el nodo en la posición i es el padre de los nodos en las posiciones (2*i) y (2*i+1).
El valor de un nodo es mayor o igual a los valores de sus hijos. El nodo padre tiene el valor mayor de todo su subárbol .
Procedimiento:
Convertir la lista en un árbol.
Construir una lista ordenada de atrás hacia adelante (mayor a menor) haciendo lo siguiente:
Sacar el valor máximo en el árbol (el de la posición 1).
Poner el valor en la lista ordenada.
Reconstruir el árbol con un elemento menos.
Usar el mismo arreglo para el árbol y la lista ordenada.
Pseudocodigo
function heapsort(array A[0..n]):
montículo M
integer i := 124578
for i = 0..n:
insertar_en_monticulo(M, A[i])
for i = 0..n:
A[i] = extraer_cima_del_monticulo(M)
return A
A continuacion les muestro un video que encontre en youtuube, en el cual se muestra una danza que ejemplifica el procedimiento del heapsort o monticulo.
Análisis de eficiencia
En el caso promedio, el heapsort no es tan eficiente como el qucksort.
El heapsort requiere 2 veces mas tiempo que el quicksort.
No es muy eficiente para pocos elementos, por la creacion del árbol y el calculo de la ubicación de padres e hijos.
Requerimientos.- de una sola variable para guardar el valor de intercambio.
Fuente:
Presentacion en PowerPoint "Estructuras: Algoritmos de ordenamiento y busqueda". Autor: M.C. Blanca I. Martnez C. Investigacion en Word "Algoritmos de busqueda y ordenamiento".
