Particionamiento Quicksort: Hoare vs. Lomuto

83

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?

Robert S. Barnes
fuente
2
No puedo pensar en ninguna situación en la que Lomuto sea mejor que Hoare. Parece que Lomuto realiza intercambios adicionales cada vez A[i+1] <= x. En una matriz ordenada (y dados los pivotes razonablemente elegidos) Hoare casi no cambia y Lomuto hace una tonelada (una vez que j se vuelve lo suficientemente pequeña, entonces todo lo demás A[j] <= x). ¿Qué me estoy perdiendo?
Wandering Logic
2
@WanderingLogic No estoy seguro, pero parece que la decisión de Cormen de usar la partición de Lomuto en su libro puede ser pedagógica, parece tener un bucle bastante directo.
Robert S. Barnes
2
Tenga en cuenta que esos dos algoritmos no hacen lo mismo. Al final del algoritmo de Hoare, el pivote no está en su lugar final. Puede agregar un swap(A[p], A[j])al final de Hoare para obtener el mismo comportamiento para ambos.
Aurélien Ooms
También debe verificar i < jen los 2 bucles de repetición de la partición de Hoare.
Aurélien Ooms
@ AurélienOoms El código se copia directamente del libro.
Robert S. Barnes

Respuestas:

92

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

n1n

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,,n

Método de Lomuto

jA[j]x1,,nx1xx1x

{1,,n}1n

1nx=1n(x1)=n212.

n

Método de Hoare

x

ijxij

x

Hyp(n1,nx,x1)nxx1(nx)(x1)/(n1)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:

1nx=1n(nx)(x1)n1=n613.

(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

0ijO(nlogn)

0A[j] <= xi=nΘ(n2)

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.

Sebastian
fuente
16
Wow, esa es una respuesta detallada. ¡Bien hecho!
Raphael
Tengo que estar de acuerdo con Raphael, muy buena respuesta!
Robert S. Barnes
1
Haría una pequeña aclaración, que a medida que la proporción de elementos únicos a elementos totales disminuye, la cantidad de comparaciones que hace Lomuto crece significativamente más rápido que las de Hoare. Esto probablemente se deba a una partición deficiente por parte de Lomuto y una buena partición promedio por parte de Hoare.
Robert S. Barnes
¡Gran explicación de los dos métodos! ¡Gracias!
v kouk
Puede crear fácilmente una variante del método de Lomuto que pueda extraer todos los elementos que sean iguales al pivote y dejarlos fuera de la recursión, aunque no estoy seguro de si ayudaría o dificultaría el caso promedio.
Jakub Narębski
5

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

n1n

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

Fernando Pelliccioni
fuente