Estoy tratando de entender por qué el ordenamiento rápido usando la partición Lomuto y un pivote fijo funciona de manera errática, pero en general deficiente, en entradas generadas aleatoriamente. Estoy pensando que aunque las entradas se generan aleatoriamente, puede haber mucho orden en las secuencias, pero no estoy seguro de cómo medir el nivel de desorden en las secuencias. Pensé en usar el número de inversiones, pero vi en esta otra pregunta que pregunté que realmente no es una buena medida en este caso.
La razón por la que sospecho que mis secuencias aleatorias tienen mucho "orden" es que aleatorizar el pivote soluciona el problema de rendimiento. Pero, en teoría, no debería haber ningún problema de rendimiento en estas secuencias de entrada supuestamente "aleatorias".
fuente
Respuestas:
La
partición Lomuto vs Hoare Lomuto sufre al ordenar claves iguales, mientras que la partición Hoare no.
Ambos esquemas de partición sufren igualmente cuando se usa un pivote distante de la mediana.
Medida del desorden
La medida del desorden para elegir con el propósito de clasificación rápida es simple.
R: ¿Qué tan lejos de la mediana está el pivote fijo, en comparación con los datos aleatorios?
Si insiste en usar la partición de Lomuto y asume que los valores duplicados están permitidos, debe agregar la siguiente prueba contra la aleatoriedad:
B: ¿Cuántos elementos duplicados hay en comparación con los aleatorios?
Por supuesto, es bastante tonto suponer que se permiten valores duplicados en su conjunto de datos y todavía evaluar la partición de Lomuto, por lo que probablemente debería eliminar los duplicados de antemano o cambiar a la partición Hoare o asumir que los duplicados son raros.
Ambas medidas son triviales para cuantificar usando estadísticas.
Podemos descartar datos patológicos.
Cualquier otra desviación de la aleatoriedad no será importante para analizar el ordenamiento rápido. Mientras el pivote esté cerca de la mediana, funcionará bien en todos los datos que no sean patológicos.
La distancia desde el azar tendría que ser grande para ser patológica rápida, por lo que podemos descartarlo.
Nunca use ningún pivote fijo en el código real
. Tenga en cuenta que si escribe código real con un pivote fijo *) (cualquiera que sea ese pivote), se está abriendo a un ataque de denegación de servicio, porque un atacante puede insertar un valor patológico justo en ese punto y, por lo tanto, siempre debe elegir un elemento aleatorio como pivote.
*) o múltiples pivotes si elige el mejor de los pivotes x.
fuente