Cosas que SÍ se dan en Informática (II)

Ordenando longanizas. Segundo capítulo.

Vale. Supongamos que nos hemos leído el primer capítulo. Dado que esto no es como una novela de Dan Brown, sería aconsejable haberlo leído para entender lo que viene ahora, sobretodo si uno no estudió informática (que raro, no estudiar informática).

Tenemos un procedimiento para ordenar vectores que tiene un coste temporal cuadrático O(n²) y ahora queremos otro método mejor, es decir, con un coste menor. O con el mismo coste y que además reproduzca una música linda al terminar.

Una idea consiste en disponer de un procedimiento (función) que calcule el mayor elemento de un vector, para colocarlo al final. Esta función es muy sencilla, recorre los elementos del vector comparando el mayor obtenido con el siguiente elemento. Es decir, almacena el mejor encontrado a cada paso, recorriendo todos los elementos. Esa función tiene por tanto un coste lineal -O(n)-, pues se ha pateado los n elementos. ¿Cuántas veces tenemos que llamara a esa función?. Pues n-1. Cuando todos los mayores elementos - 1 estén en su posición, el primero será el más pequeño. Cada vez que llamamos a la función, por otro lado disminuimos en uno el tamaño del vector, ya que la última posición ya ha sido correctamente ocupada por el mayor elemento que la función obtiene. Esto no nos preocupa cuando calculamos costes, como ya vimos. Por tanto el coste temporal es O(n²)

En resumen, que no hemos obtenido nada mejor de lo que teníamos. Al contrario, es peor, pues no podemos distinguir mediante este procedimiento si el vector está ordenado, así que aquí no hay mejor caso. En cualquier caso es una patata. Por eso es el primero que se aprende.

Imaginemos otra función que, en cambio, sirva para insertar un elemento en un vector ya ordenado. Esta función tiene un coste lineal y es muy sencilla. Para cada elemento, compara con el más grande (que estará a la derecha) y mientras el elemento a insertar sea más pequeño, le hace un hueco desplazando los más grandes a la derecha.
Un ejemplo: quiero insertar un 4 en el vector ordenado 2 7 43. Comparo con 43, como es más grande, muevo el 43 para hacer sitio al 4. Y nos queda esto: 2 7 (hueco) 43. Comparo con el 7, y éste, que es más grande, se aparta educadamente: 2 () 7 43. Pero al comparar con el 2, vemos que éste no se tiene que apartar. Y ha quedado un hermoso hueco donde ponemos el 4: 2 4 7 43.

¡Pero no tenemos un vector ordenado! ¡No queríamos esto!. Wakarimashita. Pero lo construiremos. Y si nos fijamos vemos que siempre hay una pequeña parte del vector ordenado: el primer elemento. El primer elemento es un vector ordenado... de un elemento. Y con nuestra maravillosa función podemos añadir cualquier elemento a este mini vector ordenado. Evidentemente, a no ser que queramos hacer el idiota un rato, los elementos que añadiremos serán los del propio vector desordenado. De este modo, construiremos nuestro vector.

El procedimiento es simple: recorreremos el vector llamando incrementalmente a nuestra función que inserta elementos. Tenemos nuestro glorioso vector 4 7 2 43 14 1. El 4 ya está ordenado... en el vector formado por el 4. Insertamos el 7 en ese vector. Y tenemos el 4 y el 7 ordenados en el vector 4 7. Al vector se apunta el 2, y los otros números le hacen hueco para que ocupe su lugar. Así tenemos 2 4 7. Insertamos el 43, que se queda muy atrás, cómodamente. Insertamos el 14 en 2 4 7 43. Sólo se mueve el 43 para dejarle hueco: 2 4 7 14 43. Por último, insertamos el 1, que obligará a todos los elementos a moverse un poco. Y ya está: 1 2 4 7 14 43.

Si habéis pillado lo del cálculo de costes y tenéis un poco de picardía me diréis: ¡eh! si la función para insertar tiene coste lineal (n) y hay que recorrer n-1 posiciones del vector llamándola, ¡volvemos a tener coste cuadrático!. ¡Chapuzas, más que chapuzas!

Tenéis razón, pero no. La gracia está en que la función para insertar tiene coste lineal... en el peor caso. Es decir, cuando ha de insertar el elemento más pequeño (como cuando insertamos el 1 en nuestro ejemplo). Entonces hay que recorrer todo el vector haciéndole hueco. Pero en promedio no será necesario llegar hasta el final. Cuando hemos insertado el 7 o el 43, la función ha tenido coste constante. y cuando hemos insertado el 14, sólo hemos recorrido un elemento. Al igual que el Bubble Sort, distinguimos entre un mejor caso (vector ordenado, coste O(n)) y un peor caso, coste (O(n²)).

Este algoritmo un mejor comportamiento que Bubble Sort, porque aprovecha el orden parcial en el que se encuentre el vector y no debe esperar a que se encuentre completamente ordenado como éste para obtener beneficios. ¿Cómo medimos lo que tarda el algoritmo en el caso medio, por otro lado?. Pues hemos de contar el número de veces que hemos tenido que "dejar hueco". A esto se le llaman inversiones. El dos ha realizado dos inversiones, puesto que antes estaba 2 posiciones más allá del 4 y el 7. Estos no han realizado ninguna, claro está. El cálculo absoluto es difícil de hacer, pero para eso están las notaciones. Decimos que en caso medio, el algoritmo cuesta O(n+d), donde d es el número de inversiones, una medida de lo (des)ordenado que está el vector.

Por supuesto, este genial procedimiento no lo ha inventado Aitor Menta, así que ya tenía nombre: Insertion Sort.

¿Nos quedamos con este algoritmo tan maravilloso?. Pues no, porque no nos vale. Para jugar con pocos elementos está bien, pero no podemos permitirnos un coste cuadrático cuando tratamos con cantidades realmente grandes. ¿Saben lo que hace una función n² con datos grandes?.

¿Existe alguna función que nos ayude a ordenar vectores con coste inferior a Insertion Sort? La respuesta (afirmativa) a tan interesante cuestión será dilucidada en el siguiente -y último de la serie- capítulo de: ¡Ordenando Longanizas!