Estoy aprendiendo acerca de quicksort y quiero ilustrar diferentes matrices en las que quicksort tendría dificultades. El resumen rápido que tengo en mente no tiene una mezcla aleatoria inicial, hace 2 particiones y no calcula la mediana.
Pensé en tres ejemplos hasta ahora:
[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys
Por ejemplo, no estoy muy seguro de esto:
[1,3,5,7,9,10,8,6,4,2]
Entonces, ¿qué hace que una matriz con la que Quicksort tiene dificultades en comparación con una donde sea (casi) ideal?
algorithms
sorting
mrQWERTY
fuente
fuente
[2,1,2,1,2,1,2,1]y eso es todo responder). El objetivo de la pregunta sería, idealmente, que otras personas puedan venir y descubrir más sobre por qué (que tiene una respuesta) en lugar de ejemplos (de los cuales hay innumerables).Respuestas:
Cada algoritmo de clasificación tiene el peor de los casos, y en muchos casos el peor de los casos es realmente malo, por lo que vale la pena probarlo. El problema es que no existe el peor de los casos solo porque conoces el algoritmo básico.
Los peores casos comunes incluyen: ya ordenados; ordenado en reversa; casi ordenado, un elemento fuera de servicio; todos los valores son iguales; de todos modos, excepto que primero (o último) es más alto (o más bajo). Una vez tuvimos un tipo en el que el peor de los casos era un patrón de diente de sierra en particular, que era muy difícil de predecir pero bastante común en la práctica.
El peor de los casos para quicksort es uno que hace que siempre elija el peor pivote posible, de modo que una de las particiones tenga un solo elemento. Si el pivote es el primer elemento (mala elección), los datos ya ordenados o ordenados inversamente son el peor de los casos. Para una mediana de tres datos dinámicos que son todos iguales o solo el primero o el último es diferente, el truco es el truco.
Para la clasificación rápida, la complejidad promedio es nlogn y el peor de los casos es n ^ 2. La razón por la que vale la pena desencadenar el peor comportamiento es porque este también es el caso que produce la mayor profundidad de recursión. Para una implementación ingenua, la profundidad de recursión podría ser n, lo que puede desencadenar el desbordamiento de la pila. Puede ser útil probar otras situaciones extremas (incluido el mejor de los casos) por razones similares.
fuente
O(NlogN)rendimiento promedio o mejor), los casos peores y promedio tienen la misma complejidad. Eso sugiere que generalmente NO vale la pena probar el (los) peor (es) caso (s). (Dado que la prueba es probablementeO(N)... o peor)Un algoritmo escapa de la mayoría de los casos malos utilizando un pivote aleatorio, excluyendo elementos continuos equivalentes a un pivote de partición y búsqueda asimétrica. Busca hacia adelante un elemento mayor o igual a un pivote, y busca hacia atrás un elemento menor que un pivote.
Agradezco a MichaelT, la búsqueda asimétrica está diseñada para resolver [2,1,2,1,2,1,2,1].
El siguiente resultado es generado por mi función qsort_random (). N = 100,000
La mayoría de los casos son más rápidos que un patrón aleatorio. El patrón de valle es un mal caso para la mayoría de las selecciones de pivote.
qsort_log2 () escapa del caso incorrecto seleccionando un pivote en los elementos log2 (N).
qsort (3) usa la biblioteca GNU, que es un tipo de fusión de clasificación de índice.
qsort_trad () selecciona un pivote en los elementos primero, medio y último.
qsort_random () y qsort_log2 () no utilizan el intercambio.
Los programas y scripts de Source C se publican en github .
fuente