Quicksort es uno algoritmos de ordenación más utilizados en las librerías bases de los lenguajes de programación, por su eficiencia y por su sencillez. Probablemente ya has escuchado o incluso conozcas este algoritmo, sin embargo siempre es bueno repasar lo básico porque, por ejemplo, si estas buscando empleo, es muy probable
que en una entrevista de trabajo, especialmente empresas de EEUU, te pidan implementar Quicksort o te pregunten sobre alguno de los algoritmos básicos de
ordenación o estructuras de datos como los Heaps.
Un poco de historia
Este algoritmo fue
inventado por Tony Hoare a finales de los 60s y también es la base
de otros como Quickselect -creado por el mismo Hoare- sin duda, es muy
interesante y es uno de los métodos de ordenación “Linearítmicos”
más eficientes que existen, sin embargo no siempre garantiza O(nlogn)
en su peor caso la complejidad de este algoritmo es cuadrática, eso
va a depender de la calidad de pivote que se elija. Ha sido muy estudiado, especialmente por Robert Sedgewick y utiliza la técnica de Divide and Conquer.
Descripción del algoritmo
Obviamente esta es una explicación mundana, como
mencioné anteriormente el algoritmo se ha estudiado ampliamente, incluyendo pruebas
matemáticas rigurosas. Sin embargo mi intención es que se pueda
entender de manera fácil. Para una explicación más completa ver la referencia del libro de Sedgewick al final del post o buscar en Wikipedia. Anteriormente escribí sobre el Heapsort que garantizaba O(nlogn) Quicksort es diferente porque la eficiencia del algoritmo va a depender del elemento pivote.
