размер стека быстрой сортировки

Question

Почему мы предпочитаем сортировать меньший раздел файла и помещать больший в стек после разбиения для быстрой сортировки (нерекурсивная реализация)?Это уменьшает сложность пространства быстрой сортировки O (log n) для случайных файлов.Может ли кто-нибудь это уточнить?

Answer 1

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

Поскольку тот, с кем вы продолжаете работать, меньше, он в два раза меньше того, с которым вы работали раньше. Таким образом, для каждого диапазона, который мы помещаем в стек, мы делим пополам размер диапазона, с которым работаем.

Это означает, что мы не можем поместить более чем log n диапазонов в стек до того, как диапазон, с которым мы работаем, достигнет размера 1 (и, следовательно, будет отсортирован). Это ограничивает количество стека, необходимое для завершения первого спуска.

Когда мы начинаем обрабатывать «большие части», каждая «большая часть» B (k) больше, чем «малая часть» S (k), создаваемая в одно и то же время, поэтому нам может понадобиться больше стека для обработки B ( k) чем нам нужно было справиться с S (k). Но B (k) все еще меньше, чем предыдущая «малая часть», S (k-1), и как только мы обрабатываем B (k), , мы убрали его из стека , что следовательно, на один элемент меньше, чем при обработке S (k), и того же размера, что и при обработке S (k-1). Таким образом, у нас все еще есть наша граница.

Предположим, мы сделали это наоборот - нажмите на маленькую часть и продолжайте работать с большой частью. Затем в патологически неприятном случае мы каждый раз помещаем в стек диапазон 1 и продолжаем работать с размером всего на 2 меньше, чем предыдущий. Следовательно, нам потребуется n / 2 слотов в нашем стеке.

Answer 2

Рассмотрим наихудший случай, когда вы делите раздел таким образом, что ваш раздел равен 1: n. Если вы сначала сортируете маленький субфайл, вам нужно использовать только пробел O (1), когда вы толкаете большой субфайл, а затем извлекаете его обратно (а затем снова толкаете большой субфайл). Но если вы сначала сортируете большой подфайл, чем вам нужно пространство O (N), потому что вы продолжаете помещать в стек массив из 1 элемента.

Вот цитата из «Алгоритмов» Роберта Седжевика (именно он написал статью об этом):

Для быстрой сортировки - сочетание удаления конечной рекурсии и политики обработки меньшего из двух подфайлов сначала оказывается убедитесь, что в стеке достаточно места только для, lg N записей, так как каждая запись в стеке после верхней должна представлять подфайл меньше половины размера предыдущей записи.

Answer 3

Хорошо, я прав, что вы имеете в виду, что если мы сделаем алгоритм быстрой сортировки нерекурсивным, вам придется использовать стек, в который вы помещаете разделы в стек?

Если так: алгоритм должен выделять каждую переменную, которую он использует в памяти. Таким образом, если вы запускаете два экземпляра этого параллельно, они выделяют двойной объем одного пространства памяти алгоритма ...

Теперь в рекурсивной версии вы запускаете новый экземпляр алгоритма (который должен выделять память), НО экземпляр, который вызывает рекурсивный, НЕ заканчивается, поэтому выделенная память необходима! -> на самом деле мы начали, скажем, 10 рекурсивных экземпляров и нам нужно 10 * X памяти, где X - память, необходимая для одного экземпляра.

Теперь мы используем нерекурсивный алгоритм. Вы ДОЛЖНЫ выделить только необходимую память ОДИН РАЗ. На самом деле вспомогательные переменные используют только пространство одного экземпляра. Чтобы выполнить функцию алгоритма, мы должны сохранить уже созданные разделы (или то, что мы еще не сделали). Фактически, мы помещаем его в стек и удаляем разделы, пока не сделаем последний шаг «рекурсии». Итак, представьте: вы даете алгоритму массив. Рекурсивный алгоритм должен распределять весь массив и несколько вспомогательных переменных для каждого экземпляра (опять же: если глубина рекурсии равна 10, нам нужно 10 * X памяти, где массиву нужно много). Нерекурсивному нужно выделять массив, вспомогательные переменные только один раз, НО ему нужен стек. Однако, в конце концов, вы не будете помещать в стек столько частей, что рекурсивному алгоритму потребуется меньше памяти из-за той части, которой нам не нужно повторно выделять массив каждый раз / экземпляр.

Надеюсь, я описал это так, чтобы вы могли понять это, но мой английский не очень хорош. :)