Algoritmos
Fundamentales

Tres lecciones para entender qué es un algoritmo, cómo se mide su coste y cómo se busca en una lista.

1. 01

   Qué es un algoritmo

   ¿Cuál es el mayor de estos números? Lo ves en un segundo. Pero una computadora no ve la lista completa: hay que explicarle, paso a paso, cómo encontrarlo. Con la analogía de un torneo, esta lección escribe el primer algoritmo en Python y muestra qué pasa cuando la lista está vacía.

   aprenderás

   • Qué es un algoritmo: pasos exactos, de la entrada a la salida.
   • A escribir una función con def, un bucle for y una comparación if.
   • Por qué un algoritmo de verdad tiene que funcionar con cualquier entrada (incluida la lista vacía).
   • A contar comparaciones: seis con seis números, mil con mil números.
2. 02

   Big O: cómo medimos un algoritmo

   Dos programas resuelven el mismo problema. Con diez datos, los dos terminan al instante. ¿Y con un millón? Para responder, no se miden segundos: se cuentan pasos. Con la analogía de una fiesta, esta lección introduce Big O y muestra las tres formas básicas de crecer: constante, lineal y cuadrática.

   aprenderás

   • A contar pasos en lugar de segundos.
   • La diferencia entre un bucle (recorrer), un acceso directo (primero) y dos bucles anidados (parejas).
   • Que duplicar la lista duplica el trabajo en un bucle lineal y lo cuadruplica en uno cuadrático.
   • Que dos bucles uno tras otro se suman; dos bucles uno dentro de otro se multiplican.
3. 03

   Búsqueda lineal y binaria

   Buscas un nombre en una agenda de papel. Puedes empezar en la primera página y avanzar de una en una. O abrir por la mitad y decidir hacia dónde seguir. Los dos encuentran el nombre, pero no tardan lo mismo. Con mil elementos, la búsqueda lineal hace hasta mil pasos; la binaria, como máximo diez. Y con un millón: un millón contra veinte.

   aprenderás

   • La búsqueda lineal, con len, range(len(nums)), nums[i] y == frente a =.
   • La búsqueda binaria, con low, high, mid, while, //, elif y else.
   • Por qué la binaria exige datos ordenados: con una lista desordenada descarta la mitad equivocada y devuelve -1 aunque el valor esté.
   • Por qué la lineal cuenta comparaciones y la binaria cuenta vueltas (cada vuelta puede hacer dos comparaciones).

Cuatro lecciones para poner datos en orden, de la burbuja a quick sort, pasando por la recursión y merge sort.

1. 04

   Ordenamiento simple: burbuja y selección

   Con cinco números, ordenarlos es inmediato. Pero una computadora solo puede comparar dos valores a la vez. Esta lección enseña dos formas de ordenar con esa herramienta: burbuja (comparar vecinos e intercambiarlos) y selección (buscar el menor y llevarlo a su lugar). Con [5, 2, 9, 1, 7], las dos hacen diez comparaciones, pero burbuja hace cinco intercambios y selección solo tres.

   aprenderás

   • El ordenamiento de burbuja, con copy, dos bucles for anidados y el intercambio en una línea a, b = b, a.
   • La mejora con hubo_cambio y break: si una pasada no cambia nada, la lista ya está ordenada.
   • El ordenamiento por selección, con la variable menor y un solo intercambio por vuelta.
   • El crecimiento cuadrático: con 100 elementos en orden inverso, las dos hacen 4.950 comparaciones.
2. 05

   Recursión

   Una caja. Dentro, otra caja. Y dentro de esa, otra más. En algún lugar del fondo hay una llave. ¿Cómo la encuentras si no sabes cuántas cajas hay? Abres una caja. Si dentro hay una llave, terminaste. Si dentro hay otra caja, haces exactamente lo mismo con ella. Eso es recursión: resolver un problema aplicando la misma regla a una versión más pequeña del mismo problema.

   aprenderás

   • Las dos piezas de toda recursión: el caso base (la llave) y el caso recursivo (la caja).
   • A escribir una función que se llama a sí misma, con el factorial como ejemplo: factorial(4) = 4 × factorial(3).
   • La pila de llamadas: cuatro llamadas abiertas para factorial(4), cada una con su propio n.
   • Qué pasa sin caso base: RecursionError (el límite por defecto de Python es de mil llamadas en espera).
3. 06

   Merge sort

   Ordenar mil números con burbuja, en el peor caso, toma casi quinientas mil comparaciones. Hay una forma de hacerlo con menos de nueve mil. Y la idea cabe en una frase: juntar dos montones que ya están ordenados es fácil. Merge sort parte la lista a la mitad, ordena cada mitad con la misma función y las mezcla de vuelta.

   aprenderás

   • A mezclar dos listas ordenadas en una sola, con while y and, .append() y cortes de lista (izq[i:], nums[:mitad], nums[mitad:]).
   • La parte recursiva: caso base (lista de cero o un elemento) y dos llamadas recursivas.
   • Por qué el trabajo crece como n log n: con 1.000 elementos hay 10 niveles y unos 10.000 elementos colocados.
   • La comparación con burbuja: 499.500 comparaciones frente a 5.044 en orden inverso, y un peor caso de 8.977.
4. 07

   Quick sort

   Merge sort parte la lista por la mitad sin mirar los datos. ¿Y si primero los miráramos? Con una sola pasada, un elemento puede quedar en su lugar definitivo, para siempre. Quick sort elige un pivote, manda los menores a un lado y los mayores al otro, y repite en cada lado. La diferencia con merge sort: quick sort hace su trabajo al partir; merge sort, al volver.

   aprenderás

   • A partir una lista en menores y mayores que un pivote, con una función que devuelve dos valores y los reparte en dos variables (izq, der = partir(...)).
   • La recursión de quick sort, con el pivote en medio y [pivote] como lista de un solo elemento.
   • El peor caso: si la lista ya está ordenada y el pivote es el primero, cada nivel quita un solo elemento. Con 1.000 elementos, RecursionError.
   • La solución: elegir el pivote del medio. Con 500 elementos ordenados, de 124.750 comparaciones se baja a 3.498.

Cuatro lecciones para elegir la estructura correcta según lo que vayas a hacer con los datos: pilas, colas, listas enlazadas, tablas hash y árboles.

1. 08

   Pilas y colas

   Pulsas deshacer, y desaparece lo último que hiciste, no lo primero. ¿Cómo recuerda tu computadora todo lo que hiciste, para deshacerlo en orden inverso? Con una pila: el último en entrar es el primero en salir. Con una cola, en cambio, el primero en entrar es el primero en salir, como en la fila del supermercado.

   aprenderás

   • A usar una lista de Python como pila, con append para meter y pop para sacar por arriba.
   • A usar deque como cola, con append para meter por el final y popleft para sacar por el inicio.
   • A invertir una palabra con una pila: «datos» se convierte en «sotad».
   • Los errores de sacar de una pila o cola vacía: IndexError con su mensaje exacto.
   • La conexión con la recursión: la pila de llamadas de la lección 5 es una pila.
2. 09

   Listas enlazadas

   En una lista de Python, los elementos viven pegados, uno al lado del otro. Si quieres agregar uno al principio, todos los demás tienen que correrse un lugar. ¿Y si cada elemento supiera dónde está el siguiente, y no necesitara estar pegado a nadie? Eso es una lista enlazada: nodos unidos por referencias.

   aprenderás

   • A definir un nodo con class, __init__(self, valor) y dos atributos: el valor y la pista al siguiente (None si no hay).
   • A agregar al inicio sin mover a nadie: crear un nodo, enlazarlo con la cabeza y devolverlo como nueva cabeza.
   • A recorrer la lista con while actual is not None.
   • El precio: llegar al nodo número k cuesta k pistas. Con mil nodos, llegar al último son 999 pistas.
   • El contraste con la lista de Python: nums[999] da el último directamente, pero insert(0, 5) corre a todos.
3. 10

   Tablas hash

   Para buscar en una lista, la recorres uno por uno, o la ordenas primero para usar búsqueda binaria. ¿Y si pudieras calcular en qué lugar está lo que buscas, sin buscarlo? Eso es una tabla hash: una función convierte la clave en un casillero, y guardar y buscar van directo a él.

   aprenderás

   • A construir una función hash sencilla, con ord() para el número de cada letra y % para el resto.
   • A guardar pares clave-valor en una lista de casilleros, con guardar y buscar.
   • Qué es una colisión y cómo se resuelve con una pequeña lista en cada casillero.
   • Por qué roma, amor, mora y ramo caen en la misma casilla con una función hash que solo suma letras.
   • Que el diccionario de Python ({"ana": 25}) es una tabla hash lista para usar.
4. 11

   Árboles (BST y recorridos)

   En la búsqueda binaria descartábamos la mitad de los datos en cada paso, pero necesitábamos una lista ordenada. ¿Y si los datos se guardaran ya organizados para eso, y agregar uno nuevo no moviera nada? Eso es un árbol de búsqueda: cada nodo tiene dos hijos, todo lo de la izquierda es menor, todo lo de la derecha es mayor o igual.

   aprenderás

   • A definir un nodo con dos hijos (izq y der).
   • A insertar y buscar de forma recursiva, descartando una rama en cada comparación: buscar el 60 en un árbol de siete nodos cuesta tres comparaciones.
   • Los tres recorridos: inorden (izquierda, nodo, derecha), preorden (nodo, izquierda, derecha) y postorden (izquierda, derecha, nodo).
   • Por qué el inorden de un árbol de búsqueda siempre sale ordenado.
   • El caso difícil: insertar valores ya ordenados convierte el árbol en una cadena. Con 1.000 valores ordenados, RecursionError.

Tres lecciones para recorrer grafos y encontrar el camino más corto en un mapa con pesos.

1. 12

   Grafos: BFS y DFS

   Un mapa con ciudades y rutas. Quieres visitar todas las ciudades a las que puedes llegar, sin repetir ninguna. Una estrategia visita primero las más cercanas (BFS, nivel por nivel, con una cola). Otra se adentra lo más posible (DFS, hasta el fondo, con una pila o con recursión). Las dos llegan a todas, pero una es la base de los GPS.

   aprenderás

   • A representar un grafo con un diccionario: cada nodo apunta a la lista de sus vecinos.
   • BFS con deque, popleft y un conjunto visitados. Orden desde A: A, B, C, D, E, F.
   • DFS con recursión y el mismo conjunto visitados. Orden desde A: A, B, D, E, F, C.
   • Por qué hace falta el conjunto de visitados: sin él, cualquier ciclo produce un bucle infinito en BFS o un RecursionError en DFS.
   • Que BFS garantiza el camino más corto en número de aristas; DFS, no.
2. 13

   Cola de prioridad (heap)

   Llegan tres personas a urgencias. La primera, con un corte leve. La segunda, con fiebre. La tercera, con un infarto. Si las atiendes por orden de llegada, la del infarto espera. La cola de prioridad no atiende por orden de llegada: atiende primero al más grave. Para que sea rápida, se guarda en un heap: un árbol binario donde el menor está siempre en la raíz.

   aprenderás

   • A usar heapq con heappush, heappop y heapify.
   • A guardar pares (prioridad, tarea) en una tupla, para que Python los compare por prioridad.
   • Que el heap no ordena todo: solo garantiza que el mínimo está accesible. [1, 2, 8, 5] es un heap válido, pero no está ordenado.
   • Que sacar todo con heappop sí da ordenado, pero la ventaja del heap es no ordenar de golpe: solo pagas por lo que usas.
   • La conexión con el camino más corto en un mapa: siempre necesitas expandir el nodo más cercano.
3. 14

   Dijkstra

   Un GPS no elige el camino con menos calles. Elige el más rápido. Y las calles no son iguales: unas son cortas, otras largas, otras están atascadas. Para eso, cada arista tiene un peso. Dijkstra expande siempre el nodo más cercano que aún no ha confirmado, y con un heap sacar el más cercano es rápido.

   aprenderás

   • A representar un grafo con pesos: cada nodo apunta a pares (vecino, peso).
   • El algoritmo de Dijkstra con un diccionario de distancias, un heap de pares (distancia, nodo) y un conjunto de visitados.
   • La relajación: si el camino nuevo es más corto, actualizar la distancia y meter el par en el heap.
   • La traza completa desde A: B 4→3, D 6→4, E 10→7; la distancia más corta a E es 7 (A→C→B→D→E).
   • Por qué el heap es imprescindible: con una cola normal, D se queda en 5 y E en 8 en vez de 4 y 7.
   • El caso difícil: los pesos negativos. Dijkstra da D=2 cuando la respuesta correcta es 1, porque dio B por resuelto y no volvió a mirar sus aristas.