¿El qsort de stdlib es recursivo?

Question

He leído que qsort es solo un tipo genérico, sin promesas sobre la implementación. No sé cómo varían las bibliotecas de una plataforma a otra, pero suponiendo que las implementaciones de Mac OS X y Linux son muy similares, son las implementaciones qsort recursivas y/o requieren una gran cantidad de la pila?

Tengo una gran matriz (cientos de miles de elementos) y quiero ordenarla sin soplar mi pila al olvido. Alternativamente, ¿alguna sugerencia para un equivalente para matrices grandes?

Answer 1

Aquí hay una versión de BSD, los derechos de autor de Apple, presumiblemente utilizado en OS X en algún momento u otro:

http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c

Es llamada recursiva, aunque el límite superior en la profundidad de recursión es pequeña , como Blindy explica.

Aquí hay una versión de glibc, presumiblemente utilizado en los sistemas Linux en algún momento u otro:

http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c

Es no llamada recursiva. Por exactamente la misma razón por la que el límite en la recursión de llamadas es pequeño, puede usar una pequeña cantidad fija de la pila para administrar su recursión de bucle.

¿Me molestan las nuevas versiones? No ;-)

Para unos cientos de miles de elementos de matriz, incluso la implementación de llamada recursiva no llamará a más de 20 niveles de profundidad. En el gran esquema de cosas que no es profundo, excepto en dispositivos integrados muy limitados, que no tendrían suficiente memoria para tener una matriz tan grande para ordenar en primer lugar. Cuando N está limitado anteriormente, O (log N) obviamente es constante, pero más que eso es una constante bastante manejable. Por lo general, 32 o 64 veces "pequeño" es "razonable".

Answer 2

Sí, es recursivo. No, probablemente no usará grandes cantidades de pila. ¿Por qué no simplemente probarlo? La recursividad no es un tipo de bogey: es la solución preferida para muchos problemas.

Answer 3

Ya sabes, la parte recursiva es bastante profunda. En 64 niveles de recursión (que es ~ 64 * 4 = ~ 256 bytes de total de la pila) puede ordenar una matriz de tamaño ~ 2^64, es decir, una matriz tan grande como pueda en una CPU de 64 bits, que es 147573952589676412928 bytes para enteros de 64 bits. ¡Ni siquiera puedes sostenerlo en la memoria!

Preocuparse por cosas que importan.

Answer 4

Con quicksort, la pila crecerá logarítmicamente. Necesitará mucho de elementos para explotar su pila.

Answer 5

Una implementación de qsort que puede fallar en arreglos grandes está extremadamente rota. Si realmente está preocupado, iría a RTFS, pero sospecho que cualquier implementación medio decente usará un algoritmo de ordenamiento in situ o usará malloc como espacio temporal y recurrirá a un algoritmo en contexto si falla malloc.

Answer 6

Supongo que la mayoría de las implementaciones modernas de qsort realmente usan el algoritmo Introsort. Un Quicksort razonablemente escrito no volará la pila de todos modos (primero clasificará la partición más pequeña, lo que limita la profundidad de la pila al crecimiento logarítmico).

Introsort va un paso más allá - para limitar la peor de las situaciones complejas, si ve que Quicksort no está funcionando bien (demasiada recursión, por lo que podría tener O (N) complejidad) ll cambiar a un heapsort que garantiza O (N log N) complejidad y límites pila de uso, así. Por lo tanto, incluso si el Quicksort que utiliza está escrito de manera descuidada, el cambio a Heapsort limitará el uso de la pila de todos modos.

Answer 7

Recuerdo haber leído en este libro: C Programming: A Modern Approach que la especificación ANSI C no define cómo implementar qsort.

Y el libro que escribió qsort podría ser en realidad una especie de otra especie, ordenamiento por mezcla, la ordenación por inserción y por eso no la ordenación de burbuja: P

Por lo tanto, la aplicación qsort no pueden ser recursivas.

Answer 8

Una implementación correcta de qsort no requiere más que log2 (N) niveles de recursión (es decir, profundidad de la pila), donde N es el tamaño de matriz más grande en la plataforma determinada. Tenga en cuenta que este límite se aplica independientemente de lo bueno o malo el reparto pasa a ser, es decir que es el peor de los casos profundidad de recursión. Por ejemplo, en una plataforma de 32 bits, la profundidad de recursión nunca superior a 32, en el peor de los casos posibles, dada una aplicación sensata de qsort.

En otras palabras, si usted está preocupado por el uso de la pila en concreto, que no tienen nada de que preocuparse, a menos que se trata de alguna implementación extraña de baja calidad.

Answer 9

El peor de los casos el espacio-complejidad de una aplicación ingenua ordenación rápida (que sigue siendo una opción popular para qsort) es O (n). Si la aplicación se modifica para ordenar la primera optimización más pequeña arary y cola recursividad o un pila explícita e iteración se utiliza continuación el espacio peor de los casos puede reducirse a O (log N), (lo que más respuestas aquí ya escribió). Por lo tanto, no explotará su pila si la implementación de clasificación rápida no se rompe y la biblioteca no se rompió por indicadores de compilación inadecuados. Pero, por ejemplo, la mayoría de los compiladores que soportan la eliminación de la recursión de cola no harán esta optimización en compilaciones de depuración no optimizadas. Una biblioteca construida con las banderas equivocadas (es decir, no es suficiente optimización, por ejemplo, en el dominio incrustado donde a veces se construye su propia libc depuración) se puede bloquear la pila a continuación.

Para la mayoría de los desarrolladores, esto nunca será un problema (han probado libc de proveedores que tienen una complejidad de espacio O (log N)), pero diría que es una buena idea tener un ojo en posibles problemas de biblioteca tiempo al tiempo.

ACTUALIZACIÓN: He aquí un ejemplo de lo que quiero decir: un error en libc (desde 2000) donde qsort comenzaría a agotar memoria virtual porque la implementación qsort cambiaría internamente a mergesort porque aunque hay memoria suficiente para contener una matriz temporal .

http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html