Algoritmos de búsqueda
Una búsqueda lineal requiere que, por término medio, se inspeccionen la mitad de los elementos. La búsqueda binaria es más eficaz. Se basa en el principio de que el elemento central divide la lista en dos mitades. Al inspeccionar el elemento central, el programa puede determinar qué mitad contiene el elemento deseado. El algoritmo continúa repitiendo el proceso en la mitad que contiene el elemento requerido. A continuación se presenta un procedimiento en pseudocódigo para realizar este proceso.
A menudo es necesario fusionar dos listas de elementos. Esto sólo puede hacerse de forma eficiente si las listas están ambas en la misma secuencia. El algoritmo es más sencillo si se añaden al final de las listas valores de terminación mayores que cualquier valor de las listas antes de realizar la fusión. Un procedimiento en pseudocódigo para fusionar dos listas en una tercera es el siguiente:
La ordenación por burbujas no es muy eficiente, pero es sencilla de programar y es un algoritmo útil cuando no hay muchos elementos involucrados. La ordenación por burbujas realiza una serie de pasadas por los elementos, cada una de las cuales coloca los elementos en una secuencia ligeramente mejor. Durante una pasada, el algoritmo compara cada elemento con el siguiente y, si están fuera de secuencia, intercambia sus posiciones. El efecto se muestra a continuación.
Algoritmos de ordenación Número de comparaciones
La ordenación y la búsqueda es uno de los temas más importantes en DSA. El almacenamiento y la recuperación de información es una de las aplicaciones más comunes de los ordenadores hoy en día. Con el paso del tiempo, la cantidad de datos e información almacenada y accedida a través del ordenador se ha convertido en enormes bases de datos. Se han desarrollado muchas técnicas y algoritmos para mantener y procesar eficazmente la información en las bases de datos. El proceso de búsqueda de un determinado registro de datos en la base de datos se denomina búsqueda. El proceso de ordenar los registros en una base de datos se denomina clasificación. La ordenación y la búsqueda constituyen un importante campo de estudio de los métodos computacionales. Ambos son un campo de estudio muy importante en la estructura de datos y los algoritmos. Vamos a hablar de ambos temas en detalle.
La búsqueda es el proceso de encontrar un elemento concreto en una colección de elementos. Una búsqueda suele responder si el elemento está presente en la colección o no. La búsqueda requiere un campo clave, como el nombre, el ID o el código, que está relacionado con el elemento de destino. Cuando se encuentra el campo clave de un elemento de destino, se devuelve un puntero al elemento de destino. El puntero puede ser una dirección, un índice en un vector o matriz, o alguna otra indicación de dónde encontrar el objetivo. Si no se encuentra un campo clave que coincida, se informa al usuario.
Comparación de algoritmos de clasificación
En informática, un algoritmo de ordenación es un algoritmo que pone los elementos de una lista en un orden. Los órdenes más utilizados son el orden numérico y el orden lexicográfico, y son ascendentes o descendentes. Una ordenación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los de búsqueda y fusión) que requieren que los datos de entrada estén en listas ordenadas. La ordenación también suele ser útil para canonizar los datos y para producir una salida legible para el ser humano.
Desde los inicios de la informática, el problema de la ordenación ha atraído una gran cantidad de investigación, quizás debido a la complejidad de resolverlo de forma eficiente a pesar de su enunciado sencillo y familiar. Entre los autores de los primeros algoritmos de ordenación, en torno a 1951, se encontraba Betty Holberton, que trabajó en ENIAC y UNIVAC.[1][2] La ordenación de burbujas se analizó ya en 1956.[3] Los algoritmos asintóticamente óptimos se conocen desde mediados del siglo XX, y se siguen inventando nuevos algoritmos; el ampliamente utilizado Timsort data de 2002, y la ordenación de bibliotecas se publicó por primera vez en 2006.
Algoritmos de clasificación
La búsqueda binaria (o búsqueda de medio intervalo) sólo es aplicable a una matriz ordenada. Compara la clave de búsqueda con el elemento del medio. Si hay una coincidencia, devuelve el índice del elemento. Si la clave de búsqueda es menor que el elemento del medio, se repite la búsqueda en la mitad izquierda; en caso contrario, se busca en la mitad derecha. Si el elemento que queda por buscar es cero, devuelve “no encontrado”.
Elección del pivote: Si la lista ya está ordenada, elegir el primer o el último elemento como pivote resulta en un rendimiento peor de O(n2). Elegimos el elemento del medio, y cambiamos el elemento del extremo derecho, para no interferir con el proceso de partición.
La ordenación por cubos (o bin sort) funciona distribuyendo los elementos en un número de cubos, y cada cubo se ordena individualmente. La ordenación por cubos es una ordenación por distribución, y es un primo de la ordenación radix, en la que la ordenación empieza por el dígito más significativo y va bajando hasta los menos significativos. La ordenación por cubos no es una ordenación por comparación como la ordenación por burbujas, la ordenación por inserción o la ordenación por selección.