Ordenación rápida

Quicksort es un algoritmo de clasificación eficiente y de propósito general . Quicksort fue desarrollado por el informático británico Tony Hoare en 1959 ^[1] y publicado en 1961. ^[2] Todavía es un algoritmo de clasificación utilizado comúnmente. En general, es un poco más rápido que la ordenación por fusión y la ordenación en montón para datos aleatorios, particularmente 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 esta razón, a veces se le llama clasificación por intercambio de particiones . ^[4] Luego, las submatrices se ordenan de forma recursiva . Esto se puede hacer in situ , lo que requiere pequeñas cantidades adicionales de memoria para realizar la clasificación.

Quicksort es una clasificación por comparación , lo que significa que puede ordenar elementos de cualquier tipo para los cuales se define una relación "menor que" (formalmente, un orden total ). Es una clasificación basada 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 clasificación rápida no son estables , lo que significa que no se conserva el orden relativo de elementos de clasificación iguales.

El análisis matemático de clasificación rápida muestra que, en promedio , el algoritmo realiza comparaciones para ordenar n elementos. En el peor de los casos , hace comparaciones. $O(n\log {n})$ $O(n^{2})$

Historia

El algoritmo de clasificación rápida 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 una 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 la partición en Mercury Autocode pero tuvo problemas para manejar la lista de segmentos sin clasificar. A su regreso a Inglaterra, le pidieron que escribiera 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. 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 conoció ALGOL y su capacidad de realizar recursividad, lo 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 está publicado en Communications of the ACM (CACM), Volumen 4, Número 7 de julio de 1961, pág. 321 Algoritmo 63: partición y Algoritmo 64: Quicksort.

Quicksort obtuvo una adopción generalizada y apareció, por ejemplo, en Unix como la subrutina de clasificación de biblioteca predeterminada. Por lo tanto, prestó su nombre a la subrutina de la biblioteca estándar C qsort^[7] y en 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 pivotes, incluido Samplesort , la partición adaptativa de Van Emden ^[8] y 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, incluida 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 usó la versión de Hoare durante años pero que nunca la entendió realmente, pero que la versión de Lomuto era lo suficientemente simple como para resultar correcta. ^[9] Bentley describió Quicksort como "el código más hermoso que jamás haya 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 realiza tres veces más intercambios en promedio y se degrada a $O (n 2)$ en tiempo de ejecución cuando todos los elementos son iguales. ^[10]^{[ fuente autoeditada? ]} McIlroy produciría además una función AntiQuicksort ( aqsort ) en 1998, que conduce consistentemente incluso su variante de 1993 de Quicksort a un comportamiento cuadrático al producir datos contradictorios sobre la marcha. ^[11]

Algoritmo

Ejemplo completo de clasificación rápida en un conjunto aleatorio de números. El elemento sombreado es el pivote. Siempre se elige como último elemento de la partición. Sin embargo, elegir siempre el último elemento de la partición como pivote de esta manera da como resultado un rendimiento deficiente ( $O (n 2)$ ) en matrices *ya ordenadas* o matrices de elementos idénticos. Dado que los subconjuntos de elementos ordenados/idénticos surgen mucho hacia el final de un procedimiento de clasificación en un conjunto grande, las versiones del algoritmo de clasificación rápida que eligen el pivote como elemento intermedio se ejecutan mucho más rápido que el algoritmo descrito en este diagrama en grandes conjuntos de números.

Quicksort es un tipo de algoritmo de divide y vencerás para ordenar una matriz, basado en una rutina de partición; Los detalles de esta partición pueden variar un poco, de modo que Quicksort es en realidad una familia de algoritmos estrechamente relacionados. Aplicada 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 es mayor que ningún elemento del segundo subrango. Después de aplicar esta partición, la clasificación rápida clasifica recursivamente los subrangos, posiblemente después de excluir de ellos un elemento en el punto de división que en ese momento se sabe que ya se encuentra en su ubicación final. Debido a su naturaleza recursiva, la ordenación rápida (como la rutina de partición) debe formularse de manera que pueda ser invocada para un rango dentro de una matriz más grande, incluso si el objetivo final es ordenar una matriz completa. Los pasos para la clasificación rápida in situ son:

Si el rango tiene menos de dos elementos, regrese inmediatamente ya que no hay nada que hacer. Posiblemente para otras longitudes muy cortas se aplique un método de clasificación especial y se omita el resto de estos pasos.
De lo contrario, elija un valor, llamado pivote , que se produzca en el rango (la forma precisa de elección depende de la rutina de partición y puede implicar aleatoriedad).
Dividir el rango: reordenar sus elementos, mientras se determina un punto de división, de modo que todos los elementos con valores menores que el pivote vengan antes de la división, mientras que todos los elementos con valores mayores que el pivote vengan después de ella; Los elementos que son iguales al pivote pueden ir en cualquier dirección. Dado que al menos una instancia del pivote está presente, la mayoría de las rutinas de partición garantizan que el valor que termina en el punto de división sea igual al pivote y ahora esté en su posición final (pero la terminación de la clasificación rápida no depende de esto, siempre que se produzcan subgamas estrictamente inferiores a las originales).
Aplique recursivamente la clasificación rápida al subrango hasta el punto de división y al subrango posterior, posiblemente excluyendo de ambos rangos el elemento igual al pivote en el punto de división. (Si la partición produce un subrango posiblemente mayor cerca del límite donde se sabe que todos los elementos son iguales al pivote, estos también se pueden excluir).

La elección de la rutina de partición (incluida la selección de pivote) y otros detalles no completamente especificados 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 la clasificación rápida, es necesario especificar primero estas opciones. Aquí mencionamos dos métodos de partición específicos.

Esquema de partición de Lomuto

Este esquema se atribuye a Nico Lomuto y lo popularizó Bentley en su libro Programming Pearls ^[12] y Cormen et al. en su libro Introducción a los algoritmos . ^[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 de lo a i-1 (inclusive) sean menores que el pivote, y los elementos de i a j (inclusive) sean iguales o mayores que el pivote. Como este esquema es más compacto y fácil de entender, se utiliza 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á en orden, 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, tratar con elementos iguales, utilizar otros algoritmos de clasificación, como la clasificación por inserción para matrices pequeñas, etc. En pseudocódigo , una clasificación rápida que clasifica los elementos de bajo a alto (inclusive) de una matriz $A$ se puede expresar como: ^[13]

// Ordena una (parte de una) matriz, la divide en particiones, luego ordena esos algoritmos quicksort(A, lo, hi) es  // Asegúrese de que los índices estén en el orden correcto  si lo >= hi || bajo < 0 entonces  devolver  // Particionar la matriz y obtener el índice dinámico p := partición(A, lo, hola)  // 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 algoritmo partición(A, lo, hola) es pivote := A[hi] // Elige el último elemento como pivote // índice de pivote temporal yo := lo - 1 for j := lo to hi - 1 do  // Si el elemento actual es menor o igual que el pivote  if A[j] <= pivot entonces  // Mueve el índice de pivote temporal hacia adelante yo := yo + 1 // Intercambiar el elemento actual con el elemento en el índice de pivote temporal intercambiar A[i] con A[j] // Mueve el elemento pivote a la posición de pivote correcta (entre los elementos más pequeños y más grandes) yo := yo + 1 intercambiar A[i] con A[hi] return i // el índice de pivote

La clasificación de toda la matriz se logra mediante quicksort(A, 0, length(A) - 1) .

Esquema de partición Hoare

Una demostración animada de Quicksort utilizando el esquema de partición de Hoare. Los contornos rojos muestran las posiciones de los punteros izquierdo y derecho ( iy jrespectivamente), los contornos negros muestran las posiciones de los elementos ordenados y el cuadrado negro relleno muestra el valor con el que se compara ( pivot).

El esquema de partición original descrito por Tony Hoare utiliza dos punteros (índices en el rango) que comienzan en ambos extremos de la matriz que se está particionando y luego se mueven uno hacia el otro hasta que detectan una inversión: un par de elementos, uno mayor que el límite. (términos de Hoare para el valor de pivote) en el primer puntero y uno menos que el límite 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 primer punto 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) puede reducirse de tamaño excluyendo ese pivote, después (si es necesario) de intercambiarlo con el elemento subrango más cercano a la separación; por lo tanto, se garantiza la terminación de la clasificación rápida.

Con respecto a esta descripción original, las implementaciones suelen introducir 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 o igual" y "menor o igual" en lugar de "mayor que" y "menor que", respectivamente; ya que la formulación usa do ... while en lugar de repetir ... hasta lo cual en realidad se refleja mediante el uso de operadores de comparación estrictos ^[^{aclaración necesaria}^] ). Si bien no hay razón para intercambiar elementos iguales al límite, este cambio permite omitir las pruebas en los propios punteros, que de otro modo serían necesarias para garantizar que no se salgan del rango. De hecho, dado que al menos una instancia del valor de pivote está presente en el rango, el primer avance de cualquiera de los punteros no puede pasar a través de 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ó, evitando que ese puntero se escape. (Esto último es cierto independientemente de la prueba utilizada, por lo que sería posible usar la prueba inclusiva sólo cuando se busca la primera inversión. Sin embargo, usar una prueba inclusiva en todo momento también garantiza que se encuentre una división cerca del medio cuando todos los elementos en los rangos son iguales, lo que proporciona una importante ganancia de eficiencia para clasificar conjuntos con muchos elementos iguales). El riesgo de producir una separación que no avanza se evita de una manera diferente a la descrita por Hoare. Tal separación solo puede ocurrir cuando no se encuentran inversiones, con ambos punteros avanzando hacia el elemento pivote en la primera iteración (entonces se considera que se han cruzado y no se produce ningún intercambio). La división devuelta es posterior a la posición final del segundo puntero, por lo que el caso que se debe evitar es cuando el pivote es el elemento final del rango y todos los demás son más pequeños que él. Por lo tanto, la elección del pivote debe evitar el elemento final (en la descripción de Hoare podría ser cualquier elemento del rango); Esto se hace aquí redondeando hacia abajo la posición media, usando la función. ^[16] Esto ilustra que el argumento a favor de la corrección de una implementación del esquema de partición de Hoare puede ser sutil y es fácil equivocarse.floor

En pseudocódigo , ^[13]

// Ordena una (parte de una) matriz, la divide en particiones y luego ordena el algoritmo de clasificación rápida (A, lo, hola) si lo >= 0 && hi >= 0 && lo < hola entonces p := partición(A, lo, hola) quicksort(A, lo, p) // Nota: el pivote ahora está incluido clasificación rápida (A, p + 1, hola)// Divide la matriz en dos particiones algoritmo partición(A, lo, hi) es  // Valor de pivote pivote := 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 hacia la derecha al menos una vez y mientras el elemento en  // el índice izquierdo es menor que el pivote  do i := i + 1 while A[i] < pivote  // Mueve el índice derecho hacia la izquierda al menos una vez y mientras el elemento en  // el índice derecho es mayor que el pivote  haz j := j - 1 while A[j] > pivote // Si los índices se cruzan, devuelve  si i >= j luego  devuelve j  // Intercambia los elementos en los índices izquierdo y derecho  intercambia A[i] con A[j]

Toda la matriz está ordenada por quicksort(A, 0, length(A) - 1) .

El esquema de Hoare es más eficiente que el esquema de partición de Lomuto porque realiza 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 autoeditada? ]} , lo que el plan de Lomuto no hace. Al igual que el esquema de partición de Lomuto, la partición de Hoare también provocaría que Quicksort se degradara a $O (n 2)$ para entradas ya ordenadas, si el pivote se eligiera como primer o último elemento. Sin embargo, con el elemento intermedio como pivote, los datos ordenados resultan sin (casi) intercambios en particiones del mismo tamaño, lo que conduce al mejor comportamiento de Quicksort, es decir, $O (n log(n))$ . Como otros, la partición de Hoare no produce un tipo estable. En este esquema, la ubicación final del pivote no es 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 se pueden ordenar hasta el caso base de un La partición con un solo elemento se alcanza mediante recursividad. Por lo tanto, los siguientes dos segmentos en los que recurre el algoritmo principal son (lo..p) (elementos ≤ pivote) y (p+1..hi) (elementos ≥ pivote) en contraposición a (lo..p-1) y (p+1..hi) como en el esquema de Lomuto.

Recursiones posteriores (ampliación del párrafo anterior)

Ampliemos un poco los siguientes dos segmentos en los que se repite el algoritmo principal. Debido a que utilizamos comparadores estrictos (>, <) en los bucles "do... while" para evitar quedarnos fuera del rango, existe la posibilidad de que el propio pivote 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 iniciar la partición fue 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) . Cuál de las dos opciones elegimos depende de qué índice ( i o j ) devolvemos en la función de partición cuando los índices se cruzan y cómo elegimos nuestro pivote en la función de partición ( suelo vs techo ).

Primero examinemos la elección de recurrir a (lo..p) y (p+1..hi) , con el ejemplo de ordenar una matriz donde existen múltiples elementos idénticos [0, 0] . Si el índice i (el "último" índice) se devuelve después de que los índices se cruzan en la función de partición, el índice 1 se devolverá después de la primera partición. La recursividad posterior en (lo..p) sería en (0, 1), que corresponde exactamente a la misma matriz [0, 0] . Se produce una separación que no avanza y que provoca una recursividad infinita. Por lo tanto, es obvio que cuando se recurre a (lo..p) y (p+1..hi) , debido a que la mitad izquierda de la recursión incluye el índice devuelto, el trabajo de la función de partición es excluir la "cola" en no -escenarios de avance. Es decir, se debe devolver el índice j (el índice "antiguo" 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 "piso" para garantizar que los punteros se detengan en el "primero" en lugar del "último" (con "techo" como pivote, el índice 1 se devolvería y se incluiría en (lo..p) provocando una recursividad 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 recurrir a (lo..p - 1) y (p..hi) sigue exactamente la misma lógica que la anterior. Debido a que la mitad derecha de la recursividad incluye el índice devuelto, el trabajo de la función de partición es excluir el "cabezal" en escenarios que no avanzan. Se debe devolver el índice i (el índice "último" después del cruce de los índices) en la función de partición, y se debe elegir el "techo" como pivote. Los dos matices quedan claros, nuevamente, al considerar los ejemplos de ordenar una matriz donde existen múltiples elementos idénticos ( [0, 0] ) y una matriz ya ordenada [0, 1] respectivamente. Es de destacar que en la versión recursiva, por la misma razón, se debe evitar la elección del primer elemento como pivote.

Problemas de implementación

Elección del pivote

En las primeras versiones de clasificación rápida, el elemento más a la izquierda de la partición a menudo se elegía como elemento pivote. Desafortunadamente, esto provoca el peor comportamiento en matrices ya ordenadas, lo cual es un caso de uso bastante común. ^[17] 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 ( según lo recomendado por Sedgewick ). ^[18] Esta regla de la "mediana de tres" contrarresta el caso de entrada ordenada (o inversa) y proporciona una mejor estimación del pivote óptimo (la verdadera mediana) que seleccionar cualquier elemento individual, cuando no hay información sobre el Se conoce el orden de la entrada.

Fragmento de código de mediana de tres para la partición de Lomuto:

medio := ⌊(lo + hola) / 2⌋ si A[medio] < A[lo] intercambiar A[lo] con A[mid]si A[hola] < A[lo] intercambiar A[lo] con A[hola]si A[medio] < A[hola] intercambiar A[mid] con A[hola]pivote := A[hola]

Primero coloca una mediana A[hi]y luego ese nuevo valor de A[hi]se usa para un pivote, como en el algoritmo básico presentado anteriormente.

Específicamente, el número esperado de comparaciones necesarias para ordenar $n$ elementos (ver § Análisis de clasificación rápida aleatoria) con selección pivote aleatoria es $1,386 n log n$ . El pivotamiento de la mediana de tres reduce esto a $C n, 2 \approx 1,188 n log n$ , a expensas de un aumento del tres por ciento en el número esperado de swaps. ^[7] Una regla pivotante aún más estricta, para matrices más grandes, es elegir la novena , una mediana recursiva de tres (Mo3), definida como ^[7]

noveno( a ) = mediana(Mo3(primero.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/3de a ), Mo3(medio1/3de a ), Mo3(final1/3de un ))

La selección de un elemento pivote también es complicada por la existencia de desbordamiento de enteros . Si los índices de límite del subarreglo que se está ordenando son lo suficientemente grandes, la expresión ingenua para el índice medio, $(lo + hi)/2$ , provocará un desbordamiento y proporcionará un índice de pivote no válido. Esto se puede superar usando, 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.

Elementos repetidos

Con un algoritmo de partición como el esquema de partición de Lomuto descrito anteriormente (incluso uno que elige buenos valores de pivote), la clasificación rápida muestra un rendimiento deficiente para las 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 (el pivote se elimina). En consecuencia, el esquema de partición de Lomuto requiere un tiempo cuadrático para ordenar una matriz de valores iguales. Sin embargo, con un algoritmo de partición como el esquema de partición 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 (con memoria caché). reduciendo los gastos generales de swap). En el caso de que todos los elementos sean iguales, el esquema de partición Hoare intercambia elementos innecesariamente, pero la partición en sí es el mejor de los casos, como se indica en la sección de partición Hoare anterior.

Para resolver el problema del esquema de partición de Lomuto (a veces llamado 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 qsort de la versión 7 de Unix . ^[7] ) Los valores iguales al pivote ya están ordenados, por lo que solo se necesitan las particiones menor y mayor que para ser ordenado recursivamente. En pseudocódigo, el algoritmo de clasificación rápida se convierte en:

// Ordena una (parte de una) matriz, la divide en particiones, luego ordena esos algoritmos de clasificación rápida (A, lo, hi) es  si lo >= 0 && lo < hola entonces lt, gt := partición (A, lo, hola) // Múltiples valores de retorno clasificación rápida(A, lo, lt - 1) clasificación rápida (A, gt + 1, hola)// Divide la matriz en tres particiones algoritmo partición(A, lo, hi) es  // Valor de pivote pivote := A[(lo + hi) / 2] // Elige el elemento del medio como pivote (división entera)  // Índice menor, igual y mayor lt := lo ecuación: = lo gt := hola  // Iterar y comparar todos los elementos con el pivote  mientras eq <= gt do  if A[eq] < pivot entonces  // Intercambiar los elementos en índices iguales y menores  intercambiar A[eq] con A[lt] // Aumentar el índice menor lt := lt + 1 // Aumentar índice igual ecuación:= ecuación + 1 else  if A[eq] > pivot entonces  // Intercambia los elementos en índices iguales y mayores  intercambia A[eq] con A[gt] // Disminuye el índice mayor gt := gt - 1 else  // si A[eq] = pivote entonces  // Aumentar el índice igual ecuación:= ecuación + 1  // Devuelve índices menores y mayores  return lt, gt

El partitionalgoritmo devuelve índices al primer elemento ('más a la izquierda') y al ú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, están ordenados. En consecuencia, no es necesario incluir los elementos de la partición en las llamadas recursivas a quicksort.

El mejor caso para el algoritmo ocurre ahora cuando todos los elementos son iguales (o se eligen de un pequeño conjunto de $k ≪ n$ elementos). En el caso de todos los elementos iguales, la ordenación rápida modificada realizará sólo dos llamadas recursivas en subarreglos vacíos y, por lo tanto, finalizará en tiempo lineal (suponiendo que la partitionsubrutina no demore más que el tiempo lineal).

Optimizaciones

Otras optimizaciones importantes, también sugeridas por Sedgewick y ampliamente utilizadas en la práctica, son: ^[19]^[20]

Para asegurarse de que se utilice como máximo el espacio $O (log n)$ , recurra primero al lado más pequeño de la partición, luego use una llamada final para recurrir al otro, o actualice los parámetros para que ya no incluyan el lado más pequeño ahora ordenado, y iterar para ordenar el lado más grande.
Cuando el número de elementos está por debajo de cierto umbral (quizás diez elementos), cambie a un algoritmo de clasificación no recursivo, como la clasificación por inserción , que realiza menos intercambios, comparaciones u otras operaciones en matrices tan pequeñas. El "umbral" ideal variará según los detalles de la implementación específica.
Una variante más antigua de la optimización anterior: cuando el número de elementos es menor que el umbral $k$ , simplemente deténgase; luego, una vez procesada toda la matriz, realice la clasificación por inserción. Detener la recursividad antes de tiempo deja la matriz $k$ ordenada, lo que significa que cada elemento está como máximo $a k$ posiciones de su posición ordenada final. En este caso, la ordenación por inserción tarda $O (kn)$ tiempo en finalizar la ordenación, que es lineal si $k$ es una constante. ^[21]^[12]^{: 117} En comparación con la optimización de "muchos tipos pequeños", esta versión puede ejecutar menos instrucciones, pero hace un uso subóptimo de las memorias caché en las computadoras modernas. ^[22]

Paralelización

La formulación de divide y vencerás de Quicksort lo hace susceptible de paralelización mediante el paralelismo de tareas . El paso de partición se logra mediante el uso de un algoritmo de suma de prefijos paralelos para calcular un índice para cada elemento de la matriz en su sección de la matriz particionada. ^[23]^[24] Dada una matriz de tamaño $n$ , el paso de partición realiza $O(n)$ trabajo en $O (log n)$ tiempo y requiere $O(n)$ espacio temporal adicional. Una vez dividida la matriz, las dos particiones se pueden ordenar de forma recursiva en paralelo. Suponiendo una elección ideal de pivotes, la ordenación rápida paralela ordena una matriz de tamaño $n$ en $O(n log n)$ funciona en $O(log 2 n)$ tiempo usando $O(n)$ espacio adicional.

Quicksort tiene algunas desventajas en comparación con algoritmos de clasificación alternativos, como merge sort , que complican su paralelización eficiente. La profundidad del árbol de divide y vencerás 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 temporal simplifica el paso de partición, pero aumenta la huella de memoria del algoritmo y los gastos generales constantes.

Otros algoritmos de clasificación paralela más sofisticados pueden lograr límites de tiempo aún mejores. ^[25] Por ejemplo, en 1991 David Powers describió una clasificación rápida paralelizada (y una clasificación de base relacionada ) que puede operar en tiempo $O (log n)$ en una PRAM (máquina de acceso aleatorio paralelo) CRCW (lectura y escritura simultáneas ) con $n$ procesadores realizando la partición implícitamente. ^[26]

Análisis formal

Análisis del peor de los casos

La partición más desequilibrada ocurre cuando una de las sublistas devueltas por la rutina de partición es de tamaño $n - 1$ . ^[27] 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 describe 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 realizar $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 hace que $O (n - i)$ funcione para realizar la partición, por lo que, en ese caso, la ordenación rápida toma $O$ $($ $n$ $2$ $)$ tiempo. $\textstyle \sum _ {i=0}^{n}(ni)=O(n^{2})$

Análisis del mejor de los casos

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, solo podemos realizar $log 2 n$ llamadas anidadas antes de alcanzar 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 incluye en el factor $O (n)$ ). El resultado es que el algoritmo utiliza sólo tiempo $O (n log n)$ .

Análisis de casos promedio

Para ordenar una matriz de $n$ elementos distintos, la ordenación rápida toma $O (n log n)$ tiempo esperado, ¡promediado sobre todos los $n!$ permutaciones de $n$ elementos con igual probabilidad . Alternativamente, si el algoritmo selecciona el pivote uniformemente al azar de la matriz de entrada, se puede utilizar el mismo análisis para limitar el tiempo de ejecución esperado para cualquier secuencia de entrada; luego, la expectativa se asume sobre las elecciones aleatorias realizadas por el algoritmo (Cormen et al. , Introducción a los algoritmos , ^[13] Sección 7.3).

Aquí enumeramos tres pruebas comunes de esta afirmación que brindan diferentes conocimientos sobre el funcionamiento de Quicksort.

Usando percentiles

Si cada pivote tiene una clasificación en algún punto intermedio del 50 por ciento, 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 consistentemente dichos pivotes, solo tendríamos que dividir la lista la mayoría de las veces antes de llegar a listas de tamaño 1, lo que produciría un algoritmo $O$ $($ $n$ $log$ $n$ $)$ . $\log _{4/3}n$

Cuando la entrada es una permutación aleatoria, el pivote tiene un rango aleatorio y, por lo tanto, no se garantiza que esté en el 50 por ciento medio. Sin embargo, cuando partimos de una permutación aleatoria, en cada llamada recursiva el pivote tiene un rango aleatorio en su lista, por lo que está en el medio el 50 por ciento aproximadamente la mitad del tiempo. Eso es suficiente. Imagine que se lanza una moneda: cara significa que el rango del pivote está en el 50 por ciento medio, cruz significa que no lo está. Ahora imagina que la moneda se lanza una y otra vez hasta que sale $k$ cara. Aunque esto podría llevar mucho tiempo, en promedio solo se requieren $2 k$ lanzamientos, y la posibilidad de que la moneda no obtenga $k$ caras después de $100 k$ lanzamientos es muy improbable (esto se puede hacer riguroso usando límites de Chernoff ). Con el mismo argumento, la recursividad de Quicksort terminará en promedio con 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 golpeamos una fracción constante de veces, eso es suficiente para lograr la complejidad deseada. $2\log _{4/3}n$

Usando recurrencias

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 clasificación rápida implica trabajo $O (n)$ más dos llamadas recursivas en listas de tamaño $0$ y $n -1$ , por lo que la relación de recurrencia es

T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).

Esta es la misma relación que para el ordenamiento por inserción y el ordenamiento por selección , y se resuelve en el peor de los casos $T (n) = O (n 2)$ .

En el caso más equilibrado, una única llamada de clasificación rápida implica trabajo $O (n)$ más dos llamadas recursivas en listas de tamaño $n /2$ , por lo que la relación de recurrencia es

T(n)=O(n)+2T\left({\frac {n}{2}}\right).

El teorema maestro de las recurrencias de divide y vencerás nos dice que $T (n) = O (n log n)$ .

A continuación se muestra el esquema de una prueba formal de la complejidad temporal esperada $O (n log n)$ . Supongamos que no hay duplicados, ya que los duplicados podrían manejarse con tiempo lineal de pre y posprocesamiento, o considerarse 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$ , y i es aleatorio uniforme de 0 a $n - 1$ . Entonces, promediando todas las divisiones posibles y observando 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:

C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(ni-1))= n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)

nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)

nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)

nC(n)=(n+1)C(n-1)+2n-2

{\begin{alineado}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n +1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}} \\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{ \frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n +1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+ 1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{ x}}\mathrm {d} x=2\ln n\end{aligned}}

Resolver la recurrencia da $C (n) = 2 n ln n \approx 1,39 n log 2 n$ .

Esto significa que, en promedio, Quicksort funciona sólo alrededor de un 39% peor que en su mejor caso. En este sentido, está más cerca del mejor de los casos que del peor. Una ordenación por comparación no puede utilizar comparaciones inferiores a $log 2 (n!) en promedio para ordenar$ $n$ elementos (como se explica en el artículo Ordenación por comparación ) y, en caso de $n$ grande , la aproximación de Stirling produce $log 2 (n!) \approx n (log 2 n - log 2 e)$ , por lo que la clasificación rápida no es mucho peor que una clasificación por comparación ideal. Este rápido tiempo de ejecución promedio es otra razón para el dominio práctico de Quicksort sobre otros algoritmos de clasificación.

Usando un árbol de búsqueda binario

El siguiente árbol de búsqueda binaria (BST) corresponde a cada ejecución de clasificación rápida: 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. Entonces, el número promedio de comparaciones para la clasificación rápida aleatoria es igual al costo promedio de construir un BST cuando los valores insertados forman una permutación aleatoria. $(x_{1},x_{2},\ldots,x_{n})$

Considere un BST creado mediante la inserción de una secuencia de valores que forman una permutación aleatoria. Sea $C$ el coste de creación del BST. Tenemos , donde es una variable aleatoria binaria que expresa si durante la inserción de hubo una comparación con . $(x_{1},x_{2},\ldots,x_{n})$ $C=\sum _ {i}\sum _ {j<i}c_ {i,j}$ $c_{i,j}$ $x_{i}$ $x_{j}$

Por linealidad de la expectativa , el valor esperado de $C$ es . $\operatorname {E} [C]$ $\operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})$

Arreglar $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 . ${x_{1},x_{2},\ldots,x_{j}}$ $x_{i}$ $x_{j}$ $x_{i}$ $x_{j}$

Observe que como es una permutación aleatoria, también lo es, por lo que la probabilidad de que sea adyacente es exactamente . $(x_{1},x_{2},\ldots,x_{n})$ $(x_{1},x_{2},\ldots,x_{j},x_{i})$ $x_{i}$ $x_{j}$ ${\frac {2}{j+1}}$

Terminamos con un breve cálculo:

\operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\ Iniciar sesión i\right)=O(n\log n).

Complejidad espacial

El espacio utilizado por Quicksort depende de la versión utilizada.

La versión local de Quicksort tiene una complejidad espacial de $O (log n)$ , incluso en el peor de los casos, cuando se implementa cuidadosamente utilizando las siguientes estrategias.

Se utiliza la partición in situ. Esta partición inestable requiere espacio $O (1)$ .
Después de la partición, la partición con la menor cantidad de elementos se ordena (recursivamente) primero, lo que requiere como máximo espacio $O (log n) .$ Luego, la otra partición se ordena mediante recursividad o iteración de cola, lo que no se suma a la pila de llamadas. Esta idea, como se analizó anteriormente, fue descrita por R. Sedgewick y mantiene la profundidad de la pila limitada por $O (log n)$ . ^[18]^[21]

La clasificación rápida con partición inestable e in situ 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 de los casos realiza como máximo $O (log n)$ llamadas recursivas anidadas, utiliza el espacio $O (log n)$ . Sin embargo, sin el truco de Sedgewick para limitar las llamadas recursivas, en el peor de los casos, la clasificación rápida podría realizar $O (n)$ llamadas recursivas anidadas y necesitar $O (n)$ espacio auxiliar.

Desde el punto de vista de un poco de complejidad, variables como lo y hola no utilizan espacio constante; se necesitan $O (log n)$ bits para indexar una lista de $n$ elementos. Debido a que existen tales variables en cada marco de pila, la clasificación rápida usando el truco de Sedgewick requiere $O ((log n) 2)$ bits de espacio. Sin embargo, este requisito de espacio no es tan 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 implementada de clasificación rápida utiliza espacio $O (n)$ para el almacenamiento de trabajo y puede implementar una clasificación estable. El almacenamiento de trabajo permite dividir fácilmente la matriz de entrada de manera estable y luego copiarla nuevamente en la matriz de entrada para llamadas recursivas sucesivas. La optimización de Sedgewick sigue siendo apropiada.

Relación con otros algoritmos

Quicksort es una versión optimizada para el espacio de la clasificación de árbol binario . En lugar de insertar elementos secuencialmente en un árbol explícito, Quicksort los organiza simultáneamente en un árbol implícito en las llamadas recursivas. Los algoritmos hacen exactamente las mismas comparaciones, pero en diferente orden. Una propiedad a menudo deseable de un algoritmo de clasificación es la estabilidad: es decir, el orden de los elementos que se comparan iguales no cambia, lo que permite controlar el orden de las tablas de múltiples claves (por ejemplo, listados de directorios o carpetas) de forma natural. Esta propiedad es difícil de mantener para la ordenación rápida in situ (que utiliza solo espacio adicional constante para punteros y buffers, y $O (log n)$ espacio adicional para la gestión de recursividad explícita o implícita). Para variantes de clasificación rápida 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 ligadas a disco, tienden a aumentar el costo de tiempo y, en general, hacen un uso cada vez mayor de la memoria o el disco virtual.

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 de ordenación rápida in situ, principalmente debido a su peor localidad de referencia . ^[28] Este resultado es discutible; algunas publicaciones indican lo contrario. ^[29]^[30] La principal desventaja de Quicksort es la complejidad de implementación requerida para evitar malas elecciones de pivote y el rendimiento $O (n 2)$ resultante . Introsort es una variante de Quicksort que resuelve este problema cambiando a Heapsort cuando se detecta un caso grave. Los principales lenguajes de programación, como C++ (en las implementaciones GNU y LLVM), utilizan introsort. ^[31]

Quicksort también compite con merge sort , otro algoritmo de clasificación $O (n log n) .$ Las principales ventajas de Merge sort son que es una clasificación estable y tiene un excelente rendimiento en el peor de los casos. La principal desventaja de la ordenación por fusión es que es un algoritmo fuera de lugar, por lo que cuando se opera en matrices, las implementaciones eficientes requieren $O (n)$ espacio auxiliar (frente a $O (log n)$ para la ordenación rápida con partición y cola en el lugar. recursividad, u $O (1)$ para heapsort).

La clasificación por combinación funciona muy bien en listas vinculadas y solo requiere una cantidad pequeña y constante de almacenamiento auxiliar. Aunque la ordenación rápida se puede implementar como una ordenación estable usando listas enlazadas, no hay razón para hacerlo; a menudo sufrirá malas elecciones de pivote sin acceso aleatorio y, esencialmente, siempre es inferior a la ordenación por fusión. La clasificación por combinación es también el algoritmo elegido para la clasificación externa de conjuntos de datos muy grandes almacenados en medios de acceso lento, como el almacenamiento en disco o el almacenamiento conectado a la red .

La clasificación por cubetas con dos cubetas es muy similar a la clasificación rápida; el pivote en este caso es efectivamente el valor en el medio del rango de valores, que funciona bien en promedio para entradas distribuidas uniformemente.

Pivote basado en selección

Un algoritmo de selección elige el $k-$ ésimo más pequeño de una lista de números; Este es un problema más fácil en general que ordenar. Un algoritmo de selección simple pero efectivo funciona casi de la misma manera que la ordenación rápida y, por lo tanto, se conoce como selección rápida . La diferencia es que en lugar de realizar llamadas recursivas en ambas sublistas, solo realiza una única llamada recursiva de cola en la sublista que contiene el elemento deseado. Este cambio reduce la complejidad promedio a tiempo lineal o $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, asegurando que estén cerca del centro 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 clasificación rápida (mediana de medianas de clasificación rápida) con tiempo $O (n log n)$ . Sin embargo, la sobrecarga que implica 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 la clasificación rápida y así producir un algoritmo de clasificación 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 clasificación óptimo.

Variantes

Clasificación rápida multipivote

En lugar de dividir en dos subarreglos usando un solo pivote, la ordenación rápida multipivote (también multiquicksort ^[22] ) divide su entrada en un número $s$ de subarreglos usando $s - 1$ pivotes. Si bien Sedgewick y otros consideraron el caso de doble pivote ( $s = 3 ) ya a mediados de la década de 1970, los algoritmos resultantes no fueron más rápidos en la práctica que la clasificación rápida "clásica".$ ^[32] Una evaluación realizada en 1999 de un sistema multiquicksort con un número variable de pivotes, ajustado para hacer un uso eficiente de las memorias caché del procesador, encontró que aumentaba el recuento de instrucciones en aproximadamente un 20%, pero los resultados de la simulación sugirieron que sería más eficiente en archivos muy grandes. entradas. ^[22] Una versión de clasificación rápida de doble pivote desarrollada por Yaroslavskiy en 2009 ^[33] resultó ser lo suficientemente rápida ^[34] como para justificar su implementación en Java 7 , como algoritmo estándar para ordenar matrices de primitivas (la clasificación de matrices de objetos se realiza utilizando Timsort ). ^[35] Posteriormente se descubrió que el beneficio de rendimiento de este algoritmo estaba relacionado principalmente con el rendimiento de la caché, ^[36] y los resultados experimentales indican que la variante de tres pivotes puede funcionar incluso mejor en máquinas modernas. ^[37]^[38]

Clasificación rápida externa

Para archivos de disco, es posible una clasificación externa basada en particiones similar a la clasificación rápida. Es más lento que el tipo de combinación externo, pero no requiere espacio adicional en el disco. Se utilizan 4 buffers, 2 para entrada y 2 para salida. Sea N = número de registros en el archivo, B = el número de registros por búfer y M = N/B = 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 X los segmentos que comienzan al principio del archivo y Y los segmentos que comienzan al final del archivo. Los datos se leen en los buffers de lectura X e Y. Se elige un registro dinámico y los registros en los búferes X e Y distintos del registro dinámico se copian al búfer de escritura X en orden ascendente y al búfer de escritura Y en orden descendente en comparación con el registro dinámico. Una vez que se llena el búfer X o Y, se escribe en el archivo y se lee el siguiente búfer X o Y 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 X, se le agrega el registro dinámico y se escribe el búfer X. Si ese búfer es un búfer de escritura Y, el registro dinámico se antepone al búfer Y y se escribe el búfer Y. Esto constituye un paso de partición del archivo, y el archivo ahora se compone de dos subarchivos. Las posiciones inicial y final de cada subarchivo se empujan/extraen a una pila independiente o a la pila principal mediante recursividad. Para limitar el espacio de la pila a O(log2(n)), primero se procesa el subarchivo más pequeño. Para una pila independiente, inserte los parámetros del subarchivo más grande en la pila y repita en el subarchivo más pequeño. Para la recursividad, recurra primero en el subarchivo más pequeño y luego repita para manejar el subarchivo más grande. Una vez que un subarchivo tiene menos o igual a 4 registros B, el subarchivo se ordena en el lugar mediante clasificación rápida y se escribe. Ese subarchivo ahora está ordenado y ubicado en el archivo. El proceso continúa hasta que todos los subarchivos estén ordenados y en su lugar. El número promedio de pases en el archivo es aproximadamente 1 + ln(N+1)/(4 B), pero el patrón en el peor de los casos es N pases (equivalente a O(n^2) para la clasificación interna en el peor de los casos). ^[39]

Clasificación rápida de base de tres vías

Este algoritmo es una combinación de clasificación por base y clasificación rápida. Elija un elemento de la matriz (el pivote) y considere el primer carácter (clave) de la cadena (multiclave). Divida los elementos restantes en tres conjuntos: aquellos cuyo carácter correspondiente es menor, igual 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 clasificación rápida estándar, dada para claves únicas $N <2 K$ y $K$ es una constante oculta en todos los algoritmos de clasificación por comparación estándar , incluida la clasificación rápida. Este es un tipo de ordenación rápida de tres vías en la que la partición del medio representa un subconjunto de elementos ordenados (trivialmente) que son exactamente iguales al pivote.

Clasificación rápida por base

También desarrollado por Powers como un algoritmo PRAM paralelo $O (K)$ . Esto es nuevamente una combinación de clasificación por base y clasificación rápida, pero la decisión de partición izquierda/derecha de clasificación rápida se toma en bits sucesivos de la clave y, por lo tanto, es $O$ $($ $KN$ $)$ para claves de $N$ $K$ bits. Todos los algoritmos de clasificación 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 clasificación 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 mediante clasificación rápida ni mediante clasificación rápida por base. De lo contrario, todos los algoritmos de clasificación por comparación también tendrán la misma sobrecarga de buscar bits $O$ $($ $K$ $)$ relativamente inútiles, pero la clasificación rápida por base evitará los peores comportamientos $O$ $($ $N$ $2$ $)$ de la clasificación rápida estándar y la clasificación rápida por base, y será incluso más rápido. en el mejor de los casos de esos algoritmos de comparación bajo estas condiciones de $prefijo único ($ $K$ $) ≫$ log $N.$ Consulte Powers ^[40] para obtener más información sobre los gastos generales ocultos en comparación, clasificación por base y en paralelo.

Bloquear ordenación rápida

En cualquier algoritmo de clasificación basado en comparaciones, 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 en las ramas , lo que limita el rendimiento. ^[41] BlockQuicksort ^[42] reorganiza los cálculos de Quicksort para convertir ramas impredecibles en dependencias de datos . Al particionar, la entrada se divide en bloques de tamaño moderado (que caben fácilmente en el caché de datos ) y se llenan dos matrices con las posiciones de los elementos 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 sólo una rama condicional, una prueba de terminación, que normalmente se realiza.

La técnica BlockQuicksort está incorporada en la implementación STL C++ de LLVM , libcxx, lo que proporciona una mejora del 50 % en secuencias enteras aleatorias. La ordenación rápida que anula patrones ( pdqsort ), una versión de introsort, también incorpora esta técnica. ^[31]

Clasificación rápida parcial e incremental

Existen varias variantes de clasificación rápida que separan los $k$ elementos más pequeños o más grandes del resto de la entrada.

Generalización

Richard Cole y David C. Kandathil, en 2004, descubrieron una familia de algoritmos de clasificación de un solo parámetro, llamados clasificaciones de partición, que en promedio (con todos los ordenamientos de entrada igualmente probables) realizan en la mayoría de las comparaciones (cerca del 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); estos están en su lugar y solo requieren espacio adicional. Se demostró una eficiencia práctica y una menor variación en el rendimiento frente a las clasificaciones rápidas optimizadas (de Sedgewick y Bentley - McIlroy ). ^[43] $n\log n+{O}(n)$ ${\Theta }(n\log n)$ ${\Theta }(n\log ^{2}n)$ ${O}(\log n)$

Ver también

Introsort : algoritmo de clasificación híbrido

Notas

^ "Sir Antonio Hoare". Museo de Historia de la Computación. Archivado desde el original el 3 de abril de 2015 . Consultado el 22 de abril de 2015 .
^ ab Hoare, COCHE (1961). "Algoritmo 64: clasificación rápida". Com. ACM . 4 (7): 321. doi : 10.1145/366622.366644.
^ Skiena, Steven S. (2008). El manual de diseño de algoritmos. Saltador. pag. 129.ISBN _ 978-1-84800-069-8.
^ CL Foster, Algoritmos, abstracción e implementación , 1992, ISBN 0122626605 , p. 98
^ Shustek, L. (2009). "Entrevista: Una entrevista con CAR Hoare". Com. ACM . 52 (3): 38–41. doi :10.1145/1467247.1467261. S2CID 1868477.
^ "Mi entrevista Quickshort con Sir Tony Hoare, el inventor de Quicksort". Marcelo M. De Barros. 15 de marzo de 2015.
^ abcdefg Bentley, Jon L.; McIlroy, M. Douglas (1993). "Ingeniería de una función de clasificación". Software: práctica y experiencia . 23 (11): 1249-1265. CiteSeerX 10.1.1.14.8162 . doi : 10.1002/spe.4380231105. S2CID 8822797.
^ Van Emden, MH (1 de noviembre de 1970). "Algoritmos 402: aumento de la eficiencia de Quicksort". Comunitario. ACM . 13 (11): 693–694. doi : 10.1145/362790.362803 . ISSN 0001-0782. S2CID 4774719.
^ Bentley, Jon (2007). "El código más bonito que nunca escribí". En Oram, Andy; Wilson, Greg (eds.). Hermoso código: los programadores líderes explican cómo piensan . Medios O'Reilly. pag. 30.ISBN _ 978-0-596-51004-6.
^ abc "Partición de clasificación rápida: Hoare frente a Lomuto". cs.stackexchange.com . Consultado el 3 de agosto de 2015 .
^ McIlroy, MD (10 de abril de 1999). "Un adversario asesino para la clasificación rápida" (PDF) . Software: práctica y experiencia . 29 (4): 341–344. doi :10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R. S2CID 35935409.
^ ab Jon Bentley (1999). Perlas de programación . Profesional de Addison-Wesley.
^ abcd Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. "Ordenación rápida". Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. págs. 170-190. ISBN 0-262-03384-4.
^ Salvaje, Sebastián (2012). Clasificación rápida de doble pivote de Java 7 (tesis). Universidad Técnica de Kaiserslautern.
^ Hoare, CAR (1 de enero de 1962). "Ordenación rápida". La revista informática . 5 (1): 10-16. doi : 10.1093/comjnl/5.1.10 . ISSN 0010-4620.
^ en muchos idiomas este es el comportamiento estándar de la división de enteros
^ Chandramouli, Badrish; Goldstein, Jonathan (18 de junio de 2014). "La paciencia es una virtud". Actas de la Conferencia Internacional ACM SIGMOD 2014 sobre Gestión de Datos . Sigmod '14. Snowbird Utah Estados Unidos: ACM. págs. 731–742. doi :10.1145/2588555.2593662. ISBN 978-1-4503-2376-5. S2CID 7830071.
^ ab Sedgewick, Robert (1 de septiembre de 1998). Algoritmos en C: fundamentos, estructuras de datos, clasificación, búsqueda, partes 1 a 4 (3 ed.). Educación Pearson. ISBN 978-81-317-1291-7.
^ qsort.c en GNU libc : [1], [2]
^ http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html ^{[ enlace muerto permanente ]}
^ ab Sedgewick, R. (1978). "Implementación de programas Quicksort". Com. ACM . 21 (10): 847–857. doi :10.1145/359619.359631. S2CID 10020756.
^ abc LaMarca, Anthony; Ladner, Richard E. (1999). "La influencia de las cachés en el rendimiento de la clasificación". Revista de algoritmos . 31 (1): 66-104. CiteSeerX 10.1.1.27.1788 . doi :10.1006/jagm.1998.0985. S2CID 206567217. Aunque guardar subarreglos pequeños hasta el final tiene sentido desde la perspectiva del recuento de instrucciones, es exactamente lo incorrecto desde la perspectiva del rendimiento de la caché.
^ Umut A. Acar, Guy E Blelloch, Margaret Reid-Miller y Kanat Tangwongsan, Clasificación rápida y clasificación de límites inferiores, algoritmos y estructuras de datos paralelos y secuenciales . 2013.
^ Breshears, arcilla (2012). "Partición de clasificación rápida mediante exploración de prefijos". Dr. Dobb .
^ Molinero, Russ; Boxeador, Laurence (2000). Algoritmos secuenciales y paralelos: un enfoque unificado. Prentice Hall. ISBN 978-0-13-086373-7.
^ Poderes, David MW (1991). Quicksort y Radixsort paralelos con aceleración óptima . Proc. Conferencia Internacional. sobre Tecnologías de Computación Paralela. CiteSeerX 10.1.1.57.9071 .
^ El otro puede tener $1$ elemento o estar vacío (tener $0$ elementos), dependiendo de si el pivote está incluido en una de las subparticiones, como en la rutina de partición de Hoare, o está excluido de ambas, como en la rutina de Lomuto. .
^ Edelkamp, Stefan; Weiß, Armin (7 a 8 de enero de 2019). Clasificación eficiente en el peor de los casos con QuickMergesort . ALENEX 2019: XXI Taller de Ingeniería de Algoritmos y Experimentos. San Diego. arXiv : 1811.99833 . doi :10.1137/1.9781611975499.1. ISBN 978-1-61197-549-9. en instancias pequeñas, Heapsort ya es considerablemente más lento que Quicksort (en nuestros experimentos más del 30% para n = 2 ¹⁰ ) 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 ²⁸ elementos).
^ Hsieh, Paul (2004). "Clasificación revisada". azillionmonkeys.com.
^ MacKay, David (diciembre de 2005). "Heapsort, Quicksort y entropía". Archivado desde el original el 1 de abril de 2009.
^ ab Kutenin, Danila (20 de abril de 2022). "Cambiar std::sort a la escala de Google y más allá". Frío experimental .
^ Salvaje, Sebastián; Nebel, Markus E. (2012). "Análisis de caso promedio de ordenación rápida de doble pivote de Java 7 ". Simposio europeo sobre algoritmos. arXiv : 1310.7409 . Código Bib : 2013arXiv1310.7409W.
^ Yaroslavskiy, Vladimir (2009). "Clasificación rápida de doble pivote" (PDF) . Archivado desde el original (PDF) el 2 de octubre de 2015.
^ Salvaje, S.; Nebel, M.; Reitzig, R.; Laube, U. (7 de enero de 2013). Ingeniería de clasificación rápida de doble pivote de Java 7 utilizando MaLiJAn . Actas. Sociedad de Matemática Industrial y Aplicada. págs. 55–69. doi :10.1137/1.9781611972931.5. ISBN 978-1-61197-253-5.
^ "Matrices". Plataforma Java SE 7 . Oráculo . Consultado el 4 de septiembre de 2014 .
^ Salvaje, Sebastian (3 de noviembre de 2015). "¿Por qué la clasificación rápida de doble pivote es rápida?". arXiv : 1511.01138 [cs.DS].
^ Kushagra, Shrinu; López-Ortiz, Alejandro; Qiao, Aurick; Munro, J. Ian (2014). Clasificación rápida multipivote: teoría y experimentos . Proc. Taller de Ingeniería de Algoritmos y Experimentos (ALENEX). doi : 10.1137/1.9781611973198.6 .
^ Kushagra, Shrinu; López-Ortiz, Alejandro; Munro, J. Ian; Qiao, Aurick (7 de febrero de 2014). Clasificación rápida multipivote: teoría y experimentos (PDF) (Presentación del seminario). Waterloo, Ontario .
^ Motzkin, D.; Hansen, CL (1982), "Una clasificación externa eficiente con requisitos mínimos de espacio", Revista Internacional de Ciencias de la Información y la Computación , 11 (6): 381–396, doi :10.1007/BF00996816, S2CID 6829805
^ David MW Powers, Unificación paralela: complejidad práctica, Taller de arquitectura informática de Australasia, Universidad de Flinders, enero de 1995
^ Kaligosi, Kanela; Sanders, Peter (11 a 13 de septiembre de 2006). Cómo las predicciones erróneas de las sucursales afectan la clasificación rápida (PDF) . ESA 2006: 14º Simposio europeo anual sobre algoritmos. Zúrich . doi :10.1007/11841036_69.
^ Edelkamp, Stefan; Weiß, Armin (22 de abril de 2016). "BlockQuicksort: cómo las predicciones erróneas de las ramas no afectan a Quicksort". arXiv : 1604.06697 [cs.DS].
^ Richard Cole, David C. Kandathil: "El análisis de caso promedio de tipos de partición", Simposio europeo sobre algoritmos, 14 a 17 de septiembre de 2004, Bergen, Noruega. Publicado: Apuntes de conferencias sobre informática 3221, Springer Verlag, págs.

Referencias

Sedgewick, R. (1978). "Implementación de programas Quicksort". Com. ACM . 21 (10): 847–857. doi :10.1145/359619.359631. S2CID 10020756.
Dean, BC (2006). "Un análisis simple del tiempo de ejecución esperado para algoritmos aleatorios de 'divide y vencerás'". Matemática Aplicada Discreta . 154 : 1–5. doi : 10.1016/j.dam.2005.07.005 .
Hoare, COCHE (1961). "Algoritmo 63: Partición". Com. ACM . 4 (7): 321. doi : 10.1145/366622.366642. S2CID 52800011.
Hoare, COCHE (1961). "Algoritmo 65: Buscar". Com. ACM . 4 (7): 321–322. doi :10.1145/366622.366647.
Hoare, COCHE (1962). "Ordenación rápida". Computadora. J. 5 (1): 10-16. doi : 10.1093/comjnl/5.1.10 .(Reimpreso en Hoare y Jones: Ensayos sobre ciencias de la computación, 1989.)
Musser, David R. (1997). "Algoritmos de selección y clasificación introspectivos". Software: práctica y experiencia . 27 (8): 983–993. doi :10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
Donald Knuth . El arte de la programación informática , volumen 3: clasificación y búsqueda , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Páginas 113–122 de la sección 5.2.2: Clasificación por intercambio.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill , 2001. ISBN 0-262-03293-7 . Capítulo 7: Clasificación rápida, págs. 145-164.
Faron Moller . Análisis de Quicksort. CS 332: Diseño de algoritmos. Departamento de Ciencias de la Computación, Universidad de Swansea .
Martínez, C.; Roura, S. (2001). "Estrategias de muestreo óptimas en Quicksort y Quickselect". SIAM J. Computación. 31 (3): 683–705. CiteSeerX 10.1.1.17.4954 . doi :10.1137/S0097539700382108.
Bentley, JL; McIlroy, Doctor en Medicina (1993). "Ingeniería de una función de clasificación". Software: práctica y experiencia . 23 (11): 1249-1265. CiteSeerX 10.1.1.14.8162 . doi :10.1002/spe.4380231105. S2CID 8822797.

enlaces externos

La implementación del algoritmo Wikibook tiene una página sobre el tema: Quicksort

"Algoritmos de clasificación animados: clasificación rápida". Archivado desde el original el 2 de marzo de 2015 . Consultado el 25 de noviembre de 2008 .– demostración gráfica
"Algoritmos de clasificación animados: clasificación rápida (partición de 3 vías)". Archivado desde el original el 6 de marzo de 2015 . Consultado el 25 de noviembre de 2008 .
Estructuras de datos abiertas – Sección 11.1.2 – Quicksort, Pat Morin
Ilustración interactiva de Quicksort, con tutorial de código
Clasificación rápida con Quicksort, una inmersión profunda para principiantes