Nuestro primer algoritmo

"La Máquina Analítica teje patrones algebraicos del mismo modo que el telar Jacquard teje flores y hojas" escribía Ada Lovelace en 1842, en lo que hoy en día sería una publicación científica (o paper) llamado “Sketch of the Analytical Engine invented by Charles Babbage ”.

Ella no sólo tradujo al inglés este trabajo tan importante para nuestra época sino que agregó demostraciones, notas y comentarios, haciendo que la publicación pase a tener casi el doble de la extensión que la original.

En este trabajo explicaba cómo debía funcionar la Máquina Analítica, la primera formulación teórica de lo que hoy es una computadora. Y agrega algo muy importante: un ejemplo.

En una de sus cartas a Babbage ella dice “quiero agregar algo acerca de los números de Bernoulli en una de mis notas, como un ejemplo de cómo una función implícita puede ser resuelta por la máquina sin haber sido calculada primero por una persona ”.

Los números de Bernoulli eran importantes para la época y se usaban para estudiar las propiedades de las sumas de potencias de números. Desde 1600 la gente calculaba estas potencias de números y las escribía en tablas para poder hacer las cuentas que necesitaban.

Este ejemplo, en el que Ada explica cómo la máquina haría el cálculo, es lo que se considera el primer algoritmo de la historia. Posteriormente, este algoritmo que Ada creó fue llevado a la práctica, la máquina se construyó y program de Ada pudo ejecutarse por primera vez.

Por esta razón se considera a Ada como la primera programadora de la historia.

Hoy, 175 años más tarde y rodeados de tecnología, hablamos de programas y algoritmos todo el tiempo.

El libro “Introducción a los algoritmos” de Thomas H. Cormen (un viejo conocido para cualquiera que haya estudiado algo relacionado con sistemas) nos dice “Informalmente, un algoritmo es cualquier procedimiento computacional bien definido que tome algún valor, o conjunto de valores como entrada y produce algún valor, o conjunto de valores, como salida. Un algoritmo es, por lo tanto, una secuencia de pasos computacionales que transforma el entrada en la salida”.

Básicamente un algoritmo es una solución a un problema que se automatiza, un conjunto de instrucciones u órdenes que una computadora puede ejecutar.

Pese a tener esta noción de que los algoritmos y los programas están presentes en nuestra vida, pocos de nosotros entendemos concretamente qué es un algoritmo. Cómo hizo Ada, creo que la mejor manera de entender esto es a través de un ejemplo.

Imaginemos que trabajamos en una biblioteca y llega un cargamento de 500 libros. Queremos que los libros están ordenados de forma alfabética en los estantes, para encontrarlos más fácil. Tenemos que ordenar los 500 libros de nuestro inventario. ¿Cómo hacemos?

¡Vamos con una primera versión de este algoritmo!

Primer Algoritmo: Selection Sort

Esta primera versión de nuestro algoritmo consiste en buscar siempre el libro que debería ir adelante en los estantes: Miramos en orden cada uno de los libros y cuando vemos uno que creemos que es que debería ir primero (por ejemplo empieza con A) lo agarramos. Este libro que tenemos en la mano es nuestro “mínimo” hasta el momento. Seguimos mirando los demás libros y si encontramos uno que debería ir antes agarramos ese nuevo libro y dejamos el que teníamos en la mesa. Seguimos mirando el resto de los libros y si llegamos al final de los 500, entonces significa que el que tenemos en la mano es efectivamente el primero de todos (porque ya lo comparamos con todos) y lo colocamos en el primer estante. Volvemos a repetir lo mismo para todos los otros libros hasta que terminamos y ¡listo!

Imaginando que nos cuesta 1 segundo hacer cada una de las comparaciones entre títulos, la primera pasada buscando el primero nos cuesta 500 segundos (porque tenemos que comparar 500 libros), la segunda pasada tenemos que mirar 499 porque uno ya está ubicado en el estante, la tercera pasada 498 segundos y así sucesivamente. Si sumamos todas estas pasadas nos dá un total de 125.250 segundos. ¡Casi 34 horas para ordenar 500 libros! Un día y medio.

¿Por qué es tan lento? Porque estamos haciendo muchas comparaciones de más.

Segundo Algoritmo: Bucket Sort

Les voy a otro algoritmo mucho más rápido para ordenar, que nos va a permitir hacerlo en poco más que una hora y media en vez de más de un día!

El truco es evitar las comparaciones innecesarias. Para eso, y aprovechando que la primera letra de cada uno de los títulos tiene que ser una letra de nuestro alfabeto, y solo hay 27 letras posibles lo que podemos hacer es una pasada para poner los libros en 27 pilas distintas, de acuerdo a la primera letra del título.

Esto nos ahorra muchas comparaciones, ya sabemos que todos los que empiezan con A van a estar antes de los que empiezan con B y así sucesivamente.

A partir de acá, y asumiendo que hay masomenos la misma cantidad de títulos empezando con cada letra, nos quedan 20 libros en cada pila aproximadamente. Al ser sólamente 20 podemos usar la misma técnica anterior (selection sort) para ordenar cada una de las pilas ya que ordenar cada pila nos cuesta solamente 210 segundos (20+19+18+17+..+1).

Haciendo las cuentas 500 segundos (primera pasada) más 27 veces (ordenar cada pila) 210 segundos nos dá una hora y media de trabajo.

Otros algoritmos

Hay muchos otros algoritmos para ordenar, cada una se ajusta mejor a una situación diferente y lo divertido de programar es encontrar la mejor solución a cada problema: cómo se puede ejecutar la tarea que tenemos que hacer más eficientemente.

¡Si llegaste hasta acá leyendo es que esto te interesó bastante! Te dejo este video con otras formas de ordenar nuestra biblioteca que seguro te va a gustar:

Conforme a los criterios de

Conocé más