En una entrada anterior prometí hablar de los casos en los que tiene sentido usar tu propia implementación de un algoritmo de ordenación. Hablaré de ello, pero antes quiero hacer un inciso para ilustrar hasta qué punto se pueden torcer las cosas.

Cuando digo «fallar horriblemente» no me refiero al caso de «no conseguir que funcione» sino al caso de «conseguir que funcione… hasta que un día falla». Esto último es mucho peor.

Ignorar la letra pequeña es un error. Coger un libro sobre algoritmos e implementar tu propia versión del algoritmo X sin leer el capítulo completo puede ser una metedura de pata tremenda.

Veamos, como caso práctico, los errores comunes al implementar quicksort:

1. Dejar el pivote dentro de una de las partes (posible recursividad infinita).
2. Usar siempre el primer elemento como pivote (o siempre el último).
3. Creer que usar como pivote la mediana de 3 o un elemento al azar evita completamente el peor caso.
4. Hacer dos llamadas recursivas en vez de utilizar recursividad de cola.
5. Utilizar recursividad de cola, pero siempre en el mismo lado.
6. Creer que la recursividad de cola evita todos los problemas. Reduce la memoria requerida en el peor caso, pero no el tiempo.
7. Dejar todos los elementos iguales al pivote en un lado. Si se hace esto, quicksort mostrará su peor comportamiento también en el caso de que todos (o muchos) valores sean iguales.

Explicaré uno a uno los puntos anteriores:

1. Dejar el pivote dentro de una de las partes

Al hacer la partición conviene que el elemento elegido como pivote quede ya en su sitio, y no dentro de una de las partes a ordenar. Puede parecer una pequeña optimización sin importancia, pero no lo es.

Si dejamos el pivote dentro de una de las partes a ordenar, y además ocurre que esa parte ocupa todo el array a ordenar (quedando la otra parte vacía), entonces se provoca una recursividad infinita.

Hay varios detalles que modifican el impacto de este problema, como la forma de elegir el pivote o si los valores iguales al pivote se reparten o se dejan en un lado. No obstante, la única manera de resolver este problema al cien por cien es excluir al pivote de ambas partes, dejándolo situado en su posición definitiva. Así se garantiza que cada llamada recursiva reduzca el tamaño del problema en al menos un elemento.

2. Usar siempre el primer elemento como pivote (o siempre el último)

Esto no tendría importancia si todas las permutaciones posibles se dieran con la misma probabilidad. Pero la realidad es diferente. Los casos especiales de «datos ya ordenados» (al derecho o al revés) o «datos casi ordenados» son bastante frecuentes en comparación con otras permutaciones. Y en esos casos, el primer elemento y el último son los peores candidatos para la elección del pivote.

Si usamos siempre el primer elemento (o siempre el último) como pivote, quicksort degenera en su peor comportamiento con datos ya ordenados, tanto si están en orden ascendente como si están en orden descendente.

Este problema se suele resolver de dos maneras diferentes:

• Usar como pivote la mediana tres elementos: el primero, el último y el central
• Usar como pivote el elemento de una posición escogida al azar

Ambos métodos reducen la probabilidad de que se dé el peor caso, pero no la eliminan completamente.

3. Creer que usar como pivote la mediana de 3 o un elemento al azar evita completamente el peor caso

El peor caso aún puede darse. Puede que sea muy improbable, pero sigue siendo posible. Este es el tipo de problema que no se detecta en las pruebas y que se puede manifestar más tarde, cuando las consecuencias son más graves.

No es sólo una cuestión de probabilidad. Un atacante que pueda introducir datos en nuestro sistema podría disponerlos justamente de forma que provoquen el peor comportamiento de quicksort.

Debemos tener en cuenta que el peor caso puede darse. Conviene que las pruebas lo ejerciten para evaluar las consecuencias en cuanto al tiempo requerido y la memoria adicional utilizada.

4. Hacer dos llamadas recursivas en vez de utilizar recursividad de cola

La recursividad de cola se implementa sustituyendo una de las llamadas recursivas por un bucle. De esta forma se reduce ligeramente el tiempo de ejecución.

Parece una simple optimización, pero en realidad es imprescindible para que la memoria adicional requerida sea O(log N) incluso en el peor caso. Aún así, no basta simplemente con usar recursividad de cola de cualquier manera. A continuación explico por qué.

5. Utilizar recursividad de cola, pero siempre en el mismo lado

Si no se usa recursividad de cola, o si se usa siempre en el mismo lado, el espacio de memoria adicional requerido en el peor caso será del orden de O(N), es decir, proporcional al número de elementos a ordenar. Eso puede provocar un desbordamiento de pila.

La razón es que en el peor caso se llegarán a anidar hasta O(N) llamadas recursivas y cada una de ellas ocupa algo de memoria.

Lá única manera de resolver esto pasa por usar recursividad de cola en la llamada correspondiente a la parte más grande. Así se asegura que sólo se anidarán O(log N) llamadas recursivas.

6. Creer que la recursividad de cola evita todos los problemas

La recursividad de cola, usada correctamente, resuelve el problema del espacio. Pero siguen existiendo otros problemas. El tiempo del peor caso sigue siendo O(N²) . Como ya he comentado, la forma de elegir el pivote puede ayudar a que este caso sea poco probable en la práctica. Si «poco probable» no es suficiente, entonces hay que recurrir a algún otro algoritmo que tarde O(N log N) también en el peor caso, aunque en el caso medio tarde varias veces más que quicksort.

Pero aquí no acaba la cosa. Queda un sutil detalle que puede convertir ese «poco probable» en «vergonzosamente frecuente»:

7. Dejar todos los elementos iguales al pivote en un lado

Al hacer la partición, ¿qué hay que hacer con los elementos que resultan ser iguales que el pivote? A simple vista parece un detalle sin importancia. Podemos dejarlos en cualquiera de los dos lados. El algoritmo ordenará correctamente. Además, no habrá muchos elementos iguales al pivote, ¿verdad? ¡Oh! Un momento…. ¡A lo mejor hay muchos!

Cuando hablamos de algoritmos de ordenación tendemos a pensar en valores distintos entre sí, pero en la vida real ocurre con bastante frecuencia que muchos elementos tienen un mismo valor. Supongamos que hay que ordenar los datos de 47 millones de habitantes según su estado civil (soltero/a, casado/a…). Tras un par de niveles de recursividad es posible que todos o casi todos los elementos del fragmento a ordenar sean iguales entre sí en lo que respecta al estado civil. ¿Qué pasará entonces?

La probabilidad de que el pivote elegido tenga ese valor es altísima, así que habrá muchos elementos iguales al pivote. Si los ponemos todos al mismo lado haremos una partición ineficiente. ¡La peor de todas las posibles! Quicksort exhibirá su peor comportamiento en un caso que, en principio, parecía absurdamente fácil. Este es seguramente el mayor problema porque los libros de algoritmos no hacen suficiente hincapié en él, si es que lo mencionan.

La solución es repartir equitativamente los elementos iguales al pivote entre las dos partes, aunque a primera vista parezca que movemos los datos innecesariamente. Podéis encontrar una implementación aquí.

En cualquier caso insisto: la mejor opción es casi siempre usar el método de ordenación que proporciona el propio lenguaje de programación en su biblioteca de funciones ;-)