java - quick - ¿Cuál es la diferencia de la clasificación rápida de doble pivote y la clasificación rápida?

quicksort c

Question

Nunca antes había visto un pivote dual de clasificación rápida. Si se trata de una edición de actualización de tipo rápido?
¿Y cuál es la diferencia de la clasificación rápida de doble pivote y la clasificación rápida?

Answer 1

Encuentro esto en el documento de Java.

El algoritmo de clasificación es un Quicksort Dual-Pivot de Vladimir Yaroslavskiy, Jon Bentley y Joshua Bloch. Este algoritmo ofrece el rendimiento O (n log (n)) en muchos conjuntos de datos que hacen que otras unidades rápidas se degraden a rendimiento cuadrático, y suele ser más rápido que las implementaciones tradicionales (de un solo pivote) Quicksort.

Luego encuentro esto en el resultado de búsqueda de google. Thoery del algoritmo de clasificación rápida:

1. Elige un elemento, llamado pivote, de la matriz.
2. Reordene la matriz de modo que todos los elementos, que son menores que el pivote, lleguen antes del pivote y que todos los elementos superiores al pivote aparezcan después (los valores iguales pueden ir en cualquier dirección). Después de esta partición, el elemento pivote está en su posición final.
3. Ordena recursivamente la sub-matriz de elementos menores y la sub-matriz de elementos mayores.

En comparación, clasificación rápida de doble pivote:

1. Para matrices pequeñas (longitud <17), use el algoritmo de ordenación de Inserción.
2. Elija dos elementos de pivote P1 y P2. Podemos obtener, por ejemplo, el primer elemento a [izquierda] como P1 y el último elemento a [derecha] como P2.
3. P1 debe ser menor que P2; de lo contrario, se intercambian. Entonces, están las siguientes partes:
   • parte I con índices de izquierda + 1 a L-1 con elementos, que son menores que P1,
   • parte II con índices de L a K-1 con elementos, que son mayores o iguales a P1 y menores o iguales a P2,
   • parte III con índices de G + 1 a la derecha-1 con elementos mayores que P2,
   • la parte IV contiene el resto de los elementos a examinar con índices de K a G.
4. El siguiente elemento a [K] de la parte IV se compara con dos pivotes P1 y P2, y se coloca en la parte correspondiente I, II o III.
5. Los punteros L, K y G se cambian en las direcciones correspondientes.
6. Los pasos 4 - 5 se repiten mientras K ≤ G.
7. El elemento de pivote P1 se intercambia con el último elemento de la parte I, el elemento de pivote P2 se intercambia con el primer elemento de la parte III.
8. Los pasos 1 - 7 se repiten recursivamente para cada parte I, parte II y parte III.

Answer 2

Para aquellos que estén interesados, observe cómo implementaron este algoritmo en Java:

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%2Cint%5B%5D%2Cint%2Cint%29

Como se indica en la fuente:

"Ordena el rango especificado de la matriz utilizando la porción de la matriz de área de trabajo dada, si es posible, para la fusión

El algoritmo ofrece el rendimiento de O (n log (n)) en muchos conjuntos de datos que hacen que otras unidades se degraden a un rendimiento cuadrático, y suele ser más rápido que las implementaciones tradicionales (de un solo pivote) de Quicksort ".