Quicksort: ¿qué subparte debería ordenarse primero?

Question

estoy leyendo un texto que afirma que esta relación con el orden de los dos ordenación rápida recursiva se llama:

... es importante llamar al subproblema más pequeño primero, esto en conjunto con la recursión de cola asegura que la profundidad de la pila es log n.

No estoy del todo seguro de lo que eso significa, ¿por qué debería llamar primero a Quicksort en el subconjunto más pequeño?

Answer 1

Idealmente, la lista se divide en dos sublistas de tamaño similar. No importa mucho en qué sub-lista trabajes primero.

Pero si en un mal día la lista se divide de la forma más desequilibrada posible, una sublista de dos o tres elementos, tal vez cuatro, y una sublista casi tan larga como la original. Esto podría deberse a malas elecciones de valor de partición o datos maliciosamente inventados. Imagina lo que pasaría si primero trabajaras en la sublista más grande. La primera invocación de Quicksort mantiene los punteros/índices para la lista breve en su marco de pila mientras llama de manera recursiva al quicksort para la lista larga. Esto también se divide mal en una lista muy corta y larga, y hacemos la sublista más larga primero, repite ...

En última instancia, en el peor de los malos días con el peor de los datos maliciosos, tendremos stack marcos construidos en número proporcional a la longitud de la lista original. Este es el peor comportamiento de quicksort, O (n) profundidad de llamadas recursivas. (Tenga en cuenta que estamos hablando de la profundidad de recursión de la solución rápida, no del rendimiento.)

Al hacer la sublista más corta, primero se deshace de ella con bastante rapidez. Todavía procesamos un gran número de listas minúsculas, en proporción a la longitud original de la lista, pero ahora cada una se ocupa de una o dos llamadas recursivas. Todavía hacemos O (n) llamadas (rendimiento) pero cada una es profundidad O (1).

Answer 2

Algunos idiomas tienen recursión de cola. Esto significa que si escribe f (x) {... ... .. ... .. g (x)} entonces la llamada final, a g (x), no se implementa con una llamada de función en absoluto , pero con un salto, para que la llamada final no use ningún espacio de pila.

Quicksort divide los datos que se ordenan en dos secciones. Si siempre maneja primero la sección más corta, cada llamada que consume espacio en la pila tiene una sección de datos para ordenar que es como máximo la mitad del tamaño de la llamada recursiva que la llamó. Entonces, si comienzas con 10 elementos para ordenar, la pila en su nivel más profundo tendrá una llamada ordenando esos 10 elementos, y luego una clasificación de llamadas a lo sumo 5 elementos, y luego una clasificación de llamadas a lo sumo 2 elementos, y luego una clasificación de llamadas a lo sumo 1 elemento - y luego, para 10 elementos, la pila no puede ir más profundo - el tamaño de la pila está limitado por el registro del tamaño de los datos.

Si no se preocupó por esto, podría terminar con la pila manteniendo una llamada ordenando 10 elementos, y luego una llamada ordenando 9 elementos, y luego una llamada clasificando 8 elementos, y así sucesivamente, para que el la pila era tan profunda como la cantidad de elementos que se deben clasificar. Pero esto no puede ocurrir con la recursividad de cola si primero ordena las secciones cortas, porque aunque puede dividir 10 elementos en 1 elemento y 9 elementos, la llamada ordenando 9 elementos se hace por último y se implementa como un salto, lo que no ocurre Usa más espacio en la pila: reutiliza el espacio de la pila usado anteriormente por la persona que llama, que estaba a punto de regresar de todos modos.

Answer 3

Sorprendentemente, esto resulta ser importante incluso cuando el quicksort no se enfrenta a particiones increíblemente desequilibradas, e incluso cuando realmente se usa introsort.

Surge el problema (en C++) cuando los valores en el contenedor que se está ordenando son realmente grandes.Con esto, no quiero decir que apuntan a objetos realmente grandes, sino que son realmente grandes. En ese caso, algunos (posiblemente muchos) compiladores también harán que el marco de pila recursivo sea bastante grande, porque necesita al menos un valor temporal para realizar un intercambio. Swap se llama dentro de la partición, que no es recursiva, por lo que se podría pensar que el controlador recursivo de quicksort no requeriría el monster stack-frame; desafortunadamente, la partición generalmente termina siendo inline porque es agradable y corta, y no se llama desde ningún otro lado.

Normalmente la diferencia entre 20 y 40 monturas es despreciable, pero si los valores pesan, digamos, 8kb, entonces la diferencia entre 20 y 40 monturas podría significar la diferencia entre trabajo y desbordamiento de pila, si las pilas tienen se ha reducido en tamaño para permitir muchos hilos.

Si utiliza el algoritmo "siempre recurrente en la partición más pequeña", la pila no puede superar todos los log N marcos, donde N es el número de elementos en el vector. Además, N no puede exceder la cantidad de memoria disponible dividida por el tamaño de un elemento. Así en una máquina de 32 bits, el que podría ser sólo 2 elementos 8KB en un vector, y la profundidad llamada quicksort no podía exceder 19.

En resumen, la escritura quicksort correctamente hace su uso pila predecible (siempre que pueda predecir el tamaño de un marco de pila). No molestarse con la optimización (¡para guardar una sola comparación!) Fácilmente puede causar que la profundidad de la pila se duplique incluso en casos no patológicos, y en casos patológicos puede empeorar mucho.

Answer 4

Mire el quicksort como un árbol binario implícito. El pivote es la raíz, y los subárboles izquierdo y derecho son las particiones que creas.

Considere hacer una primera búsqueda en profundidad de este árbol. Las llamadas recursivas en realidad corresponden a hacer una primera búsqueda en profundidad en el árbol implícito descrito anteriormente. Supongamos también que el árbol siempre tiene el subárbol más pequeño como el hijo izquierdo, por lo que la sugerencia es hacer un pedido por adelantado en este árbol.

Ahora suponga que implementa el preorden utilizando una pila, donde solo inserta el elemento secundario izquierdo (pero mantiene al padre en la pila) y cuando llega el momento de presionar al hijo correcto (supongamos que mantiene un estado donde sabía un nodo ha explorado o no su hijo izquierdo), reemplaza la parte superior de la pila, en lugar de presionar al secundario derecho (esto corresponde a la parte de recursividad de la cola).

La profundidad máxima de la pila es la "profundidad izquierda" máxima: es decir, si marca cada borde yendo a un niño izquierdo como 1, y yendo a un niño derecho como 0, entonces está mirando la ruta con la suma máxima de bordes (básicamente, no se cuentan los bordes correctos).

Ahora que el subárbol izquierdo no tiene más de la mitad de los elementos, cada vez que va a la izquierda (es decir, poligonal y marca de borde 1), está reduciendo la cantidad de nodos restantes para explorar al menos la mitad.

Por lo tanto, la cantidad máxima de bordes marcados con 1 que ve no es más que log n.

Por lo tanto, el uso de la pila no es más que log n, si siempre elige la partición más pequeña, y usa recursividad final.