CSI III: Ordenando longanizas (y 3)

Aprovecho para indicar que CSI significa Cosas que SÍ se dan en Informática, que, para quien no lo sepa, es una serie de cosas que se estudian en la carrera de Ingeniero Informático según el plan de estudios aprobado en les Corts que correspondan.

Vale, tras los posts 1 y 2 de la serie Ordenando Longanizas, tenemos algoritmos (formas de hacer cosas) para ordenar un vector. Todos tienen coste cuadrático en el peor caso, lo cual implica que, a malas y con un conjunto de datos muy grande, tendremos que inventar alguna excusa creíble (la red, un virus, el Windows...) para justificar el cuelgue. En eso somos muy buenos, los informáticos.

Afortunadamente, existen métodos mejores para ordenar vectores. Afortunadamente digo, porque los inventó gente bastante más lista que tú y que yo. Cuando se recuerda al autor de un algoritmo, entonces es que es muy bueno. Y uno de los más buenos es:

El Quicksort, de Sir Richard Hoare

En 1960 este señor inventó una técnica para ordenar vectores que, tras muchas aportaciones, se ha convertido en una de las más populares y eficaces para ordenar vectores. La idea es la siguiente: seleccionaré un elemento cualquiera del vector (pivote) y situaré los elementos más pequeños que él a su izquierda y los más grandes a su derecha. Cuando esto suceda, el pivote estará en su posición final.

Vale, eso es fácil de decir. ¿Cómo situamos a la derecha y a la izquierda para todos los elementos?. Bueno, pues sencillamente intercambiaremos los elementos mayores que el pivote que estén a la derecha (descolocados) con los menores que el pivote que estén a la izquierda (descolocados). Vamos recorriendo por ambos lados el vector y cuando nos crucemos... ahí colocaremos el pivote. En total sólo tenemos que recorrer la longitud del vector para obtener la posición de un elemento (como los trenes que al chocar suman la distancia que les separaba).

A ver 4 7 2 43 14 1. Suponed que cogemos el 4 como pivote. Empezamos a ver si tenemos que intercambiar por los extremos. Como 7 es mayor que el pivote y el 1 menor, los intercambio, hop: 1 2 43 14 7. Seguimos: como el 2 no es mayor que el 4 avanzo el indice y miro el 43. Lo señalo y busco elementos menores que 4 desde atrás: 14, no, 43, no, 2... un momento: ¡me he pasado!. Eso quiere decir que ya estoy señalando el lugar correcto donde insertar el pivote. Lo pongo donde señala el 2. Diréis: lo más listo sería ponerlo donde el 43. Sí, pero los algoritmos no son listos: hacen lo que tienen programado y ya. Como hemos intercambiado, tenemos algo como 2 1 4 43 14 7.

Y ahora viene lo bueno. El 4 está ordenado. Lo que no lo está son las 2 subvectores que tiene a cada lado. Para ordenarlas... aplicaremos el mismo algoritmo a cada una de ellas. La lista 2 1, el pivote es el 2 y hay que cambiar con el 1. Por tanto intercambio 2 con el 1. ¡La única dificultad consiste en saber cuándo parar de hacer esto!.

Por cierto que esto que hemos hecho (utilizar la función dentro de la misma función) se llama llamada recursiva. Al principio de programar no es sencillo pensar en funciones recursivas pero una vez las conocemos, resulta difícil no hacer uso de ellas.

Así que Quicksort funciona así: intercambia los elementos descolocados en relación al pivote y finalmente sitúa el mismo en su posición final de la lista. Luego utiliza el mismo algoritmo para ordenar los dos (o uno) subvectores que quedan a los lados del pivote.

¿Y cuánto cuesta esto?. Supongamos que, en el mejor caso, el pivote escogido resulta quedar en el medio del vector, partiendo el mismo en dos mitades equilibradas. Sabemos que entonces hay 1 elemento ordenado. Las siguientes llamadas a Quicksort hacen lo mismo, de modo que tras ellas, el vector queda dividido en cuatro partes equilibradas: en ese momento hay 3 elementos ordenados. Luego en 8, 16... . En fin que estamos calculando potencias de 2, que nos permiten ordenar tantos elementos -1. Razonando de forma inversa, si tenemos n elementos a ordenar, ¿cuántas veces hemos de aplicar este algoritmo?: pues los que nos enseñaron que era "el contrario" de la potencia: log(n).

Podemos imaginar este proceso en forma de árbol. En el primer nivel ordenamos el primer pivote y llamamos a las funciones para ordenar los elementos que quedan a la izquierda y a la derecha. Estas llamadas forman parte del segundo nivel, que ordenan otros dos elementos. El tercer nivel ordena cuatro más... Como las cantidades crecen muy rápido, el número de datos que podemos ordenar también lo hace sin más que aumentar un poco la altura del árbol. Por eso son tan buenos los algoritmos de costes logarítmico.

En cada nivel, las distintas llamadas sólo tratan partes disjuntas del vector original, de tamaño n. Ya sabemos que en cada una de ellas el coste de colocar un elemento en su posición es lineal con orden del tamaño del vector. Como las partes del vector en cada nivel suman n, el coste de cada nivel es O(n). Como tenemos log(n) niveles, el coste total del Quicksort en su mejor caso es O(nlog(n)).

¡Pero eso no nos vale!. ¿Qué pasa en el peor caso?. Pues que tenemos la mala pata de elegir siempre un pivote que resulta ser el mayor o el menor elemento de los que tenemos que ordenar. De modo que siempre perdemos una de las ramas del árbol y resulta que tenemos llamar n veces a una función que tarda O(n) en ejecutarse:. Total O(n²). Sucedería si siempre escogiésemos como pivote el primer elemento en un vector ordenado. Hay formas muy sencillas de evitar esto, escoger como pivote el mediano de tres elementos, o escogerlo simplemente al azar.

Pero ya sabemos un poco más y nos preguntamos: ¿qué sucede en el caso medio?. Pues que, aunque la elección del pivote separe de forma descompensada el resto de elementos, el coste sigue teniendo una forma logarítmica. Supongamos un caso mínimamente mejor que el peor caso: sólo dejando dos elementos a ordenar en un lado en cada partición. En ese caso la altura del árbol se reduce a la mitad y por tanto, el coste es la mitad que el del peor caso. La altura del árbol se reduce mucho con poco que equilibremos las ramas

Resultado final: mejor caso O(nlog(n)), peor caso (evitable) O(n²), caso medio O(nlog(n)). Por cierto no hay ningún algoritmo que ordene un vector con coste teórico inferior a O(nlog(n)). Los hay que tienen mejor coste en circunstancias muy especiales, los hay que arrojan mejores resultados experimentales que el Quicksort en el caso medio, los hay cuyo peor caso es mejor... Pero si usted descubre algún método de ordenar longanizas con un coste teórico menor... no se lo cuente a nadie y envíelo a Aitor Menta para que, amablemente, lo publique verifique.

Posts relacionados

Ordenando longanizas I
Ordenando longanizas II