Quicksort es un algoritmo de ordenamiento eficiente y de uso general . Quicksort fue desarrollado por el informático británico Tony Hoare en 1959 [1] y publicado en 1961. [2] Sigue siendo un algoritmo de ordenamiento de uso común. En general, es ligeramente más rápido que el ordenamiento por fusión y el ordenamiento por montículos para datos aleatorios, en particular en distribuciones más grandes. [3]
Quicksort es un algoritmo de divide y vencerás . Funciona seleccionando un elemento "pivote" de la matriz y dividiendo los otros elementos en dos submatrices, según sean menores o mayores que el pivote. Por este motivo, a veces se lo denomina ordenación por intercambio de particiones . [4] Las submatrices se ordenan luego de forma recursiva . Esto se puede hacer en el lugar , requiriendo pequeñas cantidades adicionales de memoria para realizar la ordenación.
Quicksort es un ordenamiento por comparación , lo que significa que puede ordenar elementos de cualquier tipo para el que se defina una relación "menor que" (formalmente, un orden total ). Es un ordenamiento basado en comparación, ya que los elementos a y b solo se intercambian en caso de que su orden relativo se haya obtenido en el cierre transitivo de resultados de comparación anteriores. La mayoría de las implementaciones de quicksort no son estables , lo que significa que el orden relativo de elementos de ordenamiento iguales no se conserva.
El análisis matemático de quicksort muestra que, en promedio , el algoritmo realiza comparaciones para ordenar n elementos. En el peor de los casos , realiza comparaciones.
El algoritmo quicksort fue desarrollado en 1959 por Tony Hoare mientras era estudiante visitante en la Universidad Estatal de Moscú . En ese momento, Hoare estaba trabajando en un proyecto de traducción automática para el Laboratorio Nacional de Física . Como parte del proceso de traducción, necesitaba ordenar las palabras en oraciones rusas antes de buscarlas en un diccionario ruso-inglés, que estaba en orden alfabético en cinta magnética . [5] Después de reconocer que su primera idea, la ordenación por inserción , sería lenta, se le ocurrió una nueva idea. Escribió la parte de partición en Mercury Autocode, pero tuvo problemas para lidiar con la lista de segmentos sin ordenar. A su regreso a Inglaterra, se le pidió que escribiera el código para Shellsort . Hoare le mencionó a su jefe que conocía un algoritmo más rápido y su jefe apostó seis peniques a que no lo conocía. Su jefe finalmente aceptó que había perdido la apuesta. Hoare publicó un artículo sobre su algoritmo en The Computer Journal Volumen 5, Número 1, 1962, Páginas 10-16. Más tarde, Hoare aprendió sobre ALGOL y su capacidad para hacer recursión que le permitió publicar una versión mejorada del algoritmo en ALGOL en Communications of the Association for Computing Machinery , la principal revista de informática de la época. [2] [6] El código ALGOL se publica en Communications of the ACM (CACM), Volumen 4, Número 7 de julio de 1961, págs. 321 Algoritmo 63: partición y Algoritmo 64: Quicksort.
Quicksort se adoptó ampliamente y apareció, por ejemplo, en Unix como la subrutina de ordenación predeterminada de la biblioteca. Por lo tanto, prestó su nombre a la subrutina de biblioteca estándar de C qsort [7] y a la implementación de referencia de Java .
La tesis doctoral de Robert Sedgewick en 1975 se considera un hito en el estudio de Quicksort, donde resolvió muchos problemas abiertos relacionados con el análisis de varios esquemas de selección de pivote, incluyendo Samplesort , la partición adaptativa de Van Emden [8], así como la derivación del número esperado de comparaciones e intercambios. [7] Jon Bentley y Doug McIlroy en 1993 incorporaron varias mejoras para su uso en bibliotecas de programación, incluyendo una técnica para tratar con elementos iguales y un esquema pivote conocido como pseudomediana de nueve, donde una muestra de nueve elementos se divide en grupos de tres y luego se elige la mediana de las tres medianas de tres grupos. [7] Bentley describió otro esquema de partición más simple y compacto en su libro Programming Pearls que atribuyó a Nico Lomuto. Más tarde, Bentley escribió que utilizó la versión de Hoare durante años, pero nunca la entendió realmente, pero la versión de Lomuto era lo suficientemente simple como para demostrar que era correcta. [9] Bentley describió Quicksort como el "código más hermoso que jamás había escrito" en el mismo ensayo. El esquema de partición de Lomuto también fue popularizado por el libro de texto Introducción a los algoritmos , aunque es inferior al esquema de Hoare porque hace tres veces más intercambios en promedio y se degrada a un tiempo de ejecución O ( n 2 ) cuando todos los elementos son iguales. [10] [ ¿ fuente autopublicada? ] McIlroy produciría además una función AntiQuicksort ( aqsort ) en 1998, que constantemente impulsa incluso su variante de 1993 de Quicksort a un comportamiento cuadrático al producir datos adversarios sobre la marcha. [11]
Quicksort es un tipo de algoritmo de división y conquista para ordenar una matriz, basado en una rutina de partición; los detalles de esta partición pueden variar un poco, por lo que quicksort es realmente una familia de algoritmos estrechamente relacionados. Aplicado a un rango de al menos dos elementos, la partición produce una división en dos subrangos consecutivos no vacíos, de tal manera que ningún elemento del primer subrango sea mayor que ningún elemento del segundo subrango. Después de aplicar esta partición, quicksort ordena recursivamente los subrangos, posiblemente después de excluir de ellos un elemento en el punto de división que en ese punto se sabe que ya está en su ubicación final. Debido a su naturaleza recursiva, quicksort (al igual que la rutina de partición) tiene que formularse de manera que sea invocable para un rango dentro de una matriz más grande, incluso si el objetivo final es ordenar una matriz completa. Los pasos para quicksort en el lugar son:
La elección de la rutina de partición (incluida la selección del pivote) y otros detalles no especificados en su totalidad anteriormente pueden afectar el rendimiento del algoritmo, posiblemente en gran medida para matrices de entrada específicas. Por lo tanto, al analizar la eficiencia de quicksort, es necesario especificar primero estas opciones. Aquí mencionamos dos métodos de partición específicos.
Este esquema se atribuye a Nico Lomuto y fue popularizado por Bentley en su libro Programming Pearls [12] y Cormen et al. en su libro Introduction to Algorithms . [13] En la mayoría de las formulaciones, este esquema elige como pivote el último elemento de la matriz. El algoritmo mantiene el índice i mientras escanea la matriz usando otro índice j de modo que los elementos en lo a i-1 (incluidos) sean menores que el pivote, y los elementos en i a j (incluidos) sean iguales o mayores que el pivote. Como este esquema es más compacto y fácil de entender, se usa con frecuencia en material introductorio, aunque es menos eficiente que el esquema original de Hoare, por ejemplo, cuando todos los elementos son iguales. [14] La complejidad de Quicksort con este esquema se degrada a O ( n 2 ) cuando la matriz ya está ordenada, debido a que la partición es la peor posible. [10] Se han propuesto varias variantes para mejorar el rendimiento, incluidas varias formas de seleccionar el pivote, manejar elementos iguales, usar otros algoritmos de ordenamiento como el ordenamiento por inserción para matrices pequeñas, etc. En pseudocódigo , un ordenamiento rápido que ordena los elementos desde lo hasta hi (inclusive) de una matriz A se puede expresar como: [13]
// Ordena una (porción de una) matriz, la divide en particiones y luego las ordena. El algoritmo quicksort(A, lo, hi) es // Asegura que los índices estén en el orden correcto si lo >= hi || lo < 0 entonces devolver // Particionar la matriz y obtener el índice pivote p := partición(A, lo, hi) // Ordena las dos particiones quicksort(A, lo, p - 1) // Lado izquierdo del pivote quicksort(A, p + 1, hi) // Lado derecho del pivote// Divide la matriz en dos particiones. El algoritmo de partición (A, lo, hi) es pivote: = A[hi] // Elige el último elemento como pivote // Índice pivote temporal yo := lo para j := lo a hi - 1 hacer // Si el elemento actual es menor o igual que el pivote si A[j] <= pivote entonces // Intercambia el elemento actual con el elemento en el índice pivote temporal intercambiar A[i] con A[j] // Mueve el índice pivote temporal hacia adelante yo := yo + 1 // Intercambia el pivote con el último elemento intercambia A[i] con A[hi] devuelve i // el índice del pivote
La ordenación de toda la matriz se logra mediante quicksort(A, 0, length(A) - 1) .
iy jrespectivamente), los contornos negros muestran las posiciones de los elementos ordenados y el cuadrado negro relleno muestra el valor que se está comparando ( pivot).El esquema de partición original descrito por Tony Hoare utiliza dos punteros (índices dentro del rango) que comienzan en ambos extremos de la matriz que se está particionando, luego se mueven uno hacia el otro, hasta que detectan una inversión: un par de elementos, uno mayor que el pivote en el primer puntero, y uno menor que el pivote en el segundo puntero; si en este punto el primer puntero todavía está antes del segundo, estos elementos están en el orden incorrecto entre sí, y luego se intercambian. [15] Después de esto, los punteros se mueven hacia adentro, y se repite la búsqueda de una inversión; cuando finalmente los punteros se cruzan (el primero apunta después del segundo), no se realiza ningún intercambio; se encuentra una partición válida, con el punto de división entre los punteros cruzados (cualquier entrada que pueda estar estrictamente entre los punteros cruzados es igual al pivote y puede excluirse de ambos subrangos formados). Con esta formulación es posible que un subrango resulte ser todo el rango original, lo que impediría que el algoritmo avance. Por lo tanto, Hoare estipula que al final, el subrango que contiene el elemento pivote (que todavía está en su posición original) se puede reducir en tamaño excluyendo ese pivote, después de (si es necesario) intercambiarlo con el elemento de subrango más cercano a la separación; de esta manera, se asegura la finalización de la clasificación rápida.
Con respecto a esta descripción original, las implementaciones a menudo hacen variaciones menores pero importantes. En particular, el esquema que se presenta a continuación incluye elementos iguales al pivote entre los candidatos para una inversión (por lo que se utilizan las pruebas "mayor que o igual" y "menor que o igual" en lugar de "mayor que" y "menor que" respectivamente; dado que la formulación utiliza do ... while en lugar de repeat ... till que en realidad se refleja en el uso de operadores de comparación estrictos [ aclaración necesaria ] ). Si bien no hay ninguna razón para intercambiar elementos iguales al pivote, este cambio permite que se omitan las pruebas sobre los propios punteros, que de otro modo son necesarias para garantizar que no se salgan del rango. De hecho, dado que al menos una instancia del valor pivote está presente en el rango, el primer avance de cualquiera de los punteros no puede pasar por esta instancia si se utiliza una prueba inclusiva; una vez que se realiza un intercambio, estos elementos intercambiados ahora están estrictamente por delante del puntero que los encontró, lo que evita que ese puntero se salga. (Esto último es cierto independientemente de la prueba utilizada, por lo que sería posible utilizar la prueba inclusiva solo cuando se busca la primera inversión. Sin embargo, el uso de una prueba inclusiva en todo momento también garantiza que se encuentre una división cerca del medio cuando todos los elementos en el rango sean iguales, lo que da una ganancia de eficiencia importante para ordenar matrices con muchos elementos iguales). El riesgo de producir una separación sin avance se evita de una manera diferente a la descrita por Hoare. Tal separación solo puede resultar cuando no se encuentran inversiones, y ambos punteros avanzan al elemento pivote en la primera iteración (entonces se considera que se han cruzado y no se produce ningún intercambio).
En pseudocódigo , [13]
// Ordena una (porción de una) matriz, la divide en particiones y luego las ordena. El algoritmo quicksort(A, lo, hi) es si lo >= 0 && hi >= 0 && lo < hi entonces p := partición(A, lo, hi) quicksort(A, lo, p) // Nota: el pivote ahora está incluido ordenamiento rápido(A, p + 1, hi)// Divide la matriz en dos particiones. El algoritmo partición(A, lo, hi) es // Valor pivote pivot := A[lo] // Elige el primer elemento como pivote // Índice izquierdo yo := lo - 1 // Índice derecho j := hola + 1 bucle para siempre // Mueve el índice izquierdo a la derecha al menos una vez y mientras el elemento en el índice izquierdo sea menor que el pivote haz i := i + 1 mientras A[i] < pivot // Mueva el índice derecho a la izquierda al menos una vez y mientras el elemento en el índice derecho sea mayor que el pivote, haga j := j - 1 mientras A[j] > pivote // Si los índices se cruzan, retorna si i >= j entonces retorna j // Intercambia los elementos en los índices izquierdo y derecho intercambia A[i] con A[j]
La matriz completa se ordena mediante quicksort(A, 0, length(A) - 1) .
El esquema de Hoare es más eficiente que el esquema de partición de Lomuto porque hace tres veces menos intercambios en promedio. Además, como se mencionó, la implementación dada crea una partición equilibrada incluso cuando todos los valores son iguales. [10] [ fuente autopublicada? ] , lo que el esquema de Lomuto no hace. Al igual que el esquema de partición de Lomuto, la partición de Hoare también haría que Quicksort se degrade a O ( n 2 ) para la entrada ya ordenada, si el pivote se eligió como el primer o el último elemento. Sin embargo, con el elemento del medio como pivote, los datos ordenados resultan con (casi) ningún intercambio en particiones de igual tamaño, lo que lleva al mejor comportamiento de Quicksort, es decir, O ( n log( n )) . Al igual que otros, la partición de Hoare no produce una clasificación estable. En este esquema, la ubicación final del pivote no está necesariamente en el índice que se devuelve, ya que el pivote y los elementos iguales al pivote pueden terminar en cualquier lugar dentro de la partición después de un paso de partición, y no pueden ordenarse hasta que se alcance el caso base de una partición con un solo elemento mediante recursión. Por lo tanto, los dos segmentos siguientes en los que recurre el algoritmo principal son (lo..p) (elementos ≤ pivote) y (p+1..hi) (elementos ≥ pivote) en lugar de (lo..p-1) y (p+1..hi) como en el esquema de Lomuto.
Recursiones posteriores (ampliación del párrafo anterior)
Vamos a ampliar un poco los dos segmentos siguientes en los que recurre el algoritmo principal. Debido a que estamos usando comparadores estrictos (>, <) en los bucles "do...while" para evitar que nos quedemos sin rango, existe la posibilidad de que el pivote en sí se intercambie con otros elementos en la función de partición. Por lo tanto, el índice devuelto en la función de partición no es necesariamente donde está el pivote real. Considere el ejemplo de [5, 2, 3, 1, 0] , siguiendo el esquema, después de la primera partición, la matriz se convierte en [0, 2, 1, 3, 5] , el "índice" devuelto es 2, que es el número 1, cuando el pivote real, el que elegimos para comenzar la partición, era el número 3. Con este ejemplo, vemos cómo es necesario incluir el índice devuelto de la función de partición en nuestras recursiones posteriores. Como resultado, se nos presentan las opciones de recurrir a (lo..p) y (p+1..hi) , o (lo..p - 1) y (p..hi) . La opción que elijamos de las dos depende de qué índice ( i o j ) devolvemos en la función de partición cuando los índices se cruzan, y de cómo elegimos nuestro pivote en la función de partición ( floor vs ceiling ).
Primero examinemos la opción de recursar en (lo..p) y (p+1..hi) , con el ejemplo de ordenar una matriz donde existen múltiples elementos idénticos [0, 0] . Si se devuelve el índice i (el "último" índice) después de que los índices se crucen en la función de partición, se devolvería el índice 1 después de la primera partición. La recursión posterior en (lo..p) sería en (0, 1), que corresponde exactamente a la misma matriz [0, 0] . Se produce una separación sin avance que causa una recursión infinita. Por lo tanto, es obvio que cuando se recurre en (lo..p) y (p+1..hi) , debido a que la mitad izquierda de la recursión incluye el índice devuelto, es el trabajo de la función de partición excluir la "cola" en escenarios sin avance. Es decir, se debe devolver el índice j (el índice "anterior" cuando los índices se cruzan) en lugar de i. Siguiendo una lógica similar, al considerar el ejemplo de una matriz ya ordenada [0, 1] , la elección del pivote debe ser "floor" para garantizar que los punteros se detengan en el "primero" en lugar del "último" (con "ceiling" como pivote, se devolvería el índice 1 y se incluiría en (lo..p) causando una recursión infinita). Es exactamente por la misma razón por la que se debe evitar la elección del último elemento como pivote.
La elección de recursar en (lo..p - 1) y (p..hi) sigue exactamente la misma lógica que la anterior. Debido a que la mitad derecha de la recursión incluye el índice devuelto, es el trabajo de la función de partición excluir la "cabeza" en escenarios de no avance. El índice i (el "último" índice después de que los índices se cruzan) en la función de partición necesita ser devuelto, y "ceiling" debe ser elegido como pivote. Los dos matices son claros, nuevamente, cuando se consideran los ejemplos de ordenación de una matriz donde existen múltiples elementos idénticos ( [0, 0] ), y una matriz ya ordenada [0, 1] respectivamente. Es digno de mención que con la versión de recursión, por la misma razón, la elección del primer elemento como pivote debe evitarse.
En las primeras versiones de quicksort, el elemento más a la izquierda de la partición se elegía a menudo como elemento pivote. Desafortunadamente, esto provoca un comportamiento del peor caso en matrices ya ordenadas, lo que es un caso de uso bastante común. [16] El problema se resolvió fácilmente eligiendo un índice aleatorio para el pivote, eligiendo el índice medio de la partición o (especialmente para particiones más largas) eligiendo la mediana del primer, medio y último elemento de la partición para el pivote (como recomendó Sedgewick ). [17] Esta regla de la "mediana de tres" contrarresta el caso de entrada ordenada (o ordenada a la inversa) y brinda una mejor estimación del pivote óptimo (la mediana verdadera) que seleccionar cualquier elemento individual, cuando no se conoce información sobre el orden de la entrada.
Fragmento de código de mediana de tres para la partición de Lomuto:
medio := ⌊(lo + hi) / 2⌋ si A[medio] < A[lo] intercambia A[lo] con A[mid]si A[hi] < A[lo] Intercambia A[lo] con A[hi]Si A[mid] < A[hi] intercambia A[mid] con A[hi]pivote := A[hola]
Primero se coloca una mediana A[hi]y luego ese nuevo valor A[hi]se utiliza para un pivote, como en el algoritmo básico presentado anteriormente.
En concreto, el número esperado de comparaciones necesarias para ordenar n elementos (véase § Análisis de ordenamiento rápido aleatorio) con selección de pivote aleatoria es 1,386 n log n . El pivote de mediana de tres lo reduce a C n , 2 ≈ 1,188 n log n , a expensas de un aumento del tres por ciento en el número esperado de intercambios. [7] Una regla de pivote aún más fuerte, para matrices más grandes, es elegir el noveno , una mediana de tres recursiva (Mo3), definida como [7]
La selección de un elemento pivote también se complica por la existencia de un desbordamiento de enteros . Si los índices de los límites de la submatriz que se está ordenando son suficientemente grandes, la expresión ingenua para el índice central, ( lo + hi )/2 , provocará un desbordamiento y proporcionará un índice pivote no válido. Esto se puede superar utilizando, por ejemplo, lo + ( hi − lo )/2 para indexar el elemento central, a costa de una aritmética más compleja. Surgen problemas similares en algunos otros métodos de selección del elemento pivote.
Con un algoritmo de partición como el esquema de partición de Lomuto descrito anteriormente (incluso uno que elija buenos valores de pivote), quicksort muestra un rendimiento deficiente para entradas que contienen muchos elementos repetidos. El problema es claramente evidente cuando todos los elementos de entrada son iguales: en cada recursión, la partición izquierda está vacía (ningún valor de entrada es menor que el pivote) y la partición derecha solo ha disminuido en un elemento (se elimina el pivote). En consecuencia, el esquema de partición de Lomuto tarda un tiempo cuadrático en ordenar una matriz de valores iguales. Sin embargo, con un algoritmo de partición como el esquema de partición de Hoare, los elementos repetidos generalmente dan como resultado una mejor partición y, aunque pueden ocurrir intercambios innecesarios de elementos iguales al pivote, el tiempo de ejecución generalmente disminuye a medida que aumenta el número de elementos repetidos (la memoria caché reduce la sobrecarga de intercambio). En el caso en que todos los elementos sean iguales, el esquema de partición de Hoare intercambia elementos innecesariamente, pero la partición en sí es el mejor caso, como se señaló en la sección Partición de Hoare anterior.
Para resolver el problema del esquema de partición de Lomuto (a veces llamado el problema de la bandera nacional holandesa [7] ), se puede utilizar una rutina de partición de tiempo lineal alternativa que separa los valores en tres grupos: valores menores que el pivote, valores iguales al pivote y valores mayores que el pivote. (Bentley y McIlroy llaman a esto una "partición gruesa" y ya se implementó en el qsort de la versión 7 de Unix . [7] ) Los valores iguales al pivote ya están ordenados, por lo que solo las particiones menores y mayores que necesitan ordenarse recursivamente. En pseudocódigo, el algoritmo de ordenación rápida se convierte en:
// Ordena una (porción de una) matriz, la divide en particiones y luego las ordena. El algoritmo quicksort(A, lo, hi) es si lo >= 0 y lo < hi entonces lt, gt := partición(A, lo, hi) // Múltiples valores de retorno ordenación rápida (A, lo, lt - 1) ordenación rápida (A, gt + 1, hi)// Divide la matriz en tres particiones. El algoritmo partición(A, lo, hi) es // Valor pivote pivot := A[(lo + hi) / 2] // Elige el elemento del medio como pivote (división de enteros) // Índice menor, igual y mayor es := lo eq := lo gt := hola // Iterar y comparar todos los elementos con el pivote while eq <= gt do if A[eq] < pivot then // Intercambiar los elementos en los índices iguales y menores swap A[eq] with A[lt] // Aumentar el índice menor es := es + 1 // Aumentar índice igual ecuación := ecuación + 1 de lo contrario, si A[eq] > pivote entonces // Intercambiar los elementos en los índices iguales y mayores intercambiar A[eq] con A[gt] // Disminuir el índice mayor gt := gt-1 de lo contrario // si A[eq] = pivot entonces // Aumentar el índice igual ecuación := ecuación + 1 // Devuelve los índices menor y mayor return lt, gt
El partitionalgoritmo devuelve índices para el primer elemento ('más a la izquierda') y el último ('más a la derecha') de la partición del medio. Todos los demás elementos de la partición son iguales al pivote y, por lo tanto, se ordenan. En consecuencia, no es necesario incluir los elementos de la partición en las llamadas recursivas a quicksort.
El mejor caso para el algoritmo ahora ocurre cuando todos los elementos son iguales (o se eligen de un pequeño conjunto de k ≪ n elementos). En el caso de que todos los elementos sean iguales, el ordenamiento rápido modificado realizará solo dos llamadas recursivas en submatrices vacías y, por lo tanto, finalizará en tiempo lineal (suponiendo que la partitionsubrutina no tarde más que el tiempo lineal).
Otras optimizaciones importantes, también sugeridas por Sedgewick y ampliamente utilizadas en la práctica, son: [18] [19]
La formulación de dividir y vencer de Quicksort lo hace susceptible de paralelización mediante paralelismo de tareas . El paso de partición se logra mediante el uso de un algoritmo de suma de prefijo paralelo para calcular un índice para cada elemento de la matriz en su sección de la matriz particionada. [22] [23] Dado un arreglo de tamaño n , el paso de partición realiza O( n ) trabajo en O (log n ) tiempo y requiere O( n ) espacio de borrador adicional. Después de que el arreglo ha sido particionado, las dos particiones se pueden ordenar recursivamente en paralelo. Suponiendo una elección ideal de pivotes, quicksort paralelo ordena un arreglo de tamaño n en O( n log n ) trabajo en O(log 2 n ) tiempo usando O( n ) espacio adicional.
Quicksort tiene algunas desventajas en comparación con algoritmos de ordenamiento alternativos, como el ordenamiento por fusión , que complican su paralelización eficiente. La profundidad del árbol de división y conquista de Quicksort afecta directamente la escalabilidad del algoritmo, y esta profundidad depende en gran medida de la elección del pivote del algoritmo. Además, es difícil paralelizar el paso de partición de manera eficiente en el lugar. El uso de espacio de trabajo simplifica el paso de partición, pero aumenta la huella de memoria del algoritmo y los gastos generales constantes.
Otros algoritmos de ordenamiento paralelo más sofisticados pueden lograr límites de tiempo incluso mejores. [24] Por ejemplo, en 1991 David MW Powers describió un quicksort paralelizado (y un radix sort relacionado ) que puede operar en tiempo O (log n ) en una PRAM ( máquina de acceso aleatorio paralelo) CRCW (lectura simultánea y escritura simultánea) con n procesadores realizando particiones implícitamente. [25]
La partición más desequilibrada ocurre cuando una de las sublistas devueltas por la rutina de partición tiene un tamaño de n − 1. [ 26] Esto puede ocurrir si el pivote resulta ser el elemento más pequeño o más grande de la lista, o en algunas implementaciones (por ejemplo, el esquema de partición de Lomuto como se describió anteriormente) cuando todos los elementos son iguales.
Si esto sucede repetidamente en cada partición, entonces cada llamada recursiva procesa una lista de tamaño uno menor que la lista anterior. En consecuencia, podemos hacer n − 1 llamadas anidadas antes de llegar a una lista de tamaño 1. Esto significa que el árbol de llamadas es una cadena lineal de n − 1 llamadas anidadas. La i ésima llamada realiza O ( n − i ) trabajo para realizar la partición, y , por lo que en ese caso quicksort toma O ( n 2 ) tiempo.
En el caso más equilibrado, cada vez que realizamos una partición dividimos la lista en dos partes casi iguales. Esto significa que cada llamada recursiva procesa una lista de la mitad del tamaño. En consecuencia, podemos hacer solo log 2 n llamadas anidadas antes de llegar a una lista de tamaño 1. Esto significa que la profundidad del árbol de llamadas es log 2 n . Pero no hay dos llamadas en el mismo nivel del árbol de llamadas que procesen la misma parte de la lista original; por lo tanto, cada nivel de llamadas necesita solo O ( n ) tiempo en total (cada llamada tiene una sobrecarga constante, pero como solo hay O ( n ) llamadas en cada nivel, esto se subsume en el factor O ( n ) ). El resultado es que el algoritmo usa solo O ( n log n ) tiempo.
Para ordenar una matriz de n elementos distintos, quicksort toma O ( n log n ) tiempo en expectativa, promediado sobre todas las n ! permutaciones de n elementos con igual probabilidad . Alternativamente, si el algoritmo selecciona el pivote de manera uniforme al azar de la matriz de entrada, se puede usar el mismo análisis para limitar el tiempo de ejecución esperado para cualquier secuencia de entrada; la expectativa se toma entonces sobre las elecciones aleatorias hechas por el algoritmo (Cormen et al. , Introducción a los algoritmos , [13] Sección 7.3).
Enumeramos aquí tres pruebas comunes de esta afirmación que ofrecen diferentes perspectivas sobre el funcionamiento de quicksort.
Si cada pivote tiene un rango en algún lugar en el 50 por ciento medio, es decir, entre el percentil 25 y el percentil 75, entonces divide los elementos con al menos un 25 % y como máximo un 75 % en cada lado. Si pudiéramos elegir de manera consistente dichos pivotes, solo tendríamos que dividir la lista en la mayoría de los casos antes de llegar a listas de tamaño 1, lo que daría como resultado un algoritmo O ( n log n ) .
Cuando la entrada es una permutación aleatoria, el pivote tiene un rango aleatorio, por lo que no se garantiza que esté en el 50 por ciento medio. Sin embargo, cuando comenzamos desde una permutación aleatoria, en cada llamada recursiva el pivote tiene un rango aleatorio en su lista, por lo que está en el 50 por ciento medio aproximadamente la mitad del tiempo. Eso es suficientemente bueno. Imagine que se lanza una moneda: cara significa que el rango del pivote está en el 50 por ciento medio, cruz significa que no. Ahora imagine que la moneda se lanza una y otra vez hasta que obtiene k caras. Aunque esto podría llevar mucho tiempo, en promedio solo se requieren 2 k lanzamientos, y la probabilidad de que la moneda no obtenga k caras después de 100 k lanzamientos es altamente improbable (esto se puede hacer riguroso usando límites de Chernoff ). Por el mismo argumento, la recursión de Quicksort terminará en promedio en una profundidad de llamada de solo . Pero si su profundidad de llamada promedio es O (log n ) , y cada nivel del árbol de llamadas procesa como máximo n elementos, la cantidad total de trabajo realizado en promedio es el producto, O ( n log n ) . El algoritmo no tiene que verificar que el pivote esté en la mitad media: si lo alcanzamos cualquier fracción constante de las veces, eso es suficiente para la complejidad deseada.
Un enfoque alternativo es establecer una relación de recurrencia para el factor T ( n ) , el tiempo necesario para ordenar una lista de tamaño n . En el caso más desequilibrado, una única llamada de ordenación rápida implica O ( n ) trabajo más dos llamadas recursivas en listas de tamaño 0 y n −1 , por lo que la relación de recurrencia es
Esta es la misma relación que para la ordenación por inserción y la ordenación por selección , y se resuelve en el peor caso T ( n ) = O ( n 2 ) .
En el caso más equilibrado, una única llamada de ordenamiento rápido implica O ( n ) trabajo más dos llamadas recursivas en listas de tamaño n /2 , por lo que la relación de recurrencia es
El teorema maestro para las recurrencias de divide y vencerás nos dice que T ( n ) = O ( n log n ) .
A continuación se presenta el esquema de una prueba formal de la complejidad temporal esperada de O ( n log n ) . Supongamos que no hay duplicados, ya que los duplicados podrían manejarse con un preprocesamiento y posprocesamiento de tiempo lineal, o se considerarían casos más fáciles que los analizados. Cuando la entrada es una permutación aleatoria, el rango del pivote es aleatorio uniforme de 0 a n − 1 . Entonces, las partes resultantes de la partición tienen tamaños i y n − i − 1 , e i es aleatorio uniforme de 0 a n − 1 . Por lo tanto, promediando todas las divisiones posibles y notando que el número de comparaciones para la partición es n − 1 , el número promedio de comparaciones sobre todas las permutaciones de la secuencia de entrada se puede estimar con precisión resolviendo la relación de recurrencia:
Resolviendo la recurrencia se obtiene C ( n ) = 2 n ln n ≈ 1,39 n log 2 n .
Esto significa que, en promedio, el quicksort funciona solo un 39 % peor que en su mejor caso. En este sentido, está más cerca del mejor caso que del peor. Un ordenamiento por comparación no puede usar menos de log 2 ( n !) comparaciones en promedio para ordenar n elementos (como se explica en el artículo Ordenamiento por comparación ) y en el caso de n grande , la aproximación de Stirling produce log 2 ( n !) ≈ n (log 2 n − log 2 e ) , por lo que el quicksort no es mucho peor que un ordenamiento por comparación ideal. Este rápido tiempo de ejecución promedio es otra razón para el dominio práctico del quicksort sobre otros algoritmos de ordenamiento.
El siguiente árbol binario de búsqueda (BST) corresponde a cada ejecución de quicksort: el pivote inicial es el nodo raíz; el pivote de la mitad izquierda es la raíz del subárbol izquierdo, el pivote de la mitad derecha es la raíz del subárbol derecho, y así sucesivamente. El número de comparaciones de la ejecución de quicksort es igual al número de comparaciones durante la construcción del BST mediante una secuencia de inserciones. Por lo tanto, el número promedio de comparaciones para quicksort aleatorio es igual al costo promedio de construir un BST cuando los valores insertados forman una permutación aleatoria.
Consideremos una BST creada mediante la inserción de una secuencia de valores que forman una permutación aleatoria. Sea C el costo de creación de la BST. Tenemos , donde es una variable aleatoria binaria que expresa si durante la inserción de hubo una comparación con .
Por linealidad de expectativa , el valor esperado de C es .
Fije i y j < i . Los valores , una vez ordenados, definen intervalos j +1 . La observación estructural central es que se compara con en el algoritmo si y solo si cae dentro de uno de los dos intervalos adyacentes a .
Observe que dado que es una permutación aleatoria, también es una permutación aleatoria, por lo que la probabilidad de que sea adyacente a es exactamente .
Terminamos con un pequeño cálculo:
El espacio utilizado por quicksort depende de la versión utilizada.
La versión in situ del método quicksort tiene una complejidad espacial de O (log n ) , incluso en el peor de los casos, cuando se implementa con cuidado utilizando las siguientes estrategias.
Quicksort con particionamiento in situ e inestable utiliza solo espacio adicional constante antes de realizar cualquier llamada recursiva. Quicksort debe almacenar una cantidad constante de información para cada llamada recursiva anidada. Dado que el mejor caso realiza como máximo O (log n ) llamadas recursivas anidadas, utiliza O (log n ) espacio. Sin embargo, sin el truco de Sedgewick para limitar las llamadas recursivas, en el peor de los casos quicksort podría realizar O ( n ) llamadas recursivas anidadas y necesitar O ( n ) espacio auxiliar.
Desde el punto de vista de la complejidad de bits, variables como lo y hi no utilizan espacio constante; se necesitan O (log n ) bits para indexar en una lista de n elementos. Debido a que existen tales variables en cada marco de pila, la ordenación rápida que utiliza el truco de Sedgewick requiere O ((log n ) 2 ) bits de espacio. Sin embargo, este requisito de espacio no es demasiado terrible, ya que si la lista contuviera elementos distintos, necesitaría al menos O ( n log n ) bits de espacio.
Otra versión menos común y no local del ordenamiento rápido utiliza espacio O ( n ) para el almacenamiento de trabajo y puede implementar un ordenamiento estable. El almacenamiento de trabajo permite que la matriz de entrada se pueda particionar fácilmente de manera estable y luego copiarla nuevamente a la matriz de entrada para llamadas recursivas sucesivas. La optimización de Sedgewick sigue siendo apropiada.
Quicksort es una versión optimizada en cuanto al espacio del ordenamiento de árbol binario . En lugar de insertar elementos secuencialmente en un árbol explícito, quicksort los organiza simultáneamente en un árbol que está implícito en las llamadas recursivas. Los algoritmos hacen exactamente las mismas comparaciones, pero en un orden diferente. Una propiedad a menudo deseable de un algoritmo de ordenamiento es la estabilidad, es decir, el orden de los elementos que se comparan como iguales no se modifica, lo que permite controlar el orden de las tablas de claves múltiples (por ejemplo, listas de directorios o carpetas) de forma natural. Esta propiedad es difícil de mantener para el ordenamiento rápido in situ (que utiliza solo espacio adicional constante para punteros y búferes, y O (log n ) espacio adicional para la gestión de la recursión explícita o implícita). Para los ordenamientos rápidos variantes que implican memoria adicional debido a representaciones que utilizan punteros (por ejemplo, listas o árboles) o archivos (efectivamente listas), es trivial mantener la estabilidad. Las estructuras de datos más complejas o limitadas al disco tienden a aumentar el costo de tiempo, en general haciendo un uso creciente de la memoria virtual o el disco.
El competidor más directo de quicksort es heapsort . Heapsort tiene las ventajas de la simplicidad y un tiempo de ejecución en el peor de los casos de O ( n log n ) , pero el tiempo de ejecución promedio de heapsort generalmente se considera más lento que el quicksort in situ, principalmente debido a su peor localidad de referencia . [27] Este resultado es discutible; algunas publicaciones indican lo contrario. [28] [29] La principal desventaja de quicksort es la complejidad de implementación requerida para evitar malas elecciones de pivote y el rendimiento resultante de O ( n 2 ) . Introsort es una variante de quicksort que resuelve este problema cambiando a heapsort cuando se detecta un mal caso. Los principales lenguajes de programación, como C++ (en las implementaciones de GNU y LLVM), usan introsort. [30]
Quicksort también compite con merge sort , otro algoritmo de ordenamiento O ( n log n ) . Las principales ventajas de merge sort son que es un ordenamiento estable y tiene un excelente rendimiento en el peor de los casos. La principal desventaja de merge sort es que es un algoritmo fuera de lugar, por lo que cuando se opera en matrices, las implementaciones eficientes requieren espacio auxiliar O ( n ) (frente a O (log n ) para quicksort con particionamiento en el lugar y recursión de cola, u O (1) para heapsort).
El ordenamiento por combinación funciona muy bien en listas enlazadas , ya que requiere solo una pequeña cantidad constante de almacenamiento auxiliar. Aunque el ordenamiento rápido se puede implementar como un ordenamiento estable utilizando listas enlazadas, no hay razón para hacerlo; a menudo sufrirá de malas elecciones de pivote sin acceso aleatorio y, esencialmente, siempre es inferior al ordenamiento por combinación. El ordenamiento por combinación también es el algoritmo de elección para el ordenamiento externo de conjuntos de datos muy grandes almacenados en medios de acceso lento, como almacenamiento en disco o almacenamiento conectado a red .
La ordenación por cubos con dos cubos es muy similar a la ordenación rápida; el pivote en este caso es efectivamente el valor en el medio del rango de valores, lo que funciona bien en promedio para entradas distribuidas uniformemente.
Un algoritmo de selección elige el k º más pequeño de una lista de números; este es un problema más fácil en general que la ordenación. Un algoritmo de selección simple pero eficaz funciona casi de la misma manera que quicksort, y por lo tanto se conoce como quickselect . La diferencia es que en lugar de hacer llamadas recursivas en ambas sublistas, solo hace una única llamada recursiva de cola en la sublista que contiene el elemento deseado. Este cambio reduce la complejidad promedio a lineal o tiempo O ( n ) , que es óptimo para la selección, pero el algoritmo de selección sigue siendo O ( n 2 ) en el peor de los casos.
Una variante de selección rápida, el algoritmo de mediana de medianas , elige los pivotes con más cuidado, asegurándose de que estén cerca de la mitad de los datos (entre los percentiles 30 y 70) y, por lo tanto, tiene un tiempo lineal garantizado: O ( n ) . Esta misma estrategia de pivote se puede utilizar para construir una variante de ordenación rápida (ordenación rápida de mediana de medianas) con un tiempo O ( n log n ) . Sin embargo, la sobrecarga de elegir el pivote es significativa, por lo que generalmente no se utiliza en la práctica.
De manera más abstracta, dado un algoritmo de selección O ( n ) , se puede utilizar para encontrar el pivote ideal (la mediana) en cada paso de quicksort y así producir un algoritmo de ordenamiento con un tiempo de ejecución O ( n log n ) . Las implementaciones prácticas de esta variante son considerablemente más lentas en promedio, pero son de interés teórico porque muestran que un algoritmo de selección óptimo puede producir un algoritmo de ordenamiento óptimo.
En lugar de dividir en dos submatrices utilizando un único pivote, el quicksort multipivote (también multiquicksort [21] ) divide su entrada en un número s de submatrices utilizando s − 1 pivotes. Si bien el caso de doble pivote ( s = 3 ) fue considerado por Sedgewick y otros ya a mediados de la década de 1970, los algoritmos resultantes no fueron más rápidos en la práctica que el quicksort "clásico". [31] Una evaluación de 1999 de un multiquicksort con un número variable de pivotes, ajustado para hacer un uso eficiente de las cachés del procesador, encontró que aumentaba el recuento de instrucciones en un 20% aproximadamente, pero los resultados de la simulación sugirieron que sería más eficiente en entradas muy grandes. [21] Una versión de quicksort de doble pivote desarrollada por Yaroslavskiy en 2009 [32] resultó ser lo suficientemente rápida [33] como para justificar su implementación en Java 7 , como el algoritmo estándar para ordenar matrices de primitivos (la ordenación de matrices de objetos se realiza utilizando Timsort ). [34] Posteriormente se descubrió que el beneficio de rendimiento de este algoritmo estaba relacionado principalmente con el rendimiento de la caché, [35] y los resultados experimentales indican que la variante de tres pivotes puede funcionar incluso mejor en máquinas modernas. [36] [37]
Para los archivos de disco, es posible una ordenación externa basada en particiones similar a la ordenación rápida. Es más lenta que la ordenación por fusión externa, pero no requiere espacio de disco adicional. Se utilizan 4 búferes, 2 para entrada, 2 para salida. Sea el número de registros en el archivo, el número de registros por búfer y el número de segmentos de búfer en el archivo. Los datos se leen (y escriben) desde ambos extremos del archivo hacia adentro. Sea los segmentos que comienzan al principio del archivo y los segmentos que comienzan al final del archivo. Los datos se leen en los búferes de lectura y . Se elige un registro pivote y los registros en los búferes y que no sean el registro pivote se copian en el búfer de escritura en orden ascendente y en el búfer de escritura en orden descendente en comparación con el registro pivote. Una vez que se llena el búfer o , se escribe en el archivo y se lee el siguiente búfer o del archivo. El proceso continúa hasta que se leen todos los segmentos y queda un búfer de escritura. Si ese búfer es un búfer de escritura, se le agrega el registro pivote y se escribe en el búfer. Si ese búfer es un búfer de escritura, el registro pivote se antepone al búfer y se escribe en el búfer. Esto constituye un paso de partición del archivo, y el archivo ahora está compuesto de dos subarchivos. Las posiciones de inicio y fin de cada subarchivo se insertan/extraen a una pila independiente o a la pila principal mediante recursión. Para limitar el espacio de la pila a , se procesa primero el subarchivo más pequeño. Para una pila independiente, inserte los parámetros del subarchivo más grande en la pila, itere en el subarchivo más pequeño. Para la recursión, recurra primero en el subarchivo más pequeño, luego itere para manejar el subarchivo más grande. Una vez que un subarchivo es menor o igual a 4 registros B, el subarchivo se ordena en el lugar mediante ordenación rápida y se escribe. Ese subarchivo ahora está ordenado y en su lugar en el archivo. El proceso continúa hasta que todos los subarchivos estén ordenados y en su lugar. El número promedio de pasadas en el archivo es aproximadamente , pero el patrón del peor caso es de pasadas (equivalente a para la ordenación interna del peor caso). [38]
Este algoritmo es una combinación de ordenación por radix y ordenación rápida. Elija un elemento de la matriz (el pivote) y considere el primer carácter (clave) de la cadena (multiclave). Particione los elementos restantes en tres conjuntos: aquellos cuyo carácter correspondiente es menor que, igual a y mayor que el carácter del pivote. Ordene recursivamente las particiones "menor que" y "mayor que" en el mismo carácter. Ordene recursivamente la partición "igual a" por el siguiente carácter (clave). Dado que ordenamos usando bytes o palabras de longitud W bits, el mejor caso es O ( KN ) y el peor caso O (2 K N ) o al menos O ( N 2 ) como para la ordenación rápida estándar, dada para claves únicas N <2 K , y K es una constante oculta en todos los algoritmos de ordenación por comparación estándar , incluido la ordenación rápida. Este es un tipo de ordenación rápida de tres vías en el que la partición del medio representa una submatriz ordenada (trivialmente) de elementos que son exactamente iguales al pivote.
También desarrollado por Powers como un algoritmo PRAM paralelo O ( K ) . Esto es nuevamente una combinación de ordenamiento por radix y ordenamiento rápido, pero la decisión de partición izquierda/derecha del ordenamiento rápido se toma en bits sucesivos de la clave y, por lo tanto, es O ( KN ) para claves N de K bits. Todos los algoritmos de ordenamiento por comparación asumen implícitamente el modelo transdicotómico con K en Θ (log N ) , como si K fuera más pequeño, podemos ordenar en tiempo O ( N ) usando una tabla hash o un ordenamiento de enteros . Si K ≫ log N pero los elementos son únicos dentro de O (log N ) bits, los bits restantes no serán examinados ni por el ordenamiento rápido ni por el ordenamiento por radix rápido. En su defecto, todos los algoritmos de ordenamiento por comparación también tendrán la misma sobrecarga de tener que buscar entre O ( K ) bits relativamente inútiles, pero el ordenamiento rápido por base evitará los peores comportamientos O ( N 2 ) de los ordenamientos rápidos estándar y por base, y será más rápido incluso en el mejor caso de esos algoritmos de comparación en estas condiciones de prefijo único ( K ) ≫ log N . Consulte Powers [39] para obtener más información sobre las sobrecargas ocultas en el ordenamiento por comparación, base y paralelo.
En cualquier algoritmo de ordenamiento basado en comparación, minimizar el número de comparaciones requiere maximizar la cantidad de información obtenida de cada comparación, lo que significa que los resultados de la comparación son impredecibles. Esto provoca frecuentes predicciones erróneas de las ramas , lo que limita el rendimiento. [40] BlockQuicksort [41] reorganiza los cálculos de quicksort para convertir las ramas impredecibles en dependencias de datos . Al realizar particiones, la entrada se divide en bloques de tamaño moderado (que caben fácilmente en la caché de datos ) y se llenan dos matrices con las posiciones de los elementos que se van a intercambiar. (Para evitar ramas condicionales, la posición se almacena incondicionalmente al final de la matriz y el índice del final se incrementa si se necesita un intercambio). Una segunda pasada intercambia los elementos en las posiciones indicadas en las matrices. Ambos bucles tienen solo una rama condicional, una prueba de terminación, que generalmente se realiza.
La técnica BlockQuicksort está incorporada en la implementación STL de C++ de LLVM , libcxx, lo que proporciona una mejora del 50 % en las secuencias de números enteros aleatorios. La técnica Quicksort que anula patrones ( pdqsort ), una versión de Introsort, también incorpora esta técnica. [30]
Existen varias variantes de ordenación rápida que separan los k elementos más pequeños o más grandes del resto de la entrada.
En 2004, Richard Cole y David C. Kandathil descubrieron una familia de algoritmos de ordenamiento de un parámetro, denominados ordenamientos de partición, que, en promedio (con todas las ordenaciones de entrada igualmente probables), realizan, como máximo, comparaciones (cercanas al límite inferior de la teoría de la información) y operaciones; en el peor de los casos, realizan comparaciones (y también operaciones); estas se realizan en el lugar y solo requieren espacio adicional. Se demostró una eficiencia práctica y una menor variación en el rendimiento frente a los ordenamientos rápidos optimizados (de Sedgewick y Bentley - McIlroy ). [42]
Aunque guardar pequeñas submatrices hasta el final tiene sentido desde una perspectiva de conteo de instrucciones, es exactamente lo incorrecto desde una perspectiva de rendimiento de la memoria caché.
en instancias pequeñas, Heapsort ya es considerablemente más lento que Quicksort (en nuestros experimentos, más del 30 % para n = 2 10 ) y en instancias más grandes, sufre de su pobre comportamiento de caché (en nuestros experimentos, más de ocho veces más lento que Quicksort para ordenar 2 28 elementos).
![{\displaystyle \nombre del operador {E} [C]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d00e09c61139656019942c3cd118d16b1cd3878)
![{\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9949df370597c61d1573cace1261c7595d0f1ee7)
![{\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2dadca7408799f6c84e2f2e80c4099e56cbe970)
