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

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