Quicksort es un algoritmo de ordenación que utiliza el principio de divide y vencerás, fue desarrollado por Antony R. Hoare en 1.959. Tiene 
una complejidad promedio de O(n log n) y es uno de los algoritmos más utilizados para grandes volúmenes de datos, aunque no es el más rápido.
| Rendimiento – Complejidad | |||
| Mejor caso Ω | Peor caso O | Media Θ | Espacio |
| (n log n) | (n²) | (n log n) | O(log n) |
El proceso es el siguiente:
- Del vector de entrada se elige uno de sus elementos (eje) que dividirá al vector en dos sub-vectores, uno de ellos con elementos menores que el eje y otra con elementos mayores o iguales.
- Después de elegir el eje se ordenan todos los elementos alrededor del mismo, por un lado los de valor más pequeño antes que él y los mayores detrás de él.
- Los pasos anteriores se aplican a cada uno de los sub-vectores de forma recursiva
- Todos los sub-vectores se combinan para formar el vector ordenado.
A tener en cuenta:
El eslabón más débil del algoritmo es la elección del eje. ¿Cómo elegimos el mejor eje?, difícil en un vector desordenado. El elemento de valor intermedio sería el mejor, pero encontrarlo es costoso, entonces debemos tomar alguna de estas opciones:
- El primer elemento del vector
- El último elemento
- La mediana
- Cualquier otro elemento aleatorio.
Nicklaus Wirth propuso superar este problema con el principio de “la mediana de tres”, es decir, como elemento clave del sub-vector se toma el elemento promedio de: el primero, el último y el elemento en el medio.
Si la estrategia es elegir el elemento en una posición fija (primero, último, en el medio) será ineficiente en vectores ordenados parcialmente, como alternativa podemos seleccionar la mediana. En el último caso necesitaremos un generador seudoaleatorio.
Respecto de la complejidad:
- El mejor caso. La división inicial nos dará dos sub-vectores de igual tamaño, por lo tanto, la primera iteración del vector completo de tamaño n necesita O (n). La ordenación de los dos sub-vectores restantes con n / 2 elementos toma la forma 2 * O (n / 2) para cada uno, por tanto O (n log n) .
- El peor caso. El algoritmo selecciona solo un elemento en cada iteración, por lo que O (n) + O (n-1) +… + O (1) , es igual a O (n 2 ) .
- En promedio nos da una complejidad O (n log n).
Ejemplos.
Ejemplo con el Vector = {6, 11, 5, 7, 6, 2}
- Tomamos el 6 como eje (existen dos, elegimos el primero).
- Ponemos todos los elementos menores al 6 en las primeras posiciones del vector {2, 5, 6, 7, 6, 11}
- Se repite el proceso en el sub-vector izquierdo {2,5}, tomamos el 2 como eje y solo nos queda a la derecha del eje,el 5. El sub-vector ordenado es {2,5}
- Realizamos la misma operación para el sub-vector derecho, {7, 6, 11}, obteniendo {6, 7, 11}
- Unimos sub-vector izquierdo {2,5} + eje 6 + sub-vector derecho {6, 7, 11} = {2, 5, 6, 6, 7, 11}.
El algoritmo programado en Java.
El siguiente ejemplo utiliza el mismo algoritmo base, pero con el añadido de la división de los datos a procesar y lanzamiento del algoritmo por cada una de las divisiones. Existen distintas formas de lanzar (dividir) la ordenación, aquí la más fácil, pero recomiendo la utilización de Hilo.join() para mayores divisiones (también fácil).
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.
Monoprocesador.
Multi-hilo.
