- Блинная сортировка
-
Блинная сортировка (от англ. pancake sorting) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания.
Содержание
Алгоритм
Простейший алгоритм (вариант сортировки выбором) даёт не более переворотов, однако требует поиска наибольшего элемента[1]. В 1979 году Билл Гейтс и Христос Пападимитриу представили свой алгоритм и доказали достаточность переворотов и необходимость [2]. В 1997 году Хейдари и Судборог показали нижнюю границу в . Они представили точные значения вплоть до , для которого требуется 15 переворотов[3]. Значительно превзойти (до ) результат Гейтса и Пападимитриоу получилось только в 2008 году у группы исследователей из университета Техаса в Далласе под руководством Судборога[4][5].
Задача о подгоревших блинах
Усложнённый вариант представляет собой блинную сортировку последовательности, элементы которой содержат дополнительный бинарный параметр. Эту задачу предложили Билл Гейтс и Христос Пападимитриу в 1979 году[2]. Она стала известна как «задача о подгоревших блинах» (англ. burnt pancake problem):
Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.
В 2007 году группа студентов создала биологический компьютер на основе генетически модифицированной кишечной палочки (E. coli), который решал задачу о подгорелых блинах. Роль блинов играли фрагменты дезоксирибонуклеиновой кислоты (3’ и 5’ концы которых были разными сторонами блина). Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента[6][7].
Примечания
- ↑ Douglas B. West The Pancake Problems (1975, 1979, 1973) (англ.). Архивировано из первоисточника 6 апреля 2012. Проверено 16 августа 2009.
- ↑ 1 2 William H. Gates; Christos H. Papadimitriou Bounds for sorting by prefix reversal (англ.) // Discrete Mathematics. — 1979. — В. 27. — С. 47—57.
- ↑ Mohammad H. Heydari; I. Hal Sudborough On the diameter of the pancake network (англ.) // Journal of Algorithms. — Дулут: Academic Press, Inc, 1997. — В. 1. — Т. 25. — С. 67—94.
- ↑ Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics (англ.) (17.09.2008). Архивировано из первоисточника 6 апреля 2012. Проверено 16 августа 2009.
- ↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, W. Voit An (18/11)n upper bound for sorting by prefix reversals (англ.) // Theoretical Computer Science. — Эссекс: Elsevier Science Publishers Ltd., 2009. — В. 36. — Т. 410. — С. 3372—3390.
- ↑ Karmella A Haynes, Marian L Broderick, Adam D Brown и др. Engineering bacteria to solve the Burnt Pancake Problem (англ.) // Journal of Biological Engineering. — 2008. — В. 8. — Т. 2.
- ↑ Анимационный ролик, объясняющий решение задачи биологическим компьютером (англ.). Архивировано из первоисточника 6 апреля 2012. Проверено 16 августа 2009.
См. также
Ссылки
- Weisstein, Eric W. Pancake Sorting (англ.). MathWorld. Проверено 16 августа 2009.
- Alexander Bogomolny Flipping pancakes (англ.). Архивировано из первоисточника 6 апреля 2012. Проверено 16 августа 2009.
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.