Algoritmos de Búsqueda y Ordenamiento

Búsqueda Lineal

En la búsqueda lineal se recorren los datos uno por uno hasta encontrar el dato deseado. Esto quiere decir que en un vector recorrerá desde la primera posición hasta la última y sólo se detendrá al encontrar el dato deseado o al terminar de recorrer el vector.

Búsqueda Binaria

Se utiliza el concepto «DIVIDE Y VENCERÁS». Para éste tipo de búsqueda los datos de un vector deben estar ordenados necesariamente. Primero se compara el elemento central del vector con el dato deseado. Si no es el deseado, se comprueba si el elemento deseado es mayor o menor al elemento central. Si es menor, entonces se vuelve a vuelve a tomar un dato central pero de la primera mitad de la lista sino, se toma un dato central de la segunda mitad de la lista. Después se vuelve a repetir el proceso desde la comparación del dato central con el dato deseado hasta que se encuentre el valor deseado.

Búsqueda Mediante Transformación de Claves (Hashing)

Esta es una función que consiste en transformar claves numéricas o alfanuméricas en direcciones o índices de un vector. No es necesario que los elementos de la clave estén ordenador para poder realizar este tipo de búsqueda. Veremos 4 métodos de transformación de claves: Truncamiento, plegamiento, aritmética modular y mitad del cuadrado.

1. Truncamiento

En este método se ignora parte de la clave y se deja la parte restante como índice. Ejemplos:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Plegamiento

• žPartición de la clave en diferentes partes y combinarlas.
• žTodas las partes, a excepción de la última, deben tener el mismo numero de dígitos que el tamaño del vector.

 

 

 

 

 

 

 

 

3. Aritmética Modular

• žLa clave se divide por el número de posiciones del vector.
• žEl resultado es el resto de la división

 

 

 

 

 

 

 

4. Mitad del cuadrado

• žSe calcula el cuadrado de la clave
• žDel resultado del calculo se tomarán sólo los números que se encuentran al centro.