Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями

Пусть дана перестановка со знаками <math>\pi</math> на множестве {1, 2, ..., n} из n элементов. Ее можно преобразовать в перестановку без знаков <math>f(\pi) = \pi' = [\pi'_1, \pi'_2, ..., \pi'_{2n}]</math> на множестве {1, 2, ... ,2n} из 2n элементов путем замены каждого положительного элемента i двумя элементами 2i – 1, 2i (именно в таком порядке), а каждого отрицательного элемента -i – двумя элементами 2i, 2i - 1. Расширенная перестановка <math>f(\pi)</math> здесь рассматривается как циклическая перестановка при помощи определения 2n + 1 и 1 в индексах и элементах. Чтобы гарантировать, что каждая операция на <math>f(\pi)</math> может быть имитирована операцией на <math>\pi</math>, для <math>f(\pi)</math> допускаются только операции, выполняющие разрезание перед нечетными позициями. ''Граф разрывов'' <math>G(\pi)</math> представляет собой граф с раскрашенными ребрами с 2n вершинами {1, 2, ..., 2n}, в котором для любого <math>1 \le i \le n</math> вершина <math>\pi'_{2i}</math> соединяется с <math>\pi'_{2i + 1}</math> ребром черного цвета, а вершина 2i соединяется с 2i + 1 ребром серого цвета (см. пример на рис. 1b). Поскольку степень каждой вершины в <math>G(\pi)</math> в точности равна 2, граф уникальным образом разбивается на циклы. ''k-цикл'' (то есть цикл ''длины'' k) представляет собой цикл с k черными ребрами и является ''нечетным'', если k нечетно. Обозначим количество нечетных циклов в <math>G(\pi)</math> за <math>c_{odd}(\pi)</math>. Несложно убедиться в том, что <math>G(\pi)</math> состоит из n 1-циклов и, следовательно, <math>c_{odd}(\pi) = n</math>, если ж является тождественной перестановкой [1, 2, ..., n]. Гу и др. [5] показали, что <math>c_{odd}(\mu \cdot \pi_ \le c_{odd}(\pi) + 2</math> для всех линейных перестановок <math>\pi</math> и операций <math>\mu</math>. В работе [8] Хартман и Шаран также отметили, что вышеприведенный результат имеет место также для циклических перестановок, и доказали, что нижняя граница <math>d(\pi)</math> составляет <math>(n(\pi) - c_{odd}(\pi))/2</math>.

Перестановка называется ''простой'', если ее граф разрывов содержит только k-циклы, где <math>k \le 3</math>. Простая перестановка также называется ''3-перестановкой'', если она не содержит 2-циклов. Преобразование из ж в ж называется безопасным, если п(ж) — соаа(лг) = п{ж) — со^(ж). Было показано, что любая перестановка ж может быть преобразована в простую перестановку ж' при помощи безопасных преобразований и, более того, что любая сортировка ж' имитирует сортировку ж с тем же количеством операций [6, 11]. Хартман и Шаран [8] также показали, что любая простая перестановка ж' может быть преобразована в 3-перестановку ж при помощи безопасных операций заполнения (преобразующих эти 2-циклы в 1-скрученные 3-циклы) и, более того, что любая сортировка ж имитирует сортировку ж' с тем же количеством операций. Основываясь на этих двух свойствах, можно заключить, что произвольная перестановка ж может быть преобразована в 3-перестановку ж, такую, что любая сортировка ft имитирует сортировку ж с тем же количеством операций, предполагая, что можно ограничить рассмотрение только циклическими 3-перестановками.