algorithm - ordenamiento - El peor caso para QuickSort: ¿cuándo puede ocurrir?

quicksort explicacion

Question

Al analizar QS, cada uno siempre se refiere al peor caso "casi ordenado". ¿Cuándo puede ocurrir tal escenario con la entrada natural?

El único ejemplo que se me ocurre es volver a indexar.

Answer 1

Creo que el peor caso para quicksort depende de la elección del elemento pivote en cada paso. Quicksort tiene su peor rendimiento, si el pivote es probablemente el más pequeño o el elemento más grande de la lista (por ejemplo, el primer o el último elemento de una lista ya ordenada).

Si, por ejemplo, usted elige el elemento medio de la lista, una lista ya ordenada no tiene el peor tiempo de ejecución.

Por lo tanto, si sospecha que su escenario es probable que tenga un escenario de caso malo para el servicio de envío rápido, simplemente puede cambiar su elección de elemento de giro para hacer que el quicksort tenga un mejor rendimiento.

Nota: sé que esto no dio más ejemplos de ocasiones en el mundo real para los peores casos de quicksort. Ejemplos de esto dependen de la implementación con la que está trabajando.

Answer 2

Creo que las personas confunden Quicksort con el algoritmo de clasificación basado en particiones y "qsort" las diversas implementaciones de la biblioteca.

Prefiero ver que el algoritmo Quicksort tenga un algoritmo de selección de pivote enchufable, que es bastante esencial para analizar su comportamiento.

Si el primer elemento siempre se elige como pivote, entonces una lista ya ordenada es el peor de los casos. A menudo hay una alta probabilidad de que la matriz ya esté / casi ordenada, por lo que esta implementación es bastante pobre.

Análogamente, seleccionar el último elemento como pivote es malo por el mismo motivo.

Algunas implementaciones intentan evitar este problema eligiendo el elemento medio como pivote. Esto no funcionaría tan mal en arreglos ya / casi ordenados, pero aún se podría construir una entrada que explotaría esta selección de pivote predecible y la haría funcionar en tiempo cuadrático.

Por lo tanto, obtiene algoritmos de selección de pivote aleatorizados, pero incluso esto no garantiza O(N log N) .

Entonces se desarrollaron otros algoritmos que usarían cierta información de la secuencia antes de elegir un pivote. Por supuesto, puede escanear toda la secuencia y encontrar la mediana, y usar eso como pivote. Esto garantiza O(N log N) , pero por supuesto más lento en la práctica.

Entonces se cortan algunas esquinas y las personas diseñan el algoritmo de la mediana de 3. Por supuesto, más tarde, incluso esto fue explotable por el llamado "asesino de mediana edad".

Por lo tanto, se realizan más intentos para llegar a algoritmos de selección de pivote más "inteligentes" que garanticen un comportamiento asintótico O(N log N) que sea lo suficientemente rápido como para ser práctico, con un grado de éxito variable.

Entonces realmente, a menos que uno especifique una implementación particular de Quicksort, la pregunta de cuándo ocurre el peor de los escenarios está mal definida. Si usa el llamado algoritmo de selección pivote de la mediana de las medianas, no hay un escenario cuadrático del peor de los casos.

La mayoría de las implementaciones de bibliotecas, sin embargo, es probable que pierdan la garantía O(N log N) para una clasificación mucho más rápida en el caso promedio. Algunas de las implementaciones realmente antiguas usan el primer elemento como pivote, que ahora se entiende bien como pobre y ya no es una práctica ampliamente seguida.

Answer 3

De Quicksort

para quicksort, "worst case" corresponde a ya ordenado

Una lista con todos los elementos, el mismo número ya está ordenado .

Answer 4

El peor caso rápido depende de elegir el elemento pivote. entonces el problema ocurre solo cuando 1) Matriz ya está ordenada en el mismo orden. 2) La matriz ya está ordenada en orden inverso. 3) Todos los elementos son iguales (caso especial de los casos 1 y 2)

Answer 5

La pregunta real era: "¿Cuándo puede ocurrir tal escenario (casi ordenado) con la entrada natural?".

Aunque todas las respuestas se refieren a "lo que causa el peor de los casos", ninguna ha cubierto "qué causa los datos que cumplen con el peor escenario de rendimiento de casos".

Entonces, para responder la pregunta real

• Error del programador : básicamente aterrizas ordenando una lista dos veces. Por lo general, esto sucede porque una lista se clasifica en un lugar en el código. Y luego, en otro fragmento de código, sabe que necesita ordenar la lista, por lo que la ordena de nuevo.

• Usando datos casi cronológicos : Usted tiene datos que generalmente se reciben en orden cronológico, pero ocasionalmente algunos elementos están fuera de posición. (Considere un entorno de subprocesos múltiples que agrega elementos con sello de tiempo a una lista. Las condiciones de carrera pueden hacer que los elementos se agreguen en un orden diferente al que se marcaron con el tiempo). En esta situación, si necesita datos ordenados, debe volver a -ordenar. Porque el orden de los datos no está garantizado.

• Agregar elementos a una lista : si tiene una lista ordenada y simplemente agrega algunos elementos (es decir, sin utilizar la inserción binaria). Debería volver a ordenar una lista casi ordenada.

• Datos de una fuente externa : si recibe datos de una fuente externa, es posible que no haya garantía de que esté ordenada. Entonces tú lo arreglas tú mismo. Sin embargo, si la fuente externa está ordenada, volverá a clasificar los datos.

• Ordenamiento natural : es similar a los datos cronológicos. Básicamente, el orden natural de los datos que recibe puede ser ordenado. Considere la posibilidad de que una compañía de seguros agregue registros de automóviles. Si la autoridad que asigna las matriculaciones de automóviles lo hace en un orden predecible, es probable que los autos más nuevos, pero no garantizados, tengan números de registro más altos. Como no está garantizado que esté ordenado, debe volver a ordenarlo.

• Datos intercalados : si recibe datos de varias fuentes ordenadas con teclas superpuestas, puede obtener claves que se parecen a las siguientes: 1 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18. Aunque la mitad de los elementos están fuera -de-secuencia con su vecino, la lista está "casi ordenada". Ciertamente, el uso de QuickSort que pivota en el primer elemento exhibiría O(n^2) rendimiento.

Conclusión

Entonces, dado todos los escenarios anteriores, en realidad es bastante fácil aterrizar ordenando datos casi ordenados. Y esta es exactamente la razón por la cual QuickSort, que pivota en el primer elemento, es la que realmente se debe evitar. polygene ha proporcionado información interesting sobre consideraciones alternativas de pivote.

Como nota al margen: uno de los algoritmos de clasificación que peor funcionan normalmente, en realidad funciona bastante bien con datos "casi ordenados". En los datos intercalados de arriba, el ordenamiento de burbuja requiere solo 9 operaciones de intercambio. Su rendimiento sería en realidad O(n) .

Answer 6

el peor caso en el tipo rápido:

1. Todos los elementos de la matriz son iguales
2. La matriz ya está ordenada en el mismo orden
3. La matriz ya está ordenada en orden inverso.