Является ли stdlib qsort рекурсивным?

Question

Я читал, что qsort - это просто общий вид, без обещаний о реализации.Я не знаю, как библиотеки варьируются от платформы к платформе, но при условии, что реализации Mac OS X и Linux в целом схожи, являются qsort реализациями рекурсивными и / или требуют много стека ?

У меня есть большой массив (сотни тысяч элементов), и я хочу отсортировать его, не взорвав свой стек.В качестве альтернативы, какие-либо предложения для эквивалента для больших массивов?

Answer 1

Вот версия от BSD, авторское право Apple, предположительно используемая в OS X в то или иное время:

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

Это рекурсивный вызов, хотя верхняя граница глубины рекурсии мала, как объясняет Блинди.

Вот версия от glibc, предположительно используемая в системах Linux в то или иное время:

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

Это не вызов рекурсивно. По той же причине, по которой ограничение на рекурсию вызова невелико, он может использовать небольшой фиксированный объем стека для управления своей рекурсией цикла.

Можно ли поискать последние версии? Нет; -)

Для нескольких сотен тысяч элементов массива даже рекурсивная реализация вызова не вызовет глубину более 20 уровней. В большой схеме вещей, которая не является глубокой, за исключением очень ограниченных встроенных устройств, у которых не было бы достаточно памяти, чтобы вы могли иметь массив, который можно было бы сортировать в первую очередь. Когда N ограничено сверху, O (log N), очевидно, является константой , но более того, обычно это вполне управляемая константа. Обычно 32 или 64 раза «маленький» является «разумным».

Answer 2

Знаете, рекурсивная часть глубоко вошла. В 64 уровнях рекурсии (что составляет ~ 64 * 4 = ~ 256 байт от общего количества стека) вы можете отсортировать массив размером ~ 2 ^ 64, то есть массив, который вы можете адресовать на 64-битном процессоре, который равен 147573952589676412928 байты для 64-битных целых чисел. Вы даже не можете держать это в памяти!

Беспокойство о вещах, которые важны для меня.

Answer 3

Да, это рекурсивно. Нет, он, вероятно, не будет использовать большое количество стека. Почему бы просто не попробовать? Рекурсия - это не призрак, а решение для многих проблем.

Answer 4

Правильно реализованная qsort не требует более чем log2 (N) уровней рекурсии (т. Е. Глубина стека), где N - наибольший размер массива на данной платформе. Обратите внимание, что этот предел применяется независимо от того, насколько хорошим или плохим является разделение, т. Е. Это глубина рекурсии наихудший случай . Например, на 32-битной платформе глубина рекурсии никогда не превысит 32 в худшем из возможных случаев, учитывая нормальную реализацию qsort.

Другими словами, если вас особенно беспокоит использование стека, вам не о чем беспокоиться, если только вы не имеете дело с какой-то странной некачественной реализацией.

Answer 5

Я помню, как читал в этой книге: C Программирование: современный подход что спецификация ANSI C не определяет, как реализовать qsort.

И в книге написано, что qsort на самом деле может быть другим видом сортировки, сортировки слиянием, сортировки вставкой и почему бы не пузырьковая сортировка: P

Итак, реализация qsort может быть нерекурсивной.

Answer 6

Я полагаю, что большинство современных реализаций qsort на самом деле используют алгоритм Introsort. Достаточно написанный Quicksort в любом случае не снесет стек (сначала он отсортирует меньший раздел, что ограничит глубину стека логарифмическим ростом).

Интросорт идет еще дальше - чтобы ограничить сложность наихудшего случая, если он обнаружит, что Quicksort не работает хорошо (слишком много рекурсии, поэтому он может иметь сложность O (N ² )) , он переключится на Heapsort, который гарантирует O (N log ₂ N), сложность и также ограничивает использование стека. Поэтому, даже если используемая им быстрая сортировка написана небрежно, переключение на Heapsort все равно ограничит использование стека.

Answer 7

При быстрой сортировке стек будет расти логарифмически.Вам понадобится много элементов, чтобы взорвать ваш стек.

Answer 8

Пространственная сложность наивной реализации быстрой сортировки (которая по-прежнему популярна для qsort) в худшем случае - это O (N). Если , то реализация модифицируется для сортировки меньшего размера сначала для и оптимизации хвостовой рекурсии или явного стека и используется итерация , а затем может быть занесено пространство в худшем случае. вплоть до O (журнал N), (что большинство ответов здесь уже писал). Таким образом, вы не взорвете свой стек, если реализация быстрой сортировки не нарушена и библиотека не была нарушена неправильными флагами компилятора. Но, например, большинство компиляторов, которые поддерживают устранение хвостовой рекурсии, не будут выполнять эту оптимизацию в неоптимизированных сборках отладки. Библиотека, созданная с неправильными флагами (т. Е. Недостаточно оптимизация, например, во встроенном домене, где вы иногда создаете свой собственный отладочный libc), может привести к сбою стека.

Для большинства разработчиков это никогда не будет проблемой (у них есть протестированные поставщиком библиотеки libc, которые имеют O (log N) пространство сложности), но я бы сказал, что это хорошая идея, чтобы взглянуть на потенциальные проблемы с библиотекой времени ко времени.

ОБНОВЛЕНИЕ: Вот пример того, что я имею в виду: ошибка в libc (с 2000 года), когда qsort начинал перебивать виртуальную память, потому что реализация qsort внутренне переключалась бы на mergesort, потому что в ней достаточно памяти для хранения временного массива.

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

Answer 9

Реализация

A qsort, которая может давать сбой на больших массивах, крайне нарушена.Если вы действительно беспокоитесь, я бы выбрал RTFS, но я подозреваю, что любая полуприличная реализация будет либо использовать алгоритм сортировки на месте, либо использовать malloc для временного пробела, либо использовать алгоритм на месте, если mallocтерпит неудачу.