Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. El método Quick Sort es actualmente el más eficiente y veloz de los método de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamento por partición. También, este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort, por la velocidad con la que ordena los elementos del arreglo.
Historia
El algoritmo Quicksort fue desarrollado en el año 1960 por Charles Antony Richard Hoare mientras se encontraba en la Unión Soviética, en la Universidad Estatal de Moscú.
Desarrolló el algoritmo para poder ordenar las palabras a ser traducidas, para volverlas más fácil de coincidir con un diccionario ya ordenado de ruso a inglés.
El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
Descripción del algoritmo
El algoritmo consta de los siguientes pasos:
-
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
-
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
-
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
-
Repetir este proceso de forma recursiva para cada sublista mientras estas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Características
-
Es el algoritmo de ordenación más rápido (en la práctica) conocido. Su tiempo de ejecución promedio es O(N log(N)).
-
Para el peor caso tiene un tiempo O(N), pero si se codifica correctamente las situaciones en las que sucede el peor caso pueden hacerse altamente improbables.
-
En la práctica, el hecho de que sea más rápido que los demás algoritmos de ordenación con el mismo tiempo promedio O(N log(N)) está dado por un ciclo interno muy ajustado (pocas operaciones).
-
Al igual que el algoritmo de ordenación por intercalación, el algoritmo de ordenación rápida es fruto de la técnica de resolución de algoritmos "divide y vencerás". Como ya se explicó, la técnica de divide y vencerás se basa en, en cada recursión, dividir el problema en subproblemas más pequeños, resolverlos cada uno por separado (aplicando la misma técnica) y unir las soluciones.
Ventajas del algoritmo Quicksort
-
Muy rápido
-
No requiere memoria adicional
Ventajas del algoritmo Quicksort
-
Implementación un poco más complicada
-
Recursividad (Utiliza muchos recursos)
-
Depende de una selección de pivote buena para garantizar O (n log n)
Referencias
QuickSort - EcuRed. (s. f.). EcuRed. https://www.ecured.cu/QuickSort
Weiss, M. A., & Moreno, J. L. (1995). Estructuras de datos y algoritmos. Addison Wesley Iberoamericana.
Vista general del ordenamiento rápido (artículo). (s. f.). Khan Academy. https://es.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort