El Algoritmo Quicksort

El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenacion creado por el científico británico en computación C. A. R. Hoare.

En la ordenación por fusión se pone el énfasis en cómo combinar los subproblemas resueltos, mientras que la operación de descomponer en subproblemas es trivial. Sin embargo, si al descomponer el vector, los elementos del primer subvector fueran todos menores o iguales que los del segundo subvector, no habría que realizar ninguna operación de combinación. En este caso, la descomposición es algo más compleja, pero la combinación es trivial.

Esta es la idea que subyace al algoritmo quicksort, que realiza el siguiente proceso:

• Toma un elemento cualquiera del vector denominado pivote.
• Toma los valores del vector que son menores o iguales que el pivote y forma un subvector. Se procede análogamente con los valores mayores.
• Se invoca recursivamente al algoritmo para cada subvector.

Para realizar la descomposición, se suele elegir como pivote el primer elemento del vector. Para almacenar los subvectores, se puede usar el propio vector situando los menores que el pivote a su izquierda, y los mayores a su derecha. Una forma eficiente de realizar este proceso es comenzando a recorrer el vector por ambos extremos. En el recorrido de izquierda a derecha, nos detenemos cuando se encuentre un elemento mayor que el pivote. En el recorrido de derecha izquierda, nos detenemos al encontrar un elemento menor o igual que el pivote. Entonces se intercambian ambos elementos, y se prosigue el recorrido. Cuando los recorridos se cruzan, el vector está descompuesto satisfactoriamente:

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es \(O(n·log n)\).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de \(O(n^2)\). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• En el caso promedio, el orden es \(O(n·log n)\).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

A continuación se muestra un ejemplo de su funcionamiento:

En el apartado de visualización podrás conocer su funcionamiento. Introduce los elementos del vector separados por comas y pulsa ACTUALIZAR. A continuación podrás visualizar el avance del algoritmo y de las estructuras de datos utilizando los botones de control de la parte superior.