20.3. Ordenamiento rápido o Quick sort

Veremos ahora el más famoso de los algoritmos recursivos de ordenamiento. Su fama radica en que en la práctica, con casos reales, es uno de los algoritmos más eficientes para ordenar. Este método se basa en la siguiente idea:

1. Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. De lo contrario hacer lo siguiente:
2. Tomar un elemento de la lista (por ejemplo el primero) al que llamaremos pivote y armar a partir de esa lista tres sublistas: la de todos los elementos de la lista menores al pivote, la formada sólo por el pivote, y la de los elementos mayores o iguales al pivote, pero sin contarlo al pivote.
3. Ordenar cada una de esas tres sublistas (usando este mismo método).
4. Concatenar las tres sublistas ya ordenadas.

Por ejemplo, si la lista original es [6, 7, -1, 0, 5, 2, 3, 8] consideramos que el pivote es el primer elemento (el 6) y armamos las sublistas [-1, 0, 5, 2, 3], [6] y [7,8]. Se ordenan recursivamente [-1, 0, 5, 2, 3] (obtenemos [-1, 0, 2, 3, 5]) y [7, 8] (obtenemos la misma) y concatenamos en el orden adecuado, y así obtenemos [-1, 0, 2, 3, 5, 6, 7, 8].

Para diseñar, vemos que lo más importante es conseguir armar las tres listas en las que se parte la lista original. Para eso definiremos una función auxiliar _partition que recibe una lista no vacía y devuelve las tres sublistas menores, medio y mayores (incluye los iguales, de haberlos) en las que se parte la lista original usando como pivote al primer elemento.

Contando con la función _partition, el diseño del Quick sort es muy simple:

1. Si lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. Se devuelve lista tal cual.
2. De lo contrario:
   • Dividir la lista en tres, usando _partition.
   • Llamar a quick_sort(menores), quick_sort(mayores), y concatenarlo con medio en el medio.

Por otro lado, en cuanto a la función _partition(lista):

1. Tiene como precondición que la lista es no vacía.
2. Se elige el primer elemento como pivote.
3. Se inicializan como vacías las listas menores y mayores.
4. Para cada elemento de la lista después del primero:
   • Si es menor que el pivote, se lo agrega a menores.
   • De lo contrario, se lo a agrega a mayores.
5. Devolver menores, [pivote], mayores

Una primera aproximación a este código se puede ver en el código 20.2.