Los mejores algoritmos y estructuras de datos que realmente necesitas conocer

Si quieres convertirte en ingeniero de software, pero no sabes por dónde empezar, vamos a ahorrarte el suspenso: son los algoritmos y las estructuras de datos.

Una vez que entiendas lo esencial de estos pilares de la programación, empezarás a verlos por todas partes. Y cuantos más algoritmos y estructuras de datos aprendas, más te servirán como combustible para tu carrera como ingeniero de software.

Para empezar, primero vamos a hacer una inmersión profunda en Search y Sort, dos clases de algoritmos sin los que no puedes vivir. A continuación, vamos a hacer un rápido estudio del resto del paisaje que incluye árboles, gráficos, programación dinámica y toneladas más.

A grandes rasgos, hay dos categorías de algoritmos de búsqueda que necesitará conocer de inmediato: lineal y binario. La búsqueda en profundidad (DFS) y la búsqueda en amplitud (BFS) también son muy importantes, pero las guardaremos para la sección de recorrido de grafos más adelante.

Búsqueda lineal

Los algoritmos lineales y binarios se denominan así para describir cuánto tiempo (complejidad de tiempo) va a tomar una búsqueda basada en el tamaño de la entrada que se está buscando.

Por ejemplo, con los algoritmos de búsqueda lineal, si usted tiene 100 elementos para buscar, entonces el peor de los casos requeriría que usted busque en cada elemento de la entrada antes de llegar a su valor deseado. Se llama lineal porque el tiempo que se tarda en buscar está exactamente correlacionado con la cantidad de elementos en la búsqueda (100 elementos/entrada =100 comprobaciones/complejidad)

En resumen, lineal = simple (no hay nada inteligente en el algoritmo). Por ejemplo: imagina que intentas encontrar a tu amigo Lin entre una fila de personas que están de pie sin un orden determinado. Ya sabes cómo es Lin, así que simplemente tienes que mirar a cada persona, una por una, en secuencia, hasta que reconozcas o no a Lin. Eso es todo. Al hacerlo, estás siguiendo el algoritmo de búsqueda lineal

Búsqueda binaria

La búsqueda binaria recibe su nombre porque la palabra binaria significa «de o relativo a 2 cosas» y el algoritmo funciona dividiendo la entrada en dos partes hasta encontrar el elemento que se busca. Una mitad contiene el elemento buscado y la otra no. El proceso continúa hasta que el punto en el que se divide la entrada se convierte en el elemento buscado. La búsqueda binaria es básicamente un enfoque muy disciplinado del proceso de eliminación. Es más rápido que la búsqueda lineal, pero sólo funciona con secuencias ordenadas.

Un ejemplo debería dejar esto más claro. Supongamos que estás tratando de encontrar a tu amigo Bin (que mide 1,70 m) en una fila de personas que han sido ordenadas por su altura de izquierda a derecha, del más bajo al más alto. Es una fila muy larga, y no tienes tiempo de recorrerla una por una, comparando la altura de todos con la de Bin. ¿Qué puedes hacer?

Entras en la búsqueda binaria. Seleccionas a la persona que está en el centro de la fila y mides su altura. Mide 1,70 m. Así que enseguida sabes que esta persona, junto con todas las que están a su derecha, no es Bin. Ahora que has reducido el problema a la mitad, diriges tu atención al resto de la fila y eliges de nuevo a la persona del medio. Mide 1,70 m. Así que puedes descartar a esa persona y a cualquiera a su izquierda, reduciendo el problema a la mitad de nuevo. Y así sucesivamente. Después de cinco o seis de estas divisiones, rápidamente se encuentra a Bin en una fracción del tiempo que le tomó encontrar a Lin. Al hacerlo, has seguido el algoritmo de búsqueda binaria.

Ordenación

Ordenar, también conocido como ordenar, listas de elementos es una de las tareas de programación más comunes que harás como desarrollador. Aquí veremos dos de los algoritmos de ordenación más útiles: MergeSort y QuickSort.

MergeSort

Supongamos que en lugar de encontrarnos con la línea ordenada de personas del ejemplo anterior, necesitamos crear una línea ordenada de personas a partir de un grupo desordenado. No tienes mucho tiempo, así que ideas una estrategia para acelerar las cosas.

Primero haces que el grupo de personas, que están todas apiñadas, se divida en dos. A continuación, haces que cada uno de los dos grupos se divida de nuevo en dos, y así sucesivamente, hasta que te ocupes exclusivamente de los individuos. Entonces empiezas a emparejar a los individuos, y haces que el más alto de los dos de cada pareja se sitúe a la derecha del otro. Muy pronto todo el mundo está organizado en estas parejas ordenadas izquierda-derecha.

Luego, empiezas a fusionar las parejas ordenadas en grupos ordenados de cuatro; luego fusionas los grupos ordenados de cuatro en grupos ordenados de ocho; y así sucesivamente. Finalmente, descubres que tienes una línea completa de personas ordenadas en altura, como la que encontraste anteriormente. Sin saberlo, has seguido el algoritmo MergeSort para lograr tu hazaña.

QuickSort

QuickSort es un poco demasiado complejo para imaginarlo fácilmente con la gente, así que vamos a acercarnos un poco al código. Para empezar, imaginemos que tienes una lista desordenada, o array, de ocho números que quieres ordenar.

4 2 13 6 15 12 7 9

Podrías usar MergeSort, pero has oído que QuickSort es generalmente más rápido, así que decides probarlo. Tu primer paso es elegir un número de la lista llamado pivote. La elección del número de pivote correcto marcará la diferencia en la rapidez de su QuickSort, y hay fórmulas preparadas para elegir buenos pivotes. Pero por ahora, vamos a mantenerlo simple y simplemente ir con el último número en la matriz para nuestro número de pivote: 9.

4 2 13 6 15 12 7 9

Para hacer el siguiente paso más fácil de seguir, vamos a crear un separador al principio de la matriz y representarlo con el signo de libra.

# 4 2 13 6 15 12 7 9

Moviendo de izquierda a derecha por nuestro array, nuestro objetivo es poner cualquier número menor que el pivote (9) a la izquierda del separador, y cualquier número mayor (o igual) que el pivote a la derecha del separador. Comenzamos con el primer número de nuestra matriz: 4. Para moverlo a la izquierda del separador, simplemente movemos el separador un elemento hacia arriba:

4 # 2 13 6 15 12 7 9

Hacemos lo mismo con el siguiente número: 2.

4 2 # 13 6 15 12 7 9

Pero luego llegamos al 13, que es mayor que el número pivote 9 y ya está a la derecha del separador. Así que lo dejamos solo. A continuación llegamos al 6, que tiene que ir a la izquierda del separador. Así que primero lo intercambiamos con el 13 para colocarlo en su posición:

4 2 # 6 13 15 12 7 9

Luego pasamos el separador:

4 2 6 # 13 15 12 7 9

El siguiente es el 15, que ya está a la derecha del separador, así que lo dejamos solo. Luego tenemos el 12. Lo mismo. Pero el 7, nuestro último número antes de llegar al pivote, necesita el mismo tipo de ayuda para moverse que el 6. Así que cambiamos el 7 por el 13 para colocarlo en su posición:

4 2 6 # 7 15 12 13 9

Después, una vez más, pasamos el separador:

4 2 6 7 # 15 12 13 9

Por último, llegamos a nuestro número pivote: el 9. Siguiendo la misma lógica que tenemos arriba, intercambiamos 15 con 9 para que el número pivote esté donde tiene que estar:

4 2 6 7 # 9 12 13 15

Dado que todos los números a la izquierda de 9 son ahora menores que 9, y todos los números a la derecha de 9 son mayores que 9, hemos terminado con nuestro primer ciclo de QuickSort. A continuación, trataremos cada conjunto de cuatro números a cada lado del separador como un nuevo array al que aplicar QuickSort. Nos ahorraremos los detalles, pero la siguiente ronda nos dará cuatro pares de números a los que aplicar fácilmente nuestra ronda final de QuickSort. El resultado final será la siguiente lista ordenada que nos ha llevado menos tiempo generar que con el más sencillo MergeSort:

2 4 6 7 9 12 13 15

Hoja de trucos de algoritmos de ordenación

Estos son los algoritmos de ordenación más comunes con algunas recomendaciones sobre cuándo utilizarlos. Internalícelos. Se utilizan en todas partes!

Ordenación por pila: Cuando no necesitas una ordenación estable y te importa más el rendimiento del peor caso que el del caso medio. Está garantizado que es O(N log N), y utiliza O(1) espacio auxiliar, lo que significa que no te quedarás inesperadamente sin espacio en el montón o la pila en entradas muy grandes.

Introsort: Esta es una ordenación rápida que cambia a una ordenación de montón después de una cierta profundidad de recursión para evitar el peor caso de O(N²) de la ordenación rápida. Casi siempre es mejor que una ordenación rápida simple, ya que se obtiene el caso medio de una ordenación rápida, con un rendimiento O(N log N) garantizado. Probablemente la única razón para utilizar una ordenación de pila en lugar de esta es en sistemas con severas restricciones de memoria donde el espacio de pila O(log N) es prácticamente significativo.

Ordenación de inserción: Cuando se garantiza que N es pequeño, incluso como caso base de una ordenación rápida o una ordenación por fusión. Aunque es O(N²), tiene una constante muy pequeña y es una ordenación estable.

Ordenación por burbujas, ordenación por selección: Cuando estás haciendo algo rápido y sucio y por alguna razón no puedes usar el algoritmo de ordenación de la biblioteca estándar. La única ventaja que tienen sobre la ordenación por inserción es que son ligeramente más fáciles de implementar.

Ordenación rápida: Cuando no se necesita una ordenación estable y el rendimiento del caso medio importa más que el del caso peor. Una ordenación rápida es O(N log N) en promedio, O(N²) en el peor caso. Una buena implementación utiliza O(log N) de almacenamiento auxiliar en forma de espacio de pila para la recursión.

Ordenación por fusión: Cuando se necesita una ordenación estable, O(N log N), esta es casi su única opción. Las únicas desventajas son que utiliza espacio auxiliar O(N) y tiene una constante ligeramente mayor que una ordenación rápida. Hay algunas ordenaciones de fusión en el lugar, pero, por lo que sé, no son estables o son peores que O(N log N). Incluso las ordenaciones en el lugar O(N log N) tienen una constante mucho mayor que la ordenación rápida simple que son más curiosidades teóricas que algoritmos útiles.