Hay dos métodos de partición de clasificación rápida mencionados en Cormen:

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

y:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i +1], A[r] )
return i + 1

Sin tener en cuenta el método de elegir el pivote, ¿en qué situaciones es preferible uno al otro? Sé, por ejemplo, que Lomuto se realiza relativamente mal cuando hay un alto porcentaje de valores duplicados (es decir, donde más de 2/3 la matriz tiene el mismo valor), mientras que Hoare funciona bien en esa situación.

¿Qué otros casos especiales hacen que un método de partición sea significativamente mejor que el otro?

Dimensión pedagógica

Debido a su simplicidad, el método de partición de Lomuto podría ser más fácil de implementar. Hay una bonita anécdota en la Perla de programación de Jon Bentley sobre la clasificación:

“La mayoría de las discusiones sobre Quicksort usan un esquema de partición basado en dos índices aproximados [...] [es decir, el de Hoare]. Aunque la idea básica de ese esquema es directa, siempre he encontrado los detalles difíciles: una vez pasé la mayor parte de dos días persiguiendo un error que se ocultaba en un breve ciclo de partición. Un lector de un borrador preliminar se quejó de que el método estándar de dos índices es, de hecho, más simple que el de Lomuto y esbozó un código para hacer su punto; Dejé de buscar después de encontrar dos errores ".

Dimensión de rendimiento

Para un uso práctico, la facilidad de implementación podría ser sacrificada en aras de la eficiencia. Sobre una base teórica, podemos determinar el número de comparaciones de elementos y swaps para comparar el rendimiento. Además, el tiempo real de ejecución estará influenciado por otros factores, como el rendimiento del almacenamiento en caché y las predicciones erróneas de las ramas.

Como se muestra a continuación, los algoritmos se comportan de manera muy similar en permutaciones aleatorias, excepto por el número de intercambios . ¡Allí Lomuto necesita tres veces más que Hoare!

Numero de comparaciones

$n-1$$n$

Número de intercambios

El número de intercambios es aleatorio para ambos algoritmos, dependiendo de los elementos en la matriz. Si asumimos permutaciones aleatorias , es decir, todos los elementos son distintos y cada permutación de los elementos es igualmente probable, podemos analizar el número esperado de intercambios.

$1,\ldots,n$

Método de Lomuto

$j$$A[j]$$x$$1,\ldots,n$$x-1$$x$$x-1$$x$

$\{1,\ldots,n\}$$\frac1n$

$n$

Método de Hoare

$x$

$i$$j$$x$$i$$j$

$x$

$\mathrm{Hyp}(n-1,n-x,x-1)$$n-x$$x-1$$(n-x)(x-1)/(n-1)$$x$

Finalmente, promediamos nuevamente sobre todos los valores de pivote para obtener el número total esperado de swaps para la partición de Hoare:

(Se puede encontrar una descripción más detallada en mi tesis de maestría , página 29).

Patrón de acceso a memoria

Ambos algoritmos usan dos punteros en la matriz que lo escanean secuencialmente . Por lo tanto, ambos se comportan con un almacenamiento en memoria caché casi óptimo.

Elementos iguales y listas ya ordenadas

Como ya mencionó Wandering Logic, el rendimiento de los algoritmos difiere más drásticamente para las listas que no son permutaciones aleatorias.

$n/2$

$0$$i$$j$$\mathcal O(n\log n)$

$0$A[j] <= x$i=n$$\Theta(n^2)$

Conclusión

El método de Lomuto es simple y más fácil de implementar, pero no debe usarse para implementar un método de clasificación de bibliotecas.

Algunos comentarios añadidos a la excelente respuesta de Sebastián.

Voy a hablar sobre el algoritmo de reordenamiento de partición en general y no sobre su uso particular para Quicksort .

Estabilidad

El algoritmo de Lomuto es semiestable : se preserva el orden relativo de los elementos que no satisfacen el predicado . El algoritmo de Hoare es inestable.

Patrón de acceso a elementos

El algoritmo de Lomuto se puede usar con una lista vinculada individualmente o estructuras de datos similares de solo avance. El algoritmo de Hoare necesita bidireccionalidad .

Numero de comparaciones

$n-1$$n$

Pero para hacer esto tenemos que sacrificar 2 propiedades:

1. La secuencia a particionar no debe estar vacía.
2. El algoritmo no puede devolver el punto de partición.

$n$