algorithm - complexity - quicksort animation
Clasificación rápida Peor caso (5)
Estoy trabajando en el programa que acabo de necesitar para comprenderlo mejor.
¿Cuál es el peor tiempo de ejecución de Quicksort y qué puede causar este peor rendimiento de caso? ¿Cómo podemos modificar el programa quicksort para mitigar este problema?
Sé que tiene el peor caso O(n^2) y sé que ocurre cuando el pivote único elemento mínimo o máximo. Mi pregunta es cómo puedo modificar el programa para mitigar este problema.
Un buen algoritmo será bueno.
El peor tiempo de ejecución del caso depende del método de partición en quick-sort. Eso tiene dos aspectos:
- seleccionando el pivote
- cómo dividir alrededor del pivote
Las buenas estrategias para seleccionar el pivote se han desglosado en publicaciones anteriores (mediana de medianas, mediana de tres o aleatorización). Pero incluso si el pivote se selecciona sabiamente, en el extremo, si una matriz tiene todos los elementos iguales, dará lugar al peor tiempo de ejecución si solo se crean dos particiones, porque una llevará los elementos iguales, es decir, todos los elementos:
- esto hace que la partición se llame n veces, tomando cada una de ellas n / 2 en promedio, llevando a O (n²)
- esto no es bueno, porque no es el peor escenario teórico, sino bastante común
- tenga en cuenta que no se soluciona detectando la partición vacía, porque el pivote podría tener el valor más alto o más bajo del elemento (por ejemplo, la mediana es 5, que también es el valor más alto del elemento, pero aún puede haber algunos valores <5 fuera de lugar)
Una forma de evitar este problema es dividir en tres particiones, una inferior (elementos <pivote), una igual (elementos = pivote) y una partición superior. Los "= elementos pivotantes" están en su posición final. Las particiones inferior y superior aún deben ordenarse si no están vacías.
Junto con la aleatorización, la mediana de las medianas o alguna combinación para seleccionar un pivote, el peor de los casos es bastante raro pero no imposible, lo que deja al algoritmo con un límite superior en el peor caso de O (n²).
El rendimiento de Quicksort depende de su algoritmo de selección de pivote. El algoritmo de selección de pivote más ingenuo es simplemente elegir el primer elemento como pivote. Es fácil ver que esto da como resultado el peor comportamiento posible si sus datos ya están ordenados (el primer elemento siempre será el mínimo).
Hay dos algoritmos comunes para resolver este problema: elegir aleatoriamente un pivote o elegir la mediana de tres. Aleatorio es obvio, así que no entraré en detalles. La mediana de tres implica seleccionar tres elementos (generalmente el primero, el medio y el último) y elegir la mediana de esos como el pivote.
Dado que los generadores de números aleatorios son típicamente pseudoaleatorios (por lo tanto deterministas) y una mediana no aleatoria de tres algoritmos es determinista, es posible construir datos que resulten en el peor de los casos, sin embargo, es raro que surjan en el uso normal.
También debe considerar el impacto en el rendimiento. El tiempo de ejecución de su generador de números aleatorios afectará el tiempo de ejecución de su quicksort. Con la mediana de tres, está aumentando el número de comparaciones.
Ha pasado un tiempo, pero creo que el peor caso para quicksort fue cuando los datos ya estaban ordenados. Una verificación rápida para ver si los datos ya están ordenados podría ayudar a aliviar este problema.
Una modificación fácil es elegir el pivote aleatoriamente. Esto da buenos resultados con alta probabilidad .
La peor condición de rendimiento:
Cuando cada pivote elegido es ''más grande'' o ''más pequeño'', este patrón se repite
Entonces para 1 3 5 4 2
Si los pivotes se eligen por orden 1,2,3,4,5 o 5,4,3,2,1
entonces el peor tiempo de ejecución del caso es O (n * n)
Cómo evitar el peor de los casos:
(1) Divida la matriz en cinco conjuntos. Así que si 1..100 los conjuntos son (1..20) (21..40) (41..60) (61..80) (81..100)
(2) Elija la mediana de los primeros cinco elementos en cada conjunto de modo que (3) (23) (43) (63) (83)
(3) Ahora elija la mediana entre ellos como pivote, así que aquí está (43)