Busqueda en listas, secuencial y Binaria

BUSQUEDA EN LISTAS
Secuencial y Binaria
INTRODUCCION
La ordenación o clasificación de datos (sort, en inglés) es una operación consistente en disponer un conjunto —estructura— de datos en algún determinado orden con respecto a uno de los campos de elementos del conjunto.
En terminología de ordenación, el elemento por el cual está ordenado un conjunto de datos (o se está buscando) sedenomina clave.
. Una colección de datos (estructura) puede ser almacenada en un archivo, un array (vector o tabla), un array de registros, una lista enlazada o un árbol.
Cuando los datos están almacenados en un array, una lista enlazada o un árbol, se denomina ordenación interna.
Si los datos están almacenados en un archivo, el proceso de ordenación se llama ordenación externa.
. 4, 5, 14, 21, 32,45 orden ascendente
75, 70, 35, 16, 14, 12 orden descendente
La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. En el caso de la operación de ordenación, dos criterios se suelen seguir a la hora de decidir qué algoritmo —de entre los que resuelven la ordenación— es el más eficiente:
1)tiempo menor de ejecución en computadora2)menor número de instrucciones
BUSQUEDA SECUENCIAL
La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave. En una búsqueda secuencial (a veces llamada búsqueda lineal), los elementos de una lista o vector se examinan en secuencia, uno después de otro.
El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda. Dado queel array no está en un orden prefijado, es probable que el elemento a buscar pueda ser el primer elemento, el último elemento o cualquier otro. De promedio, al menos el programa tendrá que comparar la clave de búsqueda con la mitad de los elementos del array. El método de búsqueda lineal funcionará bien con arrays pequeños o no ordenados. La eficiencia de la búsqueda secuenciales pobre, tienecomplejidad lineal,O(n).
Ventajas
Es el algoritmo más simple de búsqueda y no requiere ningún proceso previo de la tabla, ni ningún conocimiento sobre la distribución de las llaves. La búsqueda secuencial es el área del problema donde previamente existían mejores algoritmos.
Es el mejor método de búsqueda para registros desordenados y revisa nodo por nodo sin brincar ninguno ( es muy seguro).Desventajas
Este método de búsqueda 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. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.
Si los registros a los que se accede con frecuencia no están al principio del archivo, la cantidad promedio decomparaciones aumenta notablemente dado que se requiere mas tiempo para recuperar dichos registros.
Para las aplicaciones interactivas que incluyen peticione s o actualizaciones de registros individuales, los archivos secuenciales ofrecen un rendimiento pobre.
PRINCIPALES APLICACIONES
Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos paradichas aplicaciones si se procesan todos los registros.
Un ejemplo claro para utilizar esta técnica de búsqueda es cuando se tiene una base de datos no muy grande en un negocio pequeño donde los registros más usados son llamados con frecuencia , es aquí donde esta técnica es fuerte, ya que se aplica a un patrón de búsqueda pequeño, sencillo y manejable; es decir como si fuera una descripción, esuno tras otro.
BUSQUEDA BINARIA
La búsqueda secuencial se aplica a cualquier lista. Si la lista está ordenada, la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra del primer apellido o de la...