Metodos de busqueda

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos.

-          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.

Métodos de Ordenamiento

El método de ordenamiento es un algoritmo utilizado para organizar un conjunto de datos dependiendo de lo requerido en el orden. Existen varios métodos como lo son:

-          Shaker sort:

Este método se lleva al cabo en 2 etapas, en la primera de ellas se trasladan los elementos mas pequeños hacia la parte izquierda del arreglo almacenando en una variable la posición del ultimo elemento intercambiado.

En la segunda etapa se trasladan los elementos mas grandes hacia la parte derecha del arreglo, almacenando en otra variable la posición del ultimo elemento intercambiado. Este algoritmo termina cuando ya no se producen cambios en el orden o bien cuando la variable que almacena el extremo izquierdo del arreglo es mayor que la que almacena el extremo derecho.

-          Shell:

En el método de ordenación Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo. 

-          Quicksort:

La idea central de este algoritmo consiste en los siguiente:

Se toma un elemento x de una posición cualquiera del arreglo.

Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.

Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

-          Merge sort:

Este método de ordenamiento toma la lista de llaves y la divide en dos partes, las cuales se ordenan en forma independiente. Finalmente, las dos listas ordenadas resultantes, se mezclan para formar la lista ordenada final.