Алгоритмы обмена блоками - Block swap algorithms
 | Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом. (Июль 2019) (Узнайте, как и когда удалить этот шаблон сообщения) |
Алгоритмы обмена блоками поменять местами два элемента множество в компьютере алгоритмы. Просто поменять местами две неперекрывающиеся области множество равного размера. Однако поменять местами две неперекрывающиеся области массива на месте, которые расположены рядом друг с другом, но имеют разные размеры, непросто. Для этого известны три алгоритма: «Жонглирование Бентли», «Грайс-Миллс» и «Реверс».[1] Все три алгоритма являются линейными по времени На), (видеть Сложность времени ).
Алгоритм разворота
Алгоритм разворота проще всего объяснить с помощью вращения. Ротация - это разворот элементов массива на месте. Этот метод меняет местами два элемента массива извне в пределах диапазона. Вращение работает для четного числа элементов или нечетного числа элементов массива. Алгоритм разворота использует три поворота на месте для выполнения замены блока на месте:
- Повернуть область A
- Повернуть область B
- Повернуть область AB
Алгоритмы Gries-Mills и Reversal работают лучше, чем Bentley Juggling, из-за их тайник -дружелюбный шаблон доступа к памяти поведение.
Алгоритм разворота распараллеливает ну, потому что вращения можно разделить на подобласти, которые можно вращать независимо от других.
Рекомендации
- ^ Джон Бентли, «Жемчужины программирования», стр. 13–15, 209–211.
 | Эта статья требует дополнительных или более конкретных категории. (Июль 2019) |