Básicos: Algoritmos

Un programa es, básicamente, la representación de un algoritmo en código; un algoritmo es una serie de pasos que se realizan para obtener un resultado. Hay tres características principales:

• Resultado: El propósito es, precisamente, hacer algo…
• Orden: No podemos cocinar la torta antes de mezclar los ingredientes.
• Fin: En algún momento tiene que terminar. Un bucle infinito no sirve para nada.

Casi siempre existe más de un algoritmo para resolver la misma tarea. Por ejemplo, los algoritmos de ordenamiento: Dada una lista de elementos (por lo general son números en los ejemplos, pero se puede ordenar cualquier cosa que se pueda comparar como mayor/menor/igual que), devolver los elementos en orden.

Uno de los más simples es el llamado “Burbuja”:

Dada una lista L[1..n] de n elementos desordenados, recorrerla comparando cada par de elemento L[i] y L[i+1]; si L[i] > L[i+1], intercambiarlos. Si se hizo un cambio, repetir.

El algoritmo es simple y llega a un resultado ordenado, pero tiene un problema:

Por ejemplo, la lista L = [3,4,2,1]:

1. Primera pasada:
   1. 3
   2. 4 > 2: intercambiar. L = [3, 2, 4, 1]
   3. 4 > 1: intercambiar. L = [3, 2, 1, 4]
2. Segunda pasada:
   1. 3 > 2: intercambiar. L = [2, 3, 1, 4]
   2. 3 > 1: intercambiar. L = [2, 1, 3, 4]
   3. 3
3. Tercera pasada:
   1. 2 > 1: intercambiar. L = [1, 2, 3, 4]
   2. 2
   3. 3
4. Cuarta pasada (comprobación):
   1. Nada cambia.

Lista devuelta: [1, 2, 3, 4].

El problema del algoritmo: la velocidad. En el mejor de los casos (la lista está ordenada), es necesario hacer n-1 comparaciones. En el peor, n²-n (n pasadas de n-1 comparaciones). Para números chicos, no pasa nada, pero en una lista medianamente grande, digamos, 1000 elementos, son 999000 pasadas.

Se puede arreglar un poco: en cada pasada, el elemento más grande se va al final (pruebenlo todas las veces que quieran), así que no es necesario comparar los dos últimos elementos (entonces cada recorrido hacemos n, n-1, n-2, …, 3, 2, 1 comparaciones). La cantidad de pasadas total entonces se hace igual a la suma de todos los números entre 1 y n-1 (inclusive): n²/2. Sigue siendo medio millón.

Claro que, así como este algoritmo es lentísimo, ocupa muy poca memoria; al elegir un algoritmo se tienen que comparar todas las ventajas y desventajas que tenga.