Сортировка на месте

Ответ 1

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

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

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

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

Возвращаясь к сортировке, преимущества перестановки "на месте" становятся еще более очевидными, когда вы думаете о стопках перфокарт - предпочтительно избегать копирования перфокарт только для их сортировки.

Некоторые алгоритмы сортировки допускают такой стиль работы на месте, а другие - нет.

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

По этой причине обычное определение определения на месте требует достижения определенного стандарта эффективности использования пространства. Абсолютно недопустимо использовать дополнительное пространство, пропорциональное вводу (то есть O (n) дополнительное пространство), и все же называть ваш алгоритм "на месте".

На странице Википедии об алгоритмах на месте в настоящее время утверждается, что алгоритм на месте может использовать только постоянное количество - O (1) - дополнительного пространства.

В компьютерных науках алгоритм на месте (или на латыни in situ) - это алгоритм, который преобразует входные данные с использованием структуры данных с небольшим постоянным объемом дополнительного пространства для хранения.

В разделе " В вычислительной сложности" указаны некоторые технические детали, но все же делается вывод, что, например, для быстрой сортировки требуется O (log n) пробел (true) и, следовательно, он не на месте (что я считаю ложным).

O (log n) намного меньше, чем O (n) - например, основание 2 log 16 777 216 равно 24.

Quicksort и heapsort обычно считаются на месте, и heapsort может быть реализован с O (1) дополнительным пространством (я ошибся об этом ранее). Mergesort сложнее реализовать на месте, но неуместная версия очень дружественна кешу - я подозреваю, что в реальных реализациях допускаются затраты пространства O (n) - оперативная память дешевая, но пропускная способность памяти является основным узким местом, поэтому обмен памятью на эффективность и скорость кеширования часто является выгодной сделкой.

[ РЕДАКТИРОВАТЬ Когда я писал выше, я предполагаю, что я думал о сортировке массива на месте слияния. Сортировка на месте связанного списка очень проста. Основное различие заключается в алгоритме слияния - объединить два связанных списка без копирования или перераспределения легко, сделать то же самое с двумя подмассивами большого массива (и без O (n) вспомогательного хранилища) AFAIK нет.]

Быстрая сортировка также эффективна в кеше, даже на месте, но может быть дисквалифицирована как алгоритм на месте, обращаясь к ее наихудшему поведению. Существует вырожденный случай (в нерандомизированной версии, как правило, когда входные данные уже отсортированы), когда время выполнения равно O (n ^ 2), а не ожидаемому O (n log n). В этом случае дополнительное пространство также увеличивается до O (n). Тем не менее, для больших наборов данных и с некоторыми основными мерами предосторожности (главным образом, рандомизированным выбором сводных данных) это худшее поведение становится невероятно маловероятным.

Мое личное мнение состоит в том, что O (log n) дополнительное пространство приемлемо для алгоритмов на месте - это не обман, поскольку это не разрушает исходную точку работы на месте.

Тем не менее, мое мнение, конечно, только мое мнение.

Еще одно примечание - иногда люди будут вызывать функцию на месте просто потому, что она имеет один параметр как для ввода, так и для вывода. Из этого не обязательно следует, что функция занимала мало места, что результат был получен путем преобразования ввода или что параметр все еще ссылается на ту же область памяти. Это использование не является правильным (или так утверждают предписатели), хотя оно достаточно распространено, чтобы лучше знать, но не волноваться об этом.

Ответ 2

Я не думаю, что эти термины тесно связаны:

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

Естественное упорядочение - это термин, который описывает, как можно упорядочить полные объекты. Например, вы можете сказать, что 0 меньше 1 (естественное упорядочение для целых чисел) или что A до B в алфавитном порядке (естественный порядок для строк). Вы вряд ли можете сказать, что Боб больше или меньше, чем Алиса вообще, поскольку он сильно зависит от конкретных атрибутов (в алфавитном порядке по имени, по возрасту, по доходам...). Поэтому для людей нет естественного порядка.

Ответ 3

Сортировка на месте сортирует без необходимости в дополнительном пространстве. Согласно wiki, он говорит

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

Quicksort является одним из примеров сортировки на месте.

Ответ 4

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

Ответ 5

это можно сделать, используя функцию swap, вместо создания целой новой структуры мы реализуем этот алгоритм, даже не зная его имени: D