Является ли Quicksort на месте или нет?

Таким образом, эффективность пространства Quicksort равна O (log (n)). Это пространство, необходимое для поддержания стека вызовов.

Теперь, согласно странице Wikipedia на Quicksort, это квалифицируется как алгоритм на месте, поскольку алгоритм - это просто замена элементов в структуре входных данных.

Однако, согласно этой странице, эффективность пространства O (log n) исключает использование Quicksort, поскольку его эффективность пространства больше, чем O (1), Согласно этому определению любой алгоритм с эффективностью пространства больше O (1) не является на месте. Поэтому я предполагаю, что это означает, что все рекурсивные алгоритмы по определению не на месте?

Таким образом, очевидно, что здесь есть два разных определения. Википедия не всегда является полностью надежным источником, поэтому я консультировался с одним из моих профессоров.

Мой профессор согласился со вторым определением. Он сказал, что Quicksort не на месте. Несмотря на то, что данные остаются во входном массиве, дополнительное пространство, необходимое для стека, дисквалифицирует его. Мой профессор написал популярную книгу об алгоритмах, поэтому я очень уважаю его мнение, но этот ответ мне кажется не правильным.

Я считаю, что свойство места на самом деле является буквальным. Данные остаются на месте. Он не перемещается из исходной структуры данных. Для меня это определение более полезно, потому что это означает, что вы можете выполнять свой алгоритм с помощью указателей вместо того, чтобы требовать копирования данных. Это похоже на ценное свойство алгоритма и заслуживает названия "на месте".

Ответ 1

Вступление к алгоритмам от MIT Press квалифицирует QuickSort как на месте - он сортирует элементы внутри массива с максимально большим количеством их вне массива на любом заданное время.

В конце дня люди всегда будут отличаться мнениями (это напоминание сверху вниз, которое рассматривается как динамическое программирование, а не для некоторых "классических" людей), с теми, кому вы доверяете больше всего. Я доверяю редакторам и авторам в MIT Press (вместе с моим профессором, который квалифицирует его как на месте).

Как правило, проблема с QuickSort заключается не в том, что она не сортируется на месте, а в том, что она нестабильна - спутниковые данные не поддерживаются в порядке.

Edit

Точка Kuroi подчеркивает часть этого аргумента, который я считаю очень важным.

Многие утверждают, что для рекурсивных вызовов требуется O (log (n)) дополнительная память, и данные просачиваются в виде индексов в стеке, однако это незначительно для очень больших размеров N (log (1,000,000,000) = ~ 30), и он игнорирует тот факт, что обычно перемещение данных в куче занимает значительно больше, когда размер (данные) → size (index).

Индексы данных не являются самими элементами, поэтому элементы данных не хранятся вне массива, за исключением их постоянного количества (в каждом вызове).

Ответ 2

Строго говоря, Quicksort имеет пространственную эффективность O (n), так как вырожденный случай потребовал бы индекса в стеке для каждого элемента массива. Хотя в среднем это будет O (log (n)). Учитывая, что я не думаю, что вы можете назвать это алгоритмом "на месте" , если не пойти с дегенеративным определением "на месте" , что означает, что исходные данные не хранятся вне границ исходного массива (исключая операции копирования/свопинга).

Это определение "на месте" было бы вырожденным, потому что вы могли бы взять любой "неулокальный" алгоритм и заставить его удовлетворить это требование "на месте" , заставив его использовать все свои дополнительные указатели использования хранилища данных в исходном массиве, Затем, когда ответ будет найден, вы можете изменить порядок исходного массива "на месте" , используя данные указателя.

Ответ 3

qsort действительно заменяет данные на месте, но пространство стека, используемое для рекурсии, находится в log ₂ (N).

Эти два свойства не противоречат друг другу. Обычно "на месте" относится к памяти кучи, то есть к тому, что вы должны явно выделять для работы алгоритма.

Однако сложность логарифмического пространства в основном пренебрежимо мала, за исключением патологических случаев (скажем, вы хотите сделать quicksort на 8-битном микроконтроллере с 512 байтами стека:)).

Ответ 4

Все зависит от определения алгоритма "на месте" .

Если вы определяете "на месте" как требующий постоянного объема памяти, то quicksort не является "на месте" , так как для рекурсии требуется лог (N).

Если вы определяете "на месте" как более удобное для человека "не перемещает данные вне структуры ввода", то quicksort снова не "на месте" . Данные просачиваются в память в виде индексов, с которыми вызывается метод quicksort, которые необходимы для работы алгоритма. Содержимое этой дополнительной памяти напрямую зависит от ввода, как он не протекает?

Если вы определяете "на месте" как не копирование, то как насчет глупого алгоритма для поиска суммы массива: создайте еще один массив длины (n - 1) с такими элементами, как b [i] = a [ я + 1] + a [0]/n. Это своего рода копирование, хотя содержимое отличается, но содержимое этой дополнительной памяти является функцией входных данных, так же, как индексы, хранящиеся в стеке в алгоритме быстрой сортировки.

Я думаю, что определение wikipedia "на месте" является наиболее полезным, и, согласно ему, quicksort не является "на месте" , так как использует непостоянный объем памяти.