Estructura de datos

ESTRUCTURA DE DATOS

UNIVERSIDAD CUAUHTEMOC

ING. EN SISTEMAS

METODO DE BUSQUEDA
Búsqueda Binaria: La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coincidenfinaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento 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.
Estemétodo se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria son:
* La lista debe estar ordenada, en un orden especifico de acuerdo al valor de la clave.
* Debe conocerse el número de elementos.
Si el conjunto de elementos es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo detipo divide y vencerás:
1. Se divide el elemento en dos partes.
2. Se determina la parte que debe contener la clave buscada.
3. Se repite el proceso en esa parte.
Una forma razonable de dividir el conjunto de elementos es mantener los elementos ordenados y después utilizar los índices del arreglo ordenado para determinar la parte del arreglo sobre la que se va a trabajar.
Búsquedasecuencial:
La búsqueda secuencial, también se le conoce como búsqueda lineal.
Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la clave indicada (k) o hasta el final de la lista.
Este método consiste en recorrer el arreglo o vector elemento aelemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del vector y se observa una casilla tras otra hasta que se encuentre 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 vector o arreglo no esta en ningún orden en particular, existe la mismaprobabilidad de que el valor se encuentra ya se en el primer elemento, como en el ultimo. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del vector.
El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

Diferencias entre ambos métodos:
En el caso del método de búsqueda binaria, los arreglos deben estarúnicamente ordenados, como se planteo anteriormente, por su parte el método de búsqueda secuencial o lineal, puede emplearse tanto en arreglos pequeños, como en aquellos que no están ordenados.
En segundo orden, podemos ver que el método de búsqueda binaria, es el método más eficiente para encontrar elementos en un arreglo ordenado, lo contrario sucede con el método de búsqueda secuencial ya queeste es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas.



METODO DE ORDENACION
El ordenamiento es uno de los procesos más comunes y útiles en el procesamiento de datos, es la clasificación u ordenación de los mismos. La colocación en orden de una lista de valores se le llama ordenación. Por ejemplo, se podría disponer de unalista de valores numéricos en orden ascendente o descendente, o bien una lista de nombres en orden alfabético.
El método de ordenación por burbuja es el mas conocido y popular entre estudiantes y aprendices de programación.
Este método se basa en la ordenación por cambios de elementos, ya que se van comparando de dos en dos los elementos de la tabla (vector). Si nosotros deseamos ordenar...