Блинная сортировка

Блинная сортировка

Блинная сортировка (от англ. pancake sorting) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания.

Алгоритм

Простейший алгоритм (вариант сортировки выбором) даёт не более 2n − 3 переворотов, однако требует поиска наибольшего элемента. В 1979 году Билл Гейтс и Христос Пападимитриоу представили свой алгоритм и доказали достаточность (5n + 5) / 3 переворотов и необходимость 17n / 16. В 1997 году Хейдари и Судборог показали нижнюю границу в 15n / 14. Они представили точные значения вплоть до N = 13, для которого требуется 15 переворотов. Значительно превзойти (до 18n / 11) результат Гейтса и Пападимитриоу получилось только в 2008 году у группы исследователей из университета Техаса в Далласе под руководством Судборога

Пример двоичного дерева

Вывод по блинной сортировке

Усложнённый вариант представляет собой блинную сортировку последовательности, элементы которой содержат дополнительный бинарный параметр. Эту задачу предложили Билл Гейтс и Христос Пападимитриоу в 1979 году. Она стала известна как «задача о подгоревших блинах» (англ. burnt pancake problem):

Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.

В 2007 году группа студентов создала биологический компьютер на основе генетически модифицированной кишечной палочки (E. coli), который решал задачу о подгорелых блинах. Роль блинов играли фрагменты дезоксирибонуклеиновой кислоты (3’ и 5’ концы которых были разными сторонами блина). Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента