Я ищу алгоритм сортировки для массивов int, который не выделяет ни одного байта, кроме размера массива, и ограничен двумя инструкциями:
SWAP: поменять следующий индекс на текущий;
MOVE: перемещает курсор к индексу +1 или -1;
То есть вы не можете поменять местами не соседние индексы и не поменять местами 100
после того, как просто поменяли местами индексы 10
. Какой алгоритм наиболее эффективен, т. Е. Тот, который использует меньшее количество полных ходов?
algorithms
sorting
in-place
MaiaVictor
источник
источник
Ответы:
Рассмотрим сорт коктейльного шейкера , который является двунаправленной версией пузырьковой сортировки. Вы сортируете пузырьки от низкого к высокому, а затем (это добавленная часть) сортируете пузырьки от высокого к низкому, повторяйте, пока не закончите. Это по-прежнему , но в среднем оно делает значительно меньше проходов, потому что небольшие элементы около верхнего конца массива будут перемещаться в свою конечную позицию за один проход, а не за N проходов. Кроме того, вы можете отслеживать самые низкие и самые высокие позиции, где произошел обмен; последующие проходы не должны сканировать за этими точками.O(n2)
источник
Количество перестановок смежных элементов, необходимое для упорядочения массива, равно количеству инверсий в массиве. В общей сложности с n элементами имеется не более n * (n-1) / 2 инверсий, поэтому пузырьковая сортировка дает асимптотически оптимальное количество обменов в этой модели.
источник
Единственный алгоритм с двумя упомянутыми вами операторами, который достаточно эффективен, - это пузырьковая сортировка. Сложность алгоритма в худшем случае .O(n2)
Я также предполагаю, что помимо этих двух операций, мы также можем проверить, находимся ли мы в самой правой (Op 3) или самой левой позиции (Op 4), либо с помощью часовых и либо с помощью какой-либо операции в списке , Также у нас должна быть операция сравнения (Op 5), заданная отдельно или в сочетании с операцией свопинга. Если операция сравнения сочетается с операцией подкачки, то она должна сообщить нам, был ли выполнен обмен или нет.+ ∞−∞ +∞
Алгоритм, который не использует логический флаг, чтобы узнать, поменяли ли мы какой-либо элемент или нет, приведен ниже (хитрость для сохранения информации в состоянии машины, а не памяти):
Решение Эрика Липперта, сортировка гномов, также работает, потому что в основном это двусторонняя пузырьковая сортировка.
источник