Observación del comportamiento cuadrático con quicksort - O (n^2)

Question

El algoritmo quicksort tiene una complejidad de tiempo promedio de O (n * log (n)) y la peor complejidad de O (n^2).

Suponiendo alguna variante del algoritmo quicksort de Hoare, ¿qué tipo de entrada hará que el algoritmo de quicksort muestre la peor de las complicaciones?

Indique cualquier suposición relacionada con los detalles de implementación con respecto al algoritmo específico de la solución rápida, como la selección de pivote, etc., o si proviene de una biblioteca comúnmente disponible, como libc.

Algunos lectura:

1. A Killer Adversary for Quicksort
2. Quicksort Is Optimal
3. Engineering a Sort Function
4. Introspective Sorting and Selection Algorithms

Answer 1

Los Quick sort realiza peor es decir, a O (n^2) cuando todos los valores de el pivote elegido es el más grande o el más pequeño de la t aken set. Considera este ejemplo.

El pivote elegido es decir 1, tendrá 4 elementos en el lado derecho del pivote y no hay elementos en el lado izquierdo. Aplicando esta misma lógica de forma recursiva y el pivote elegido es 2, 3, 4, 5 respectivamente, hemos alcanzado una situación en la que este tipo se ha realizado en el peor momento posible.

Se ha recomendado y probado que Quicksort funciona bien si la entrada se baraja bien.

Además, la selección de un género generalmente depende de un conocimiento claro sobre el dominio de entrada. Por ejemplo, si la entrada es enorme, hay algo llamado como clasificación externa que puede usar memoria externa. Si el tamaño de entrada es muy pequeño, podemos ir a un tipo de fusión, pero no para conjuntos de entrada medianos y grandes, ya que utiliza memoria extra. La principal ventaja de la clasificación rápida es su significado "in situ", es decir, no se utiliza memoria adicional para los datos de entrada. Su peor momento en el papel es O (n^2) pero aún así es ampliamente preferido y utilizado. Mi punto aquí es que los algoritmos de clasificación se pueden cambiar en función del conocimiento del conjunto de entrada y es una cuestión de preferencia.

Answer 2

Para ampliar lo que dijo Bragboy, en lugar de solamente ejecutando:

quicksort(array); 

Run:

shuffle(array); 
quicksort(array); 

Cuando la definición de shuffle() podrían ser:

shuffle(array){ 
    for(int i = array.length; i > 0; i--){ 
     r= random number % i; 
     swap(array[i], array[r]); 
    } 
} 

Si lo hace, , probablemente, trate con el caso de obtener entrada que hace que quicksort() sea lento.

Answer 3

El algoritmo Quicksort de Hoare elige un pivote aleatorio. Para obtener resultados reproducibles, sugeriría la modificación de Scowen que, entre otras cosas, elige el artículo medio de la entrada.Para esta variante, un patrón de diente de sierra con el pivote siendo el más pequeño parece ser la peor entrada de caso:

starting with   { j i h g f a e d c b } 
compare 1 to 6   { (j) i h g f (a) e d c b } 
compare 6 to 10   { j i h g f (a) e d c (b) } 
compare 6 to 9   { j i h g f (a) e d (c) b } 
compare 6 to 8   { j i h g f (a) e (d) c b } 
compare 6 to 7   { j i h g f (a) (e) d c b } 
swap 1<=>6    { (a) i h g f (j) e d c b } 
compare 1 to 5   { (a) i h g (f) j e d c b } 
compare 1 to 4   { (a) i h (g) f j e d c b } 
compare 1 to 3   { (a) i (h) g f j e d c b } 
compare 1 to 2   { (a) (i) h g f j e d c b } 
compare 2 to 6   { a (i) h g f (j) e d c b } 
compare 3 to 6   { a i (h) g f (j) e d c b } 
compare 4 to 6   { a i h (g) f (j) e d c b } 
compare 5 to 6   { a i h g (f) (j) e d c b } 
compare and swap 6<=>10 { a i h g f (b) e d c (j) } 
compare 7 to 10   { a i h g f b (e) d c (j) } 
compare 8 to 10   { a i h g f b e (d) c (j) } 
compare 9 to 10   { a i h g f b e d (c) (j) } 
compare 2 to 6   { a (i) h g f (b) e d c j } 
compare 6 to 9   { a i h g f (b) e d (c) j } 
compare 6 to 8   { a i h g f (b) e (d) c j } 
compare 6 to 7   { a i h g f (b) (e) d c j } 
swap 2<=>6    { a (b) h g f (i) e d c j } 
compare 2 to 5   { a (b) h g (f) i e d c j } 
compare 2 to 4   { a (b) h (g) f i e d c j } 
compare 2 to 3   { a (b) (h) g f i e d c j } 
compare 3 to 6   { a b (h) g f (i) e d c j } 
compare 4 to 6   { a b h (g) f (i) e d c j } 
compare 5 to 6   { a b h g (f) (i) e d c j } 
compare and swap 6<=>9 { a b h g f (c) e d (i) j } 
compare 7 to 9   { a b h g f c (e) d (i) j } 
compare 8 to 9   { a b h g f c e (d) (i) j } 
compare 3 to 6   { a b (h) g f (c) e d i j } 
compare 6 to 8   { a b h g f (c) e (d) i j } 
compare 6 to 7   { a b h g f (c) (e) d i j } 
swap 3<=>6    { a b (c) g f (h) e d i j } 
compare 3 to 5   { a b (c) g (f) h e d i j } 
compare 3 to 4   { a b (c) (g) f h e d i j } 
compare 4 to 6   { a b c (g) f (h) e d i j } 
compare 5 to 6   { a b c g (f) (h) e d i j } 
compare and swap 6<=>8 { a b c g f (d) e (h) i j } 
compare 7 to 8   { a b c g f d (e) (h) i j } 
compare 4 to 6   { a b c (g) f (d) e h i j } 
compare 6 to 7   { a b c g f (d) (e) h i j } 
swap 4<=>6    { a b c (d) f (g) e h i j } 
compare 4 to 5   { a b c (d) (f) g e h i j } 
compare 5 to 6   { a b c d (f) (g) e h i j } 
compare and swap 6<=>7 { a b c d f (e) (g) h i j } 
compare and swap 5<=>6 { a b c d (e) (f) g h i j }