Peor de los casos la complejidad del algoritmo quicksort

Question

Buenas tardes,

Tengo una duda sobre el escenario del peor caso del algoritmo quicksort, basado en el número de comparaciones realizadas por el algoritmo, para un número dado de elementos. Esto es parte de la auto-estudio.

Por quicksort, me estoy refiriendo a un algoritmo que comienza por tomar el primer elemento de la lista inicial (el pivote; vamos a llamar a $a_1$) y los formularios de dos sublistas, la primera que contiene los elementos que están a menos de $a_1$, en el orden en que surgen, y la segunda contiene los elementos mayor que $a_1$, en el orden en que surgen. A continuación, pone a $a_1$ al final de la primera lista. Este procedimiento se repite sucesivamente de forma recursiva para cada sublista, hasta que cada sublista contiene un elemento.

Mi pregunta es: Cada una de las fuentes acerca de este tema parece estar de acuerdo en que el peor escenario es cuando la lista se ordenan ya está ordenada y el pivote es el elemento más pequeño en la lista. En este caso, el número total de comparaciones es $n(n - 1)/2$ donde $n$ es el número de elementos en la lista (por ejemplo, ver aquí: http://www.daniweb.com/software-development/cpp/threads/171145).

Pero a mí me parece que el peor caso ocurre cuando la lista está ordenada en orden decreciente y el pivote es el primer elemento en la lista, que, en este caso, sería el mayor elemento en la lista.

Por ejemplo, considere la lista de $\{4, 3, 2, 1\}$. Yo elegí el pivote como el primer elemento. Cada paso de la quicksort dividirá la lista original de la siguiente manera, de acuerdo a la descripción que me dio anteriormente:

En el primer paso, $\{4, 3, 2, 1\}$ se divide en dos listas: $\{3, 2, 1, 4\}$ (elementos menores que el pivote más el pivote anexa al final) y $\{\}$ (elementos mayores que el pivote: lista vacía). El primer paso requiere de 3 comparaciones para encontrar que 3, 2, 1 son menores que 4.

Del mismo modo, en el segundo paso, la lista de $\{3, 2, 1, 4\}$ se divide en $\{2, 1, 3\}$$\{4\}$, requiriendo 3 comparaciones (para saber que 2, 1 son más pequeños, de 3 y 4 es mayor que 3). El tercer paso se divide $\{2, 1, 3\}$ a $\{1, 2\}$$\{3\}$, requiriendo 2 comparaciones. El último paso se divide $\{1, 2\}$ a $\{1\}$$\{2\}$, requiriendo 1 comparación.

Si me suma el número de comparaciones para cada paso, me parece $3 + 3 + 2 + 1 = 9$. De hecho, si yo generalizar la situación anterior a $n$ elementos ordenados en orden decreciente, con el primer elemento como pivote, llego $n(n - 1)/2 + n - 1$ comparaciones.

Si la lista está ordenada en orden creciente $\{1, 2, 3, 4\}$ y yo elegimos el pivote a ser el elemento más pequeño de la lista (en este caso, el primer elemento), el número de comparaciones serían $n(n - 1)/2 = 4(3)/2 = 6$.

9 comparaciones es mayor que 6 comparaciones. ¿Por qué no es el peor de los casos?

Gracias de antemano.

Answer 1

Implementaciones típicas de quicksort no anexar el pivote de una de las listas. En lugar de ello, se implementan (en Haskell la notación) como

qsort [] = []
qsort xs = qsort left ++ [pivot] ++ qsort right
    where pivot = head xs
          left  = filter (<x)  xs
          right = filter (>=x) xs

que mantiene la simetría entre la izquierda y la derecha listas (si los elementos de la lista son distintos) y los resultados en el mismo número de comparaciones para una lista inicial que se ordena el aumento o la ordenada disminuyendo.

Tenga en cuenta que el "peor caso" no se encuentra sólo por las listas que están ordenados en orden creciente o ascendente. Por ejemplo, en las siguientes listas se requieren seis comparaciones para ordenar:

[1,2,3,4]
[1,2,4,3]
[1,4,2,3]
[1,4,3,2]   
[4,3,2,1]
[4,3,1,2]
[4,1,2,3]
[4,1,3,2]

En general, cualquier pedido que se traduce en el temor o mayor elemento seleccionado como el pivote en cada etapa de la recursividad le dará peor de los casos el rendimiento.

Answer 2

Creo que estás malinterpretando el algoritmo quicksort. El primer paso tipo $\{4, 3, 2,1\}$ en $$\{3, 2, 1\}, \{4\}, \{\},$$ with $\{3, 2, 1\}$ and $\{\}$ to be passed back (recursively) to the quicksort algorithm to be sorted again. The $\{4\}$ doesn't need to be sorted; the point of the first pass of the algorithm was to find the right place for the first element $4$! In the second iteration, then, you're only comparing $3$ with $2$ and $1$, for two comparisons - not three. Similarly, there's only one comparison in the third iteration ($2$ with $1$), para un total de seis comparaciones.

Generalizando, si la lista está en orden inverso, a continuación, tomará $1 + 2 + \cdots + n-1 = \frac{n(n-1)}{2}$ comparaciones, el mismo número que si la lista ya estaba ordenada. Así que ambos son peor de los casos.

---

Añadido (no es parte de la respuesta original): Chris Taylor respuesta señala que el peor de los casos de $\frac{n(n-1)}{2}$ comparaciones se produce cuando el menor o mayor elemento restante es seleccionado como el pivote en cada etapa de la recursividad, y enumera los ocho de tales permutaciones de cuatro elementos para que esto suceda.

Pregunta: Para un determinado$n$, ¿cuántas permutaciones producir el peor de los casos?

Respuesta: $2^{n-1}$.

Hay dos opciones para $\sigma(1)$ - el menor o el mayor de los elementos de la permutación. Después de $\sigma(1)$ es elegido hay dos opciones para $\sigma(2)$ - el menor o el mayor de los elementos restantes. Después de $\sigma(1)$ $\sigma(2)$ son elegidos hay dos opciones para $\sigma(3)$, y así sucesivamente, hasta llegar a $\sigma(n)$, que tiene que ser el único elemento a la izquierda. Esto le da a $2^{n-1}$ permutaciones que producen el peor de los casos.

Answer 3

En realidad, a usted y a su "fuente" son correctas. El peor caso es el caso de que le sucede a seleccionar el más grande o el más pequeño elemento como pivote. Sólo los ya ordenados caso puede ser pensado más de un "epic fail" que otros, pero de lo contrario, no importa.

El rendimiento de quicksort depende del hecho de que usted puede bisecar el array en dos proporcional en tamaño de la matriz original. Si pones sólo un número constante de los elementos de una de las partes, se obtiene complejidad cuadrática.