Origenes
Quicksort fue publicado en el año de 1962 por sir Tony Hoare. Su primer trabajo en un nuevo empleo, fue el de implementar un algoritmo de ordenamiento, basado en el mejor algoritmo de este tipo, hasta entonces conocido(Shell sort). Sir Tony Hoare, aposto con su jefe a que el podía mejorarlo. Quicksort fue el resultado.
Hoy en día sigue siendo uno de los algoritmos más utilizados y uno de los más eficientes, salvo en algunas excepciones.
Ventajas y desventajas del algoritmo
Quicksort, es uno de los algoritmos de ordenamiento mas rapido que se conoce. Sin embargo, la diferencia entre el mejor de los casos y el peor de los casos es muy notable.
El peor caso ocurre cuando el arreglo ya está ordenada, porque cada llamada genera sólo un subarreglo (todos los elementos son menores que el elemento de división). En este caso el rendimiento se degrada a O(n2).
Quicksort suele considerarse muy elegante, siendo incluso el motivo del libro del autor y programador Greg Wilson, titulado “Beautiful Code”.
Una de sus desventajas, es que es un poco mas difícil de implementar que los algoritmos promedio. A pesar de esto, debido a su alta eficiencia, quicksort sigue siendo el algoritmo de ordenamiento mas popular.
Tiempo de ejecucion
Se puede probar el tiempo de ejecucion de quicksort en el mejor de los casos de la siguiente manera
Vamos a suponer que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. de aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n)
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). 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 arreglo y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
