La historia de la informática está llena de algoritmos brillantes que resolvieron problemas complejos de forma elegante. Algunos ordenan datos, otros encuentran caminos y otros protegen tus tarjetas de crédito.
Los algoritmos famosos son soluciones clásicas a problemas que aparecen una y otra vez en informática.
Ya sabemos qué es un algoritmo y cómo medir su eficiencia con Big O. Ahora toca ponerles nombre a algunas de esas recetas que han acabado apareciendo en miles de programas, librerías y sistemas reales.
No hace falta que sepáis implementarlos todos de memoria ahora mismo. Lo importante es saber que existen, qué problema resuelven y cuándo os sonará su nombre.
Resumen
Esta lista no pretende ser completa. Es una primera vuelta por algunos algoritmos que merece la pena reconocer.
| Categoría | Algoritmos | ¿Para qué sirven? |
|---|---|---|
| Ordenación | QuickSort, Merge Sort, Timsort | Ordenar datos eficientemente |
| Búsqueda | Binary Search, DFS, BFS | Encontrar elementos o recorrer estructuras |
| Grafos | Dijkstra, A* | Buscar caminos y rutas |
| Seguridad | RSA, SHA-256 | Proteger comunicaciones y validar integridad |
| Compresión | Huffman | Reducir tamaño sin perder información |
| Web e IA | PageRank, backpropagation | Ranking, aprendizaje automático |
Algoritmos de ordenación
Ordenar datos es una de las tareas más repetidas en informática. Listas de clientes, resultados de búsqueda, fechas, puntuaciones, archivos… todo acaba ordenándose tarde o temprano.
Bubble Sort
Bubble Sort se enseña mucho porque es muy fácil de entender. Compara elementos vecinos y los intercambia si están en orden incorrecto.
Los elementos grandes van “burbujeando” hacia el final de la lista.
- Complejidad típica:
O(n^2). - Ventaja: sencillo para aprender.
- Inconveniente: lento para listas grandes.
QuickSort
QuickSort usa la estrategia de divide y vencerás. Elige un pivote, coloca a un lado los valores menores y al otro los mayores, y repite el proceso en cada sublista.
En la práctica suele ser muy rápido, aunque su peor caso clásico es O(n^2) si se eligen mal los pivotes.
- Complejidad media:
O(n log n). - Ventaja: muy rápido en muchos escenarios reales.
- Inconveniente: no es estable en sus versiones habituales.
Merge Sort
Merge Sort también divide la lista en trozos, ordena cada parte y luego las fusiona.
Su gran punto fuerte es que tiene un comportamiento muy predecible y puede ser estable.
- Complejidad:
O(n log n). - Ventaja: estable y consistente.
- Inconveniente: suele necesitar memoria auxiliar
O(n).
Cuando llamáis a sort() en un lenguaje moderno, normalmente se ejecuta una variante muy optimizada, a veces híbrida. Por ejemplo, Python usa Timsort, que combina ideas de Merge Sort e Insertion Sort.
Algoritmos de búsqueda
Una vez tenemos datos, queremos encontrar cosas. Y aquí hay algoritmos que conviene tener en la cabeza.
Búsqueda binaria
La búsqueda binaria encuentra un elemento en una lista ordenada dividiendo el espacio de búsqueda por la mitad en cada paso.
Es como buscar una palabra en un diccionario de papel. No empiezas por la primera página; abres por la mitad y vas descartando bloques enteros.
- Complejidad:
O(log n). - Requisito: la colección debe estar ordenada.
DFS
DFS (Depth First Search) recorre un árbol o grafo yendo tan profundo como pueda por un camino antes de retroceder.
Es útil para explorar laberintos, recorrer estructuras jerárquicas, detectar ciclos o analizar dependencias.
- Uso típico: árboles, grafos, backtracking.
BFS
BFS (Breadth First Search) explora primero los vecinos cercanos y luego se va alejando.
En grafos sin pesos, BFS encuentra el camino con menor número de pasos.
- Uso típico: rutas por niveles, distancia mínima en grafos sin pesos.
Algoritmos de caminos y grafos
Los grafos aparecen por todas partes: mapas, redes sociales, dependencias entre tareas, rutas de paquetes por internet, árboles de decisión…
Dijkstra
El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen al resto de nodos en un grafo con pesos no negativos.
Es una de esas ideas que aparecen en mapas, redes y sistemas de planificación.
- Uso típico: rutas, redes, costes mínimos.
- Ojo: no funciona correctamente si hay pesos negativos.
A*
A* es una búsqueda de caminos que usa una heurística para priorizar las rutas que parecen acercarse más al destino.
Dijkstra explora de forma más uniforme. A* intenta ir con algo más de intención, siempre que la heurística esté bien elegida.
- Uso típico: videojuegos, mapas, robótica.
Algoritmos de seguridad
Sin algoritmos criptográficos, internet sería un sitio bastante incómodo para comprar, iniciar sesión o enviar información privada.
RSA
RSA es un algoritmo de criptografía asimétrica. Usa una clave pública para cifrar o verificar, y una clave privada para descifrar o firmar.
Su seguridad se apoya en la dificultad de factorizar números muy grandes, aunque en sistemas modernos suele combinarse con otros algoritmos dentro de protocolos más amplios.
- Uso típico: intercambio de claves, firmas digitales, certificados.
Hashing
Los algoritmos de hash transforman datos de cualquier tamaño en una huella de tamaño fijo.
No sirven para “descifrar” después. Sirven para comprobar integridad, comparar datos o almacenar contraseñas de forma más segura (siempre con sal y algoritmos adecuados para contraseñas).
- Ejemplos: SHA-256, SHA-3, BLAKE2.
- Ojo: MD5 y SHA-1 ya no se consideran seguros para usos criptográficos.
Algoritmos de compresión
La compresión busca representar la misma información usando menos espacio.
Huffman Coding
Huffman es un algoritmo de compresión sin pérdida.
Asigna códigos más cortos a los símbolos más frecuentes y códigos más largos a los símbolos raros. Así reduce el tamaño total sin perder información.
- Uso típico: compresión de texto y como componente dentro de formatos más grandes.
Algoritmos de la web e inteligencia artificial
Terminamos con dos nombres que aparecen mucho cuando hablamos de web moderna e IA.
PageRank
PageRank fue una de las ideas que hizo destacar a Google en sus primeros años.
Modela la web como un grafo de enlaces. Una página no es importante solo porque tenga muchas palabras clave, sino porque otras páginas importantes apuntan hacia ella.
- Idea principal: los enlaces funcionan como votos, pero no todos los votos pesan igual.
Backpropagation
Backpropagation es el algoritmo que permite entrenar redes neuronales ajustando sus pesos a partir del error cometido.
Usa cálculo diferencial, concretamente la regla de la cadena, para repartir el error hacia atrás por la red.
- Uso típico: entrenamiento de redes neuronales.
