Quicksort на месте или нет?
Таким образом, пространственная эффективность быстрой сортировки равна O(log(n)). Это пространство, необходимое для поддержки стека вызовов.
Теперь, согласно странице Википедии на Quicksort, это квалифицируется как алгоритм на месте, так как алгоритм просто меняет элементы внутри структуры входных данных.
Однако, согласно этой странице, эффективность пространства O(log n) дисквалифицирует быструю сортировку, поскольку ее эффективность пространства больше, чем O(1). Согласно этому определению, любой алгоритм с пространственной эффективностью, превышающей O (1), не применяется. Итак, я предполагаю, что это означает, что все рекурсивные алгоритмы по определению не существуют?
Очевидно, что здесь есть два разных определения. Википедия не всегда является полностью надежным источником, поэтому я посоветовался с одним из моих профессоров.
Мой профессор согласился со вторым определением. Он сказал, что Quicksort не на месте. Даже если данные остаются во входном массиве, дополнительное пространство, необходимое для стека, дисквалифицирует его. Мой профессор написал популярную книгу по Алгоритмам, поэтому я очень уважаю его мнение, но этот ответ просто не кажется мне правильным.
Я вижу свойство in-place как буквальное. Данные остаются на месте. Он не движется от своей первоначальной структуры данных. Для меня это определение более полезно, потому что оно означает, что вы можете выполнять свой алгоритм с указателями вместо того, чтобы требовать от вас копирования данных. Это кажется ценным свойством алгоритма и достойно названия "на месте".
4 ответа
Введение в алгоритмы из MIT Press квалифицирует QuickSort как " на месте" - она сортирует элементы в массиве с не более чем постоянным количеством их вне массива в любой момент времени.
В конце концов, у людей всегда будут разные мнения (считается ли динамическая программирование нисходящей мемоизацией? Не для некоторых "классических" людей), на стороне того, кому вы доверяете больше всего. Я доверяю редакторам и авторам MIT Press (вместе с моим профессором, который квалифицирует его как "на месте").
Как правило, проблема с быстрой сортировкой заключается не в том, что она не сортируется на месте, а в том, что она нестабильна - спутниковые данные не хранятся в порядке.
редактировать
Точка зрения Курои подчеркивает часть этого аргумента, я думаю, что это очень важно.
Многие утверждают, что это требует O(log(n)) дополнительной памяти для рекурсивных вызовов, и данные просачиваются в виде индексов в стеке, однако это незначительно для очень больших размеров N (log(1,000,000,000) =~ 30) и игнорирует тот факт, что обычно перемещение данных в куче занимает гораздо больше времени, когда размер (данные) >> размер (индекс).
Индексы данных не являются самими элементами, поэтому элементы данных не хранятся вне массива, кроме как их постоянного количества (в каждом вызове).
Строго говоря, Quicksort обладает пространственной эффективностью O(n), поскольку для вырожденного случая потребуется индекс в стеке для каждого элемента массива. Хотя в среднем это будет O(log(n)). Учитывая, что я не думаю, что есть какой-то способ, которым вы могли бы назвать его алгоритмом "на месте", если только вы не используете вырожденное определение "на месте", означающее, что исходные данные не сохраняются за пределами границ исходного массива (исключая операции копирования / обмена).
Это определение "на месте" было бы вырожденным, потому что вы могли бы взять любой алгоритм "не на своем месте" и заставить его удовлетворить это требование "на месте", если бы он использовал все свои дополнительные указатели использования хранилища данных для исходного массива. Затем, когда ответ найден, вы можете изменить порядок исходного массива "на месте", используя данные указателя.
qsort действительно меняет данные на месте, но пространство стека, используемое для рекурсии, находится в журнале2(N).
Эти два свойства не противоречат друг другу. Обычно "на месте" относится к куче памяти, то есть к тому, что вы должны явно выделить для работы алгоритма.
Однако сложность логарифмического пространства в основном не учитывается, за исключением патологических случаев (скажем, вы хотите выполнить быструю сортировку на 8-битном микроконтроллере с 512 байтами стека:)).
Все зависит от определения "на месте" алгоритма.
Если вы определяете "на месте" как требующий постоянного объема памяти, то быстрая сортировка не является "на месте", так как для рекурсии требуется память журнала (N).
Если вы определяете "на месте" как более дружественный человеку "не перемещает данные за пределы входной структуры", то быстрая сортировка снова не "на месте". Данные просачиваются в память в виде индексов, с помощью которых вызывается метод быстрой сортировки, которые необходимы для работы алгоритма. Содержимое этой дополнительной памяти напрямую зависит от ввода, как оно не протекает?
Если вы определяете "на месте" как не копирующий, то как насчет глупого алгоритма для нахождения суммы массива: создайте еще один массив длины (n - 1) с такими элементами, как b[i] = a[i + 1] + a[0] / n. Это своего рода копирование, хотя содержимое отличается, но содержимое этой дополнительной памяти является функцией входных данных, так же как индексы, хранящиеся в стеке в алгоритме быстрой сортировки.
Я думаю, что определение "на месте" в Википедии является наиболее полезным, и в соответствии с ним быстрая сортировка не является "на месте", поскольку она использует непостоянный объем памяти.