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

Базовая идея алгоритма 1,5-аппроксимации Хартмана и Шарана для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений заключается в следующем. Авторы свели задачу к сортировке циклической 3-перестановки при помощи транспозиций и транспозиций-обращений и затем сосредоточились на преобразовании 3-циклов в 1-циклы в графе разрывов для этой 3-перестановки. По определению, ориентированный (т. е. 2- или 3-скрученный) 3-цикл позволяет выполнять 2-операцию; поэтому авторы продолжили рассмотрение только неориентированных (т. е. 0- или 1-скрученных) 3-циклов. Поскольку конфигурации, включающие только 0-скрученные 3-циклы, в работе [7] обрабатывались при помощи (0, 2, 2)-последовательностей, Хартман и Шаран ограничили рассмотрение конфигурациями, состоящими из 0- и 1-скрученных 3-циклов. Они показали, что все эти конфигурации являются закрытыми и что они могут быть отсортированы при помощи (0, 2, 2)-последовательности операций для каждой из следующих пяти возможных закрытых конфигураций: (1) закрытая конфигурация с двумя неориентированными перемежающимися 3-циклами, не формирующими 1-скрученную пару; (2) закрытая конфигурация с двумя пересекающимися, 0-скрученными 3-циклами; (3) закрытая конфигурация с двумя пересекающимися, 1-скрученными 3-циклами; (4) закрытая конфигурация с 0-скрученными 3-циклами, пересекающаяся со связанными ребрами 1-скрученного 3-цикла; (5) закрытая конфигурация, содержащая <math>k \ge 2</math> взаимно перемежающихся 1-скрученных 3-циклов, таких, что их повороты являются последовательными на круге, а k – максимальное число, обладающее этим свойством. В результате последовательность операций, использованных Хартманом и Шараном в их алгоритме, содержит только 2-операции и (0, 2, 2)-последовательности. Поскольку каждая последовательность из трех операций увеличивает количество нечетных циклов минимум на 4 из возможных 6 за 3 шага, коэффициент этого алгоритма аппроксимации составляет 1,5. Кроме того, Хартман и Шаран показали, что их алгоритм можно реализовать за время <math>O(n^{3/2} \sqrt{log \; n})</math> с использованием структуры данных Каплана и Вербина [10], где n – число элементов в перестановке.