Ordenación rápida

En las primeras versiones de quicksort, el elemento más a la izquierda de la partición solía elegirse como pivote. Desafortunadamente, esto provoca un comportamiento desfavorable en matrices ya ordenadas, un caso de uso bastante común. ^{[ 17 ]} El problema se resolvió fácilmente eligiendo un índice aleatorio para el pivote, el índice central de la partición o (especialmente para particiones más largas) la mediana del primer, el medio y el último elemento de la partición como pivote (como recomendó Sedgewick ). ^{[ 18 ]} Esta regla de "mediana de tres" contrarresta el caso de entrada ordenada (o en orden inverso) y proporciona una mejor estimación del pivote óptimo (la mediana real) 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] Intercambiar A[lo] con A[mid] si A[hi] < A[lo] Intercambiar A[lo] con A[hi] si A[medio] < A[alto] Intercambiar A[medio] con A[agudo] pivote := A[hi]

Primero coloca la mediana A[hi], y luego ese nuevo valor A[hi]se utiliza como 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 del caso promedio ) con selección aleatoria de pivote es 1,386 n log n . El pivoteo de mediana de tres reduce esto a C _{n , 2} ≈ 1,188 n log n , a costa de un aumento del tres por ciento en el número esperado de intercambios. ^{[ 8 ]} Una regla de pivoteo aún más fuerte, para arreglos más grandes, es elegir el noveno , una mediana recursiva de tres (Mo3), definida como ^{[ 8 ]}

noveno( a ) = mediana (Mo3(primer 1/3 de a ) , Mo3 ( medio 1/3 de a ) , Mo3 ( final 1/3 de a ) )

La selección del elemento pivote también se complica por la existencia de desbordamiento de enteros . Si los índices límite del subconjunto que se está ordenando son suficientemente grandes, la expresión simple para el índice central, ( lo + hi )/2 , provocará un desbordamiento y dará como resultado un índice pivote inválido. Esto se puede solucionar utilizando, por ejemplo, lo + ( hi − lo )/2 para indexar el elemento central, aunque esto implica una aritmética más compleja. Problemas similares surgen en otros métodos de selección del elemento pivote.

Con un algoritmo de particionamiento como el esquema de partición de Lomuto descrito anteriormente (incluso uno que elige 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 (el pivote se ha eliminado). En consecuencia, el esquema de partición de Lomuto tarda un tiempo cuadrático en ordenar un arreglo de valores iguales. Sin embargo, con un algoritmo de particionamiento como el esquema de partición de Hoare, los elementos repetidos generalmente dan como resultado un mejor particionamiento, 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 la caché de memoria reduciendo la sobrecarga de intercambio). En el caso de que todos los elementos sean iguales, el esquema de partición de Hoare intercambia elementos innecesariamente, pero el particionamiento en sí es el mejor caso, como se señaló en la sección de partición de Hoare anterior.

Para resolver el problema del esquema de partición de Lomuto (a veces llamado problema de la bandera nacional holandesa ^{[ 8 ]} ), se puede utilizar una rutina de partición alternativa de tiempo lineal 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 lo llaman "partición gorda" y ya estaba implementado en el algoritmo qsort de la versión 7 de Unix ^{[ 8 ]} ) . Los valores iguales al pivote ya están ordenados, por lo que solo las particiones menores que y mayores que necesitan ordenarse recursivamente. En pseudocódigo, el algoritmo quicksort se convierte en:

// Ordena (una parte de) un array, lo divide en particiones y luego ordena esas particiones. El algoritmo quicksort(A, lo, hi) es if lo >= 0 && lo < hi then lt, gt := partition(A, lo, hi) // Múltiples valores de retorno ordenación rápida(A, lo, lt - 1) ordenación rápida(A, gt + 1, hola) // Divide el array en tres particiones algoritmo partition(A, lo, hi) es // Valor pivote pivote := A[(lo + hi) / 2] // Elige el elemento central como pivote (división entera)// Índice menor, igual y mayor lt := lo eq := lo gt := hola // Iterar y comparar todos los elementos con el pivote mientras eq <= gt hacer si A[eq] < pivote entonces // Intercambiar los elementos en los índices iguales y menores intercambiar A[eq] con A[lt] // Incrementar el índice menor lt := lt + 1 // Incrementar el índice igual eq := eq + 1 else if A[eq] > pivot then // Intercambiar los elementos en los índices iguales y mayores intercambiar A[eq] con A[gt] // Disminuir el índice mayor gt := gt - 1 else // si A[eq] = pivote entonces // Incrementar el índice igual eq := eq + 1 // Devuelve los índices menor y mayor return lt, gt

El partitionalgoritmo devuelve los índices del primer ('más a la izquierda') y del último ('más a la derecha') elemento de la partición central. Todos los demás elementos de la partición son iguales al pivote y, por lo tanto, están ordenados. En consecuencia, los elementos de la partición no necesitan incluirse en las llamadas recursivas a quicksort.

El mejor escenario para el algoritmo se da 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 algoritmo quicksort modificado realizará solo dos llamadas recursivas en subarreglos vacíos y, por lo tanto, finalizará en tiempo lineal (siempre que la partitionsubrutina no tarde más que tiempo lineal).

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

• Para asegurarnos de que se utilice como máximo un espacio de O (log n ) , primero recurramos en el lado más pequeño de la partición, luego usemos una llamada de cola para recurrir en el otro, o bien actualicemos los parámetros para que ya no incluyan el lado más pequeño ahora ordenado, e iteremos para ordenar el lado más grande.
• Cuando el número de elementos sea inferior a un umbral determinado (por ejemplo, diez elementos), se recomienda utilizar un algoritmo de ordenación no recursivo, como la ordenació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 anterior de la optimización previa: cuando el número de elementos es menor que el umbral k , simplemente se detiene; luego, después de que se haya procesado todo el array, se realiza una ordenación por inserción. Detener la recursión prematuramente deja el array ordenado k posiciones, lo que significa que cada elemento está como máximo k posiciones lejos de su posición final ordenada. En este caso, la ordenación por inserción tarda O ( kn ) tiempo en terminar la ordenación, que es lineal si k es una constante. ^{[ 21 ] [ 13 ] : 117} En comparación con la optimización de "muchas ordenaciones pequeñas", esta versión puede ejecutar menos instrucciones, pero hace un uso subóptimo de las memorias caché en las computadoras modernas. ^{[ 22 ]}

La formulación de divide y vencerás de Quicksort lo hace apto para la paralelización usando paralelismo de tareas . El paso de partición se realiza mediante el uso de un algoritmo de suma de prefijos paralelo para calcular un índice para cada elemento de la matriz en su sección de la matriz particionada. ^{[ 23 ] [ 24 ]} Dado 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 adicional de trabajo. Después de que la matriz ha sido particionada, las dos particiones se pueden ordenar recursivamente en paralelo. Suponiendo una elección ideal de pivotes, Quicksort paralelo ordena una matriz de tamaño n en O( n log n ) trabajo en O(log ² n ) tiempo usando O( n ) espacio adicional.

Quicksort presenta algunas desventajas en comparación con otros algoritmos de ordenación, como la ordenación por fusión , lo que dificulta su paralelización eficiente. La profundidad del árbol de divide y vencerás de Quicksort influye directamente en la escalabilidad del algoritmo, y esta profundidad depende en gran medida de la elección del pivote. Además, resulta difícil paralelizar de forma eficiente la etapa de particionamiento in situ. El uso de espacio temporal simplifica la etapa de particionamiento, pero aumenta el consumo de memoria y la sobrecarga constante del algoritmo.

Otros algoritmos de ordenación paralela más sofisticados pueden lograr límites de tiempo aún mejores. ^{[ 25 ]} 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 paralela ) CRCW (lectura y escritura concurrentes ) con n procesadores mediante la partición implícita. ^{[ 26 ]}

Si cada pivote tiene un rango en algún lugar del 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. Elegir consistentemente tales pivotes solo tendría que dividir la lista como máximo${\displaystyle \log _{4/3}n}$veces antes de alcanzar listas de tamaño 1, lo que produce 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% central. Sin embargo, al partir de una permutación aleatoria, el pivote de cada llamada recursiva tiene un rango aleatorio en su lista y, por lo tanto, está en el 50% central aproximadamente la mitad de las veces. Imaginemos que se lanza una moneda: cara significa que el rango del pivote está en el 50% central, cruz significa que no lo está. Ahora imaginemos que la moneda se lanza una y otra vez hasta obtener k caras. Aunque esto podría llevar mucho tiempo, en promedio solo se requieren 2k lanzamientos , y la probabilidad de que la moneda no obtenga k caras después de 100k 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${\displaystyle 2\log _{4/3}n}$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 central siempre que sea un número consistente de veces.

Utilizando argumentos más cuidadosos, es posible extender esta demostración a la versión de Quicksort donde el pivote se elige aleatoriamente, para mostrar una cota de tiempo que se cumple con alta probabilidad : específicamente, para cualquier dado${\displaystyle a\geq 4}$, dejar${\displaystyle c=(a-4)/2}$, entonces con probabilidad al menos${\displaystyle 1-{\frac {1}{n^{c}}}}$, el número de comparaciones no será mayor${\displaystyle 2an\log _{4/3}n}$. ^{[ 28 ]}

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 sola llamada a quicksort implica un trabajo de 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

${\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}$

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 ² ) .

En el caso más equilibrado, una sola llamada a quicksort implica un trabajo de O ( n ) más dos llamadas recursivas en listas de tamaño n /2 , por lo que la relación de recurrencia es

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

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 demostración formal de la complejidad temporal esperada O ( n log n ) . Supongamos que no hay duplicados, ya que estos podrían manejarse con un preprocesamiento y postprocesamiento de tiempo lineal, o considerarse casos más sencillos que los analizados. Cuando la entrada es una permutación aleatoria, el rango del pivote es uniformemente aleatorio de 0 a n − 1. Entonces, las partes resultantes de la partición tienen tamaños i y n − i − 1 , e i es uniformemente aleatorio de 0 a n − 1. Por lo tanto, promediando sobre todas las posibles divisiones 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:

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

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

${\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}$

${\displaystyle nC(n)=(n+1)C(n-1)+2n-2}$

${\displaystyle {\begin{aligned}{\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}}}$

Resolviendo la recurrencia se obtiene C ( n ) = 2 n ln n ≈ 1,39 n log ₂ n .

Esto significa que, en promedio, quicksort tiene un rendimiento solo un 39 % inferior al de su mejor caso. En este sentido, se acerca más al mejor caso que al peor. Un algoritmo de ordenación por comparación no puede utilizar menos de log₂ ( _n ! ) comparaciones en promedio para ordenar n elementos (como se explica en el artículo "Ordenación por comparación ") y, en el caso de n grande , la aproximación de Stirling da como resultado log₂ ( n !) ≈ n (log₂n ₋ log₂e ) , por lo que quicksort no es mucho peor que un algoritmo de ordenación _por comparación ideal. Este rápido tiempo de ejecución promedio es otra razón del dominio práctico de quicksort sobre otros algoritmos de ordenación _.

El siguiente árbol de búsqueda binaria (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${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$formen una permutación aleatoria.

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

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

Fijar i y j < i . Los valores${\displaystyle {x_{1},x_{2},\ldots ,x_{j}}}$, una vez ordenados, defina j +1 intervalos. La observación estructural central es que${\displaystyle x_{i}}$se compara con${\displaystyle x_{j}}$en el algoritmo si y solo si${\displaystyle x_{i}}$cae dentro de uno de los dos intervalos adyacentes a${\displaystyle x_{j}}$.

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

Simplificado como el cálculo breve:

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

En lugar de particionar en dos submatrices usando un solo pivote, el quicksort multipivote (también multiquicksort ^{[ 22 ]} ) particiona su entrada en un número s de submatrices usando 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". ^{[ 34 ]} 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 número de instrucciones en un 20%, pero los resultados de la simulación sugirieron que sería más eficiente en entradas muy grandes. ^{[ 22 ]} Una versión de quicksort de doble pivote desarrollada por Yaroslavskiy en 2009 ^{[ 35 ]} resultó ser lo suficientemente rápida ^{[ 36 ]} como para justificar su implementación en Java 7 , como algoritmo estándar para ordenar arreglos de primitivos (la ordenación de arreglos de objetos se realiza utilizando Timsort ). ^{[ 37 ]} Posteriormente se descubrió que la ventaja de rendimiento de este algoritmo estaba relacionada principalmente con el rendimiento de la caché, ^{[ 38 ]} y los resultados experimentales indican que la variante de tres pivotes puede tener un rendimiento aún mejor en máquinas modernas. ^{[ 39 ] [ 40 ]}

Para archivos de disco, es posible una ordenación externa basada en particionamiento similar a quicksort. Es más lenta que la ordenación por fusión externa, pero no requiere espacio adicional en disco. Se utilizan 4 búferes, 2 para entrada y 2 para salida.${\displaystyle N=}$el número de registros en el archivo,${\displaystyle B=}$el número de registros por búfer y${\displaystyle M=N/B=}$el número de segmentos de búfer en el archivo. Los datos se leen (y se escriben) desde ambos extremos del archivo hacia adentro.${\displaystyle X}$representan los segmentos que comienzan al principio del archivo, y${\displaystyle Y}$representan segmentos que comienzan al final del archivo. Los datos se leen en el${\displaystyle X}$y${\displaystyle Y}$leer búferes. Se elige un registro pivote y los registros en el${\displaystyle X}$y${\displaystyle Y}$Los búferes distintos del registro pivote se copian al${\displaystyle X}$escribir búfer en orden ascendente y${\displaystyle Y}$escribir búfer en orden descendente según la comparación con el registro pivote. Una vez que${\displaystyle X}$o${\displaystyle Y}$El búfer se llena, se escribe en el archivo y el siguiente${\displaystyle X}$o${\displaystyle Y}$El búfer se lee 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${\displaystyle X}$búfer de escritura, el registro pivote se agrega a él y el${\displaystyle X}$Se escribe en el búfer. Si ese búfer es un${\displaystyle Y}$búfer de escritura, el registro pivote se antepone al${\displaystyle Y}$búfer y el${\displaystyle Y}$Se ha escrito el búfer. Esto constituye un paso de partición del archivo, y ahora el archivo está compuesto por dos subarchivos. Las posiciones de inicio y fin de cada subarchivo se insertan/extraen en una pila independiente o en la pila principal mediante recursión. Para limitar el espacio de la pila a${\displaystyle O(\log _{2}(n))}$El subarchivo más pequeño se procesa primero. Para una pila independiente, se insertan los parámetros del subarchivo más grande en la pila y se itera sobre el subarchivo más pequeño. Para la recursión, se procesa primero el subarchivo más pequeño y luego se itera sobre el subarchivo más grande. Una vez que un subarchivo tiene menos o igual a 4 B registros, se ordena in situ 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${\displaystyle {\frac {1+\ln(N+1)}{(4B)}}}$, pero el patrón del peor caso es${\displaystyle N}$pases (equivalentes a${\displaystyle O(n^{2})}$para la ordenación interna del peor caso). ^{[ 41 ]}

Este algoritmo es una combinación de ordenación por radix y ordenación rápida. Se elige un elemento del array (el pivote) y se considera el primer carácter (clave) de la cadena (multiclave). Los elementos restantes se dividen en tres conjuntos: aquellos cuyo carácter correspondiente es menor que, igual que y mayor que el carácter del pivote. Se ordenan recursivamente las particiones "menor que" y "mayor que" según el mismo carácter. Se ordena recursivamente la partición "igual a" según el siguiente carácter (clave). Dado que la ordenación se realiza mediante bytes o palabras de longitud W bits, el mejor caso es O ( KN ) y el peor caso O (2KN ⁾ o al menos O ( N² ) como en la ordenación rápida estándar, dado que para claves únicas N < 2K ^, K es una constante oculta en todos los algoritmos de ordenación por comparación estándar , incluida la ordenación rápida. Este es un tipo de ordenación rápida ^de tres vías en la que la partición central representa un subconjunto ordenado (trivialmente) de elementos que son exactamente iguales al pivote.

También desarrollado por Powers como un algoritmo PRAM paralelo O ( K ) . Este es nuevamente una combinación de ordenación por radix y ordenación rápida, pero la decisión de partición izquierda/derecha de la ordenación rápida se realiza en bits sucesivos de la clave, y por lo tanto es O ( KN ) para N claves de K bits. Todos los algoritmos de ordenación por comparación asumen implícitamente el modelo transdicotómico con K en Θ (log N ) , ya que si K es menor podemos ordenar en tiempo O ( N ) usando una tabla hash o ordenació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 por la ordenación rápida ni por la ordenación rápida por radix. De no ser así, todos los algoritmos de ordenación por comparación también tendrán la misma sobrecarga de examinar O ( K ) bits relativamente inútiles ^, pero la ordenación rápida por radix evitará los comportamientos del peor caso O ( N² ) de la ordenación rápida estándar y la ordenación rápida por radix, y será más rápida incluso en el mejor caso de esos algoritmos de comparación bajo estas condiciones de uniqueprefix( K ) ≫ log N. Consulte Powers ^{[ 42 ]} para obtener más información sobre las sobrecargas ocultas en la ordenación por comparación, por radix y en paralelo.

En cualquier algoritmo de ordenació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 de bifurcaciones , lo que limita el rendimiento. ^{[ 43 ]} BlockQuicksort ^{[ 44 ]} reorganiza los cálculos de quicksort para convertir las bifurcaciones impredecibles en dependencias de datos . Al particionar, la entrada se divide en bloques de tamaño moderado (que caben fácilmente en la caché de datos ), y dos matrices se llenan con las posiciones de los elementos a intercambiar. (Para evitar bifurcaciones 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 bifurcación condicional, una prueba de terminación, que generalmente se toma.

La técnica BlockQuicksort está incorporada en la implementación de la STL de C++ de LLVM , libcxx, lo que proporciona una mejora del 50 % en secuencias de enteros aleatorios. El algoritmo quicksort que evita patrones ( pdqsort ), una versión de introsort, también incorpora esta técnica. ^{[ 33 ]}

Existen varias variantes del algoritmo quicksort que separan los k elementos más pequeños o más grandes del resto de la entrada.