Алгоритмы замены блоков

В компьютерных алгоритмы алгоритмах замены блоков меняют местами две области элементов массива . Поменять местами две непересекающиеся области массива одинакового размера очень просто. Однако поменять местами две непересекающиеся области массива, находящиеся рядом друг с другом, но имеющие неравные размеры, непросто (такая замена эквивалентна вращению массива ). Известны три алгоритма, позволяющие выполнить эту задачу: «Жонглирование Бентли» (также известный как алгоритм «Дельфин»). ), Гриса-Миллса и разворота. Все три алгоритма имеют линейное время. O(n) (см. Временная сложность ).

Алгоритм разворота

Алгоритм разворота проще всего объяснить с помощью вращений. Вращение — это изменение местами элементов массива. Этот метод меняет местами два элемента массива снаружи внутри диапазона. Вращение работает для четного или нечетного числа элементов массива. Алгоритм реверса использует три вращения на месте для выполнения замены блоков на месте:

• Повернуть регион А
• Повернуть регион Б
• Повернуть регион AB

Алгоритмы Гриса-Миллса и Reversal работают лучше, чем алгоритм Bentley Juggling, благодаря их к кэшу дружественным шаблонам доступа к памяти, .

Алгоритм Reversal хорошо распараллеливается , поскольку повороты можно разбить на подобласти, которые можно вращать независимо от других.