Какой алгоритм сортировки в постоянном пространстве наиболее эффективен?

19

Я ищу алгоритм сортировки для массивов int, который не выделяет ни одного байта, кроме размера массива, и ограничен двумя инструкциями:

  1. SWAP: поменять следующий индекс на текущий;

  2. MOVE: перемещает курсор к индексу +1 или -1;

То есть вы не можете поменять местами не соседние индексы и не поменять местами 100после того, как просто поменяли местами индексы 10. Какой алгоритм наиболее эффективен, т. Е. Тот, который использует меньшее количество полных ходов?

MaiaVictor
источник
13
Не удивительно, что это физическая машина, которая сортирует список тележек, наклеенных на скрученную ленту. Машина может только перемещать ленту вперед или назад и может менять местами только соседние карты. В реальном мире вы не можете телепортироваться, так что вот ограничения ...
MaiaVictor
2
Итак, когда вы говорите, что вам нужен алгоритм, который не выделяет ни одного байта, кроме размера массива , я полагаю, вы имеете в виду только хранение элементов, верно? Я все еще могу выделить счетчики и тому подобное?
Дархогг
5
Да, конечно. Конечно. Вы можете выделить несколько дополнительных структур. Вы даже можете выделить весь массив и выполнить много действительно сложных вычислений, что считается нулевой стоимостью. Единственное, что вам нужно минимизировать, - это количество SWAP / MOVE на реальной физической машине, потому что она медленная. Лучшее, что я мог придумать, это пузырьковая сортировка, но я предположил, что должны быть лучшие варианты.
MaiaVictor
1
Я не думаю, что есть такой алгоритм. Без какой - либо дополнительной памяти, вы не будете иметь способ хранить любое состояние элемента управления.
Рафаэль
1
@svrm: да, тогда с неограниченной оперативной памятью и возможностью копировать ленту в оперативную память и делать произвольные вычисления на ней бесплатно, алгоритм «попробуй все и примени лучше» оптимален с точки зрения количества ходов ленты. Маловероятно, чтобы это было практично, но это потому, что на практике время выполнения составляло бы миллиарды лет, а не 0 ;-) Если для копирования ленты длины N в ОЗУ потребуется N шагов, то наивная грубая сила может быть неоптимальной, но она находится в пределах N оптимального. Но ничто из этого не относится к вашей проблеме: многие проблемы, если так сформулированы, могут быть решены «в автономном режиме» с использованием фиктивного алгоритма.
Стив Джессоп

Ответы:

13

Рассмотрим сорт коктейльного шейкера , который является двунаправленной версией пузырьковой сортировки. Вы сортируете пузырьки от низкого к высокому, а затем (это добавленная часть) сортируете пузырьки от высокого к низкому, повторяйте, пока не закончите. Это по-прежнему , но в среднем оно делает значительно меньше проходов, потому что небольшие элементы около верхнего конца массива будут перемещаться в свою конечную позицию за один проход, а не за N проходов. Кроме того, вы можете отслеживать самые низкие и самые высокие позиции, где произошел обмен; последующие проходы не должны сканировать за этими точками.O(n2)

zwol
источник
4

Количество перестановок смежных элементов, необходимое для упорядочения массива, равно количеству инверсий в массиве. В общей сложности с n элементами имеется не более n * (n-1) / 2 инверсий, поэтому пузырьковая сортировка дает асимптотически оптимальное количество обменов в этой модели.

Чарльз
источник
На самом деле, пузырьковая сортировка даст точно оптимальное количество обменов. Однако для каждой перестановки существует несколько способов сделать оптимальное количество перестановок, и неясно, какой из них уменьшает общее количество ходов. (Под пузырьковой сортировкой я подразумеваю «выбрать самую большую несортированную и переместить ее в конец отсортированной»)
Петр Кравчук
4

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

Я также предполагаю, что помимо этих двух операций, мы также можем проверить, находимся ли мы в самой правой (Op 3) или самой левой позиции (Op 4), либо с помощью часовых и либо с помощью какой-либо операции в списке , Также у нас должна быть операция сравнения (Op 5), заданная отдельно или в сочетании с операцией свопинга. Если операция сравнения сочетается с операцией подкачки, то она должна сообщить нам, был ли выполнен обмен или нет.+ +

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

Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

Решение Эрика Липперта, сортировка гномов, также работает, потому что в основном это двусторонняя пузырьковая сортировка.

Shreesh
источник
Как насчет сортировки вставок?
Дархогг
Bubble sort требует как минимум двух счетчиков циклов, которые уже превышают допустимые.
Рафаэль
1
Нет, вы можете идти влево и вправо, а затем направо и налево, пока не произойдет никаких изменений (максимум n раз) без использования счетчика. Вам даже не нужно дополнительное место для логического флага, чтобы заметить, если есть изменение. Если есть изменение, вы просто переходите к другой подпрограмме, которая делает то же самое, за исключением того, что это другая подпрограмма.
Shreesh
1
И, конечно, я предполагаю, что вы можете читать пустым на обоих концах, чтобы вы могли знать, что это начало или конец списка. Кроме того, я предполагаю, что мы читаем как текущий, так и следующий элемент, чтобы узнать, нужно ли менять местами.
Shreesh
1
Или, если мы изменим оператор swap как «swap, если не в порядке возрастания».
Shreesh