En este post vamos a cubrir un par de algoritmos fundamentales, incluyendo un algoritmo de búsqueda común conocido como búsqueda binaria, así como dos métodos de ordenación, merge sort y quick sort [1]. Para cada algoritmo, hablaremos de cómo funcionan y de algunos detalles sobre el tiempo de ejecución. Si estás buscando algún código de ejemplo, por favor mira mis implementaciones para la ordenación binaria, tomadas de [2], la ordenación por fusión tomada de [3] y la ordenación rápida tomada de [4].
En la búsqueda binaria, asumimos que empezamos con un array ordenado, y que estamos buscando un elemento particular dentro de ese array [1]. Elegimos el punto medio de la matriz y lo comparamos con el valor que estamos buscando [1]. Si el punto medio es menor que el valor, entonces sabemos que debemos buscar a la derecha (es decir, en las entradas más grandes); si el punto medio es mayor que el valor, entonces buscamos a la izquierda (es decir, en las entidades más pequeñas) [1]. De este modo, cortamos la matriz por la mitad y repetimos el proceso: miramos el punto medio y, en función de cómo se compare con el valor que buscamos, vamos a la izquierda o a la derecha. Repetimos este proceso hasta que encontremos el valor deseado.
La importancia de la ordenación radica en el hecho de que la búsqueda de datos puede optimizarse a un nivel muy alto, si los datos se almacenan de forma ordenada. La ordenación también se utiliza para representar los datos en formatos más legibles. A continuación se presentan algunos ejemplos de ordenación en escenarios de la vida real.
Los algoritmos de ordenación pueden requerir algo de espacio extra para la comparación y el almacenamiento temporal de algunos elementos de datos. Estos algoritmos no requieren ningún espacio extra y se dice que la ordenación ocurre en el lugar, o por ejemplo, dentro del propio array. Esto se llama ordenación en el lugar. La ordenación de burbujas es un ejemplo de ordenación en el lugar.
Sin embargo, en algunos algoritmos de ordenación, el programa requiere un espacio mayor o igual a los elementos que se ordenan. La ordenación que utiliza un espacio igual o superior se denomina ordenación no in situ. La ordenación por fusión es un ejemplo de ordenación no localizada.
Se dice que un algoritmo de ordenación es adaptativo si aprovecha los elementos ya “ordenados” de la lista que se va a ordenar. Es decir, si al ordenar la lista de origen hay algún elemento ya ordenado, los algoritmos adaptativos lo tendrán en cuenta e intentarán no reordenarlos.
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 requerido. 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 manera 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.
Un algoritmo es un procedimiento paso a paso que define un conjunto de instrucciones que deben ejecutarse en un orden determinado para obtener el resultado deseado. Los algoritmos suelen crearse independientemente de los lenguajes subyacentes, es decir, un algoritmo puede implementarse en más de un lenguaje de programación.
Escribimos los algoritmos paso a paso, pero no siempre es así. La escritura de algoritmos es un proceso y se ejecuta después de que el dominio del problema esté bien definido. Es decir, debemos conocer el dominio del problema, para el que estamos diseñando una solución.
En el diseño y análisis de algoritmos, normalmente se utiliza el segundo método para describir un algoritmo. Facilita al analista el análisis del algoritmo ignorando todas las definiciones no deseadas. Puede observar qué operaciones se utilizan y cómo fluye el proceso.
Vamos a aprender sobre el análisis de algoritmos a priori. El análisis de algoritmos se ocupa del tiempo de ejecución de varias operaciones. El tiempo de ejecución de una operación puede definirse como el número de instrucciones informáticas ejecutadas por operación.