Блинная сортировка c доклад
Обновлено: 02.07.2024
10 сент. 2010 г.
Блинная сортировка
Блинная сортировка
Блинная сортировка (от англ. pancake sorting) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания.
Алгоритм
Простейший алгоритм (вариант сортировки выбором) даёт не более 2n − 3 переворотов, однако требует поиска наибольшего элемента. В 1979 году Билл Гейтс и Христос Пападимитриоу представили свой алгоритм и доказали достаточность (5n + 5) / 3 переворотов и необходимость 17n / 16. В 1997 году Хейдари и Судборог показали нижнюю границу в 15n / 14. Они представили точные значения вплоть до N = 13, для которого требуется 15 переворотов. Значительно превзойти (до 18n / 11) результат Гейтса и Пападимитриоу получилось только в 2008 году у группы исследователей из университета Техаса в Далласе под руководством Судборога
Пример двоичного дерева
Вывод по блинной сортировке
Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.
В 2007 году группа студентов создала биологический компьютер на основе генетически модифицированной кишечной палочки (E. coli), который решал задачу о подгорелых блинах. Роль блинов играли фрагменты дезоксирибонуклеиновой кислоты (3’ и 5’ концы которых были разными сторонами блина). Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента
Блинная сортировка (англ. pancake sorting) — алгоритм сортировки с помощью одной операции — переворота элементов последовательности до какого-то индекса (префикса последовательности). Разумеется, разрешены сравнения, при оценке времени работы этого алгоритма оценивается количество переворотов, а не сравнений. Название алгоритма пошло от изначальной задачи отсортировать стопку блинов по возрастанию размера.
Содержание
Для начала покажем, что любую последовательность можно отсортировать с помощью блинной сортировки. Для этого будет предложен алгоритм, позволяющий отсортировать любой массив, сделав не более [math]2n[/math] операций, где [math]n[/math] — размер массива.
Найдём максимальный элемент последовательности с номером [math]i[/math] и развернём префикс массива до [math]i[/math] -го элемента. Теперь максимальный элемент находится в начале массива. Развернём весь массив, теперь максимальный элемент находится в конце массива. Сделаем то же самое рекуррентно для префикса длины [math]n-1[/math] . Переместим второй по возрастанию элемент в конец подотрезка, после чего последние два элемента будут отсортированы, и продолжим для префикса длины [math]n-2[/math] . Таким образом, на каждой итерации мы сделаем две операции, и всего итераций будет не больше [math]n[/math] (их может быть меньше [math]n[/math] : если после [math]i[/math] -ой итерации отсортированным окажется суффикс длины больше, чем [math]i+1[/math] , можно рекурсивно запустить алгоритм на префиксе длины [math]n-i-k[/math] вместо [math]n-i-1[/math] ). Тогда суммарное количество операций не превосходит [math]2n[/math] и любая последовательность может быть отсортирована таким образом.
Существуют простые оценки: [math]2n[/math] сверху и, для [math]n \geqslant 4[/math] , [math]n[/math] снизу. Более сложные границы были предложены в 1978 году Биллом Гейтсом и Христосом Пападимитриу, и улучшить их получилось лишь в 2008.
Оценка в [math]2n[/math] операций следует из доказательства корректности алгоритма, в котором предлагается алгоритм сортировки любой последовательности за [math]2n[/math] операций. Она может быть улучшена до [math]2n-3[/math] чуть более умной сортировкой последних элементов.
Назовём соседством в массиве пару элементов, которые идут последовательно в массиве и для которых нет элемента, большего одного из них и меньшего другого. Если максимальный элемент находится в конце массива, это тоже будет считаться соседством (будем считать, что массив сортируется по возрастанию).
Для любого [math]n\geqslant 4[/math] существует массив, в котором нет соседств. С другой стороны, отсортированный массив имеет [math]n[/math] соседств, и за один переворот можно добавить не больше одного соседства, поэтому отсортировать массив, сделав меньше, чем [math]n[/math] переворотов, невозможно.
Для начала введём некоторые обозначения.
Пусть [math]S_n[/math] — множество перестановок элементов массива длины [math]n[/math] . Будем считать перестановки строками в [math]\Sigma^*_n[/math] , где [math]\Sigma_n=\[/math] . Введём бинарное отношение [math]R: \Sigma^*_n \rightarrow \Sigma^*_n[/math] : [math]\pi R\sigma[/math] тогда и только тогда, когда [math]\pi =xy[/math] и [math]\sigma =x^Ry[/math] , где [math]\pi, \sigma \in \Sigma^*_n[/math] и [math]x^R[/math] обозначает развёрнутую [math]x[/math] .
Пусть [math]\pi[/math] — перестановка, тогда [math]f(\pi)[/math] — наименьшее [math]k[/math] такое, что существует последовательность перестановок [math]\pi_0 R \pi_1 R \ldots R \pi_k = e_n[/math] , где [math]e_n = 123\ldots n[/math] . Тогда для числа [math]n[/math] будем обозначать [math]f(n)[/math] за максимальное [math]f(\pi)[/math] среди всех [math]\pi \in S_n[/math] .
Пусть [math]\pi[/math] — перестановка из [math]S_n[/math] . Тогда [math]\pi (j)[/math] — число номер [math]j[/math] в перестановке для [math]1 \leqslant j \leqslant n[/math] . Соседством в [math]\pi[/math] назовём пару [math](j, j+1)[/math] такую, что [math]|\pi (j) - \pi (j+1)| = 1[/math] . Также будем называть соседством пару [math](j, j+1)[/math] , если [math]\ <\pi (j), \pi (j+1) \>= \[/math] . Для [math]x \in \Sigma^*_n[/math] будем обозначать длину [math]x[/math] как [math]|x|[/math] .
Пусть [math]\pi=xby[/math] , [math]x, b, y \in \Sigma^*_n[/math] . [math]b[/math] будем называть блоком, если для любого [math]j[/math] такого, что [math]|x|+1 \leqslant j \leqslant |x| + |b| - 1[/math] , пара [math](j, j+1)[/math] — соседство, при этом пары [math](|x|, |x|+1)[/math] и [math](|x|+|b|-1, |x|+|b|[/math] не являются соседствами. Если [math]\pi (j)[/math] не является частью блока, то есть [math](j-1, j)[/math] и [math](j, j+1)[/math] — не соседства, элемент [math]\pi (j)[/math] будем называть свободным.
За [math]o[/math] будем обозначать элемент из [math]\[/math] . Подразумевается, что сложение проводится по модулю [math]n[/math] .
Будет предложен алгоритм, который изменит перестановку [math]\pi[/math] так, чтобы в ней было [math]n-1[/math] соседств. После этого отсортировать массив можно не более чем за 4 действия (в иллюстрациях дальше показана последовательность действий, состояние в следующей строке получается из состояния в предыдущей одним разворотом префикса):
| [math]a[/math] | |
| [math]k-1 \ldots 1[/math] | [math]n \ldots k[/math] |
| [math]k\ldots n[/math] | [math]1\ldots k-1[/math] |
| [math]n\ldots k[/math] | [math]1 \ldots k-1[/math] |
| [math]k-1 \ldots 1[/math] | [math]k \ldots n[/math] |
| [math]1 \ldots k-1[/math] | [math]k \ldots n[/math] |
| [math]b[/math] | |
| [math]k\ldots n[/math] | [math]1\ldots k-1[/math] |
| [math]n\ldots k[/math] | [math]1\ldots k-1[/math] |
| [math]k-1 \ldots 1[/math] | [math]k\ldots n[/math] |
| [math]1\ldots k-1[/math] | [math]k\ldots n[/math] |
- входные данные: перестановка [math]\pi\in S_n[/math]
- выходные данные: перестановка [math]\sigma[/math] с [math]n-1[/math] соседством
Циклически повторять следующее. Пусть [math]t[/math] — первый элемент [math]\pi[/math] ( [math]\pi = t\pi '[/math] ). Как минимум одно из условий выполняется, выполнить соответствующее действие:
- [math]t[/math] свободный, [math]t+o[/math] свободный. Выполнить разворот [math]a[/math] ,
- [math]t[/math] свободный, [math]t+o[/math] — первый элемент блока. Выполнить разворот [math]b[/math] ,
- [math]t[/math] свободный, и [math]t+1[/math] , и [math]t-1[/math] — последние элементы в блоке. Выполнить развороты [math]c[/math] ,
- [math]t[/math] в блоке, [math]t+o[/math] свободен. Выполнить разворот [math]d[/math] ,
- [math]t[/math] в блоке, [math]t+o[/math] — первый элемент блока. Выполнить разворот [math]e[/math] ,
- [math]t[/math] в блоке с последним элементом [math]t+k\cdot o[/math] ( [math]k\gt 0[/math] ), [math]t-o[/math] — последний элемент другого блока, и [math]t+(k+1)\cdot o[/math] свободен. Выполнить перевороты [math]f[/math] или [math]g[/math] в зависимости от расположения блоков,
- [math]t[/math] в блоке с последним элементом [math]t+k\cdot o[/math] ( [math]k\gt 0[/math] ), [math]t-o[/math] — последний элемент другого блока, и [math]t+(k+1)\cdot o[/math] в блоке. Выполнить развороты [math]h[/math] или [math]k[/math] в зависимости от того, в начале или в конце блока находится элемент [math]t+(k+1)\cdot o[/math] ,
- ничего из перечисленного выше. В перестановке [math]\pi[/math] [math]n-1[/math] соседство. Завершить работу алгоритма.
| [math]a[/math] | |||
| [math]t[/math] | [math]\ldots[/math] | [math]t+o[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]t[/math] | [math]t+o[/math] | [math]\ldots[/math] |
| [math]b[/math] | |||
| [math]t[/math] | [math]\ldots[/math] | [math]t+o\ldots[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]t[/math] | [math]t+o\ldots[/math] | [math]\ldots[/math] |
| [math]c[/math] | |||||
| [math]t[/math] | [math]\ldots[/math] | [math]\ldots t+o[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] |
| [math]t+o\ldots[/math] | [math]\ldots[/math] | [math]t[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots t+o[/math] | [math]t[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] |
| [math]t-o \ldots[/math] | [math]\ldots[/math] | [math]t[/math] | [math]t+o \ldots[/math] | [math]\ldots[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]t[/math] | [math]t+o \ldots[/math] | [math]\ldots[/math] | [math]\ldots[/math] |
| [math]d[/math] | |||
| [math]t\ldots[/math] | [math]\ldots[/math] | [math]t+o[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots t[/math] | [math]t+o[/math] | [math]\ldots[/math] |
| [math]e[/math] | |||
| [math]t\ldots[/math] | [math]\ldots[/math] | [math]t+o\ldots[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots t[/math] | [math]t+o \ldots[/math] | [math]\ldots[/math] |
| [math]f[/math] | |||||
| [math]t\ldots t+ko[/math] | [math]\ldots[/math] | [math]t+(k+1)o[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] |
| [math]t+(k+1)o[/math] | [math]\ldots[/math] | [math]t+ko\ldots t[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]t+(k+1)o[/math] | [math]t+ko\ldots t[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] |
| [math]t-o \ldots[/math] | [math]\ldots[/math] | [math]t \ldots t+ko[/math] | [math]t+(k+1)o[/math] | [math]\ldots[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]t \ldots t+ko[/math] | [math]t+(k+1)o[/math] | [math]\ldots[/math] | [math]\ldots[/math] |
| [math]g[/math] | |||||
| [math]t \ldots t+ko[/math] | [math]\ldots[/math] | [math]\ldots t-o[/math] | [math]\ldots[/math] | [math]t+(k+1)o[/math] | [math]\ldots[/math] |
| [math]t+(k+1)o[/math] | [math]\ldots[/math] | [math]t-o \ldots[/math] | [math]\ldots[/math] | [math]t+ko \ldots t[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots to[/math] | [math]\ldots[/math] | [math]t+(k+1)o[/math] | [math]t+ko \ldots t[/math] | [math]\ldots[/math] |
| [math]t \ldots t+ko[/math] | [math]t+(k+1)o[/math] | [math]\ldots[/math] | [math]t-o \ldots[/math] | [math]\ldots[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]t+(k+1)o[/math] | [math]t+ko \ldots t[/math] | [math]t-o \ldots[/math] | [math]\ldots[/math] | [math]\ldots[/math] |
| [math]h[/math] | |||
| [math]t \ldots t+ko[/math] | [math]\ldots[/math] | [math]t+(k+1)o \ldots[/math] | [math]\ldots[/math] |
| [math]t+ko \ldots t[/math] | [math]\ldots[/math] | [math]t+(k+1)o \ldots[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]t \ldots t+ko[/math] | [math]t+(k+1)o \ldots[/math] | [math]\ldots[/math] |
| [math]k[/math] | |||
| [math]t \ldots t+ko[/math] | [math]\ldots[/math] | [math]\ldots t+(k+1)o[/math] | [math]\ldots[/math] |
| [math]t+(k+1)o \ldots[/math] | [math]\ldots[/math] | [math]t+ko \ldots t[/math] | [math]\ldots[/math] |
| [math]\ldots[/math] | [math]\ldots t+(k+1)o[/math] | [math]t+ko \ldots t[/math] | [math]\ldots[/math] |
Предложенный алгоритм создает перестановку с [math]n-1[/math] соседствами не более чем за [math]\dfrac<5n-7>[/math] итераций.
Алгоритм всегда завершит работу. На каждой итерации при условии, что в перестановке меньше [math]n-1[/math] соседств, выполнится одно из условий [math]1-7[/math] . На каждой итерации создается не меньше одного соседства и ни одного соседства не разрушается, поэтому алгоритм создаст нужную перестановку не больше чем за [math]n-1[/math] итераций.
Будем называть случай 1 действием 1, случай 2 действием 2, случаи 3 и 6 действием 3, случаи 4, 5 и 7 действиями 4, 5 и 7 соответственно. Пусть [math]x_i[/math] обозначает количество действий типа [math]i[/math] , выполненных за время работы алгоритма. Суммарное число разворотов составит
[math]z=x_1 + x_2 + 4x_3 + x_4 + 2x_5 + x_7[/math]
[math]x_i[/math] умножено на количество разворотов, выполняемых за это действие.
Действие 3 может быть разделено на 4 случая. Перед предпоследним разворотом самый левый элемент массива и элемент после [math]t-o[/math] могут
- Быть непарными.
- Образовывать новый блок.
- Соединять блок с отдельным элементом.
- Соединять два блока.
Эти 4 варианта учитываются, если считать [math]x_3 = x_+x_+x_+x_[/math] . В таблице 1 записано, как каждое действие увеличивается количество соседств. Суммарное количество соседств можно записать в виде суммы
[math]n-1 = a + x_1 + x_2 + 2x_ + 3x_ + 3x_ + 3x_ + x_4 + x_5 + x_7[/math]
Если [math]b[/math] — количество блоков в изначальной перестановке, то, поскольку каждое действие изменяет количество блоков так, как показано в таблице 1, а в конечной перестановке 1 блок, имеем
[math]b + x_1 - x_ - x_ - 2x_ - x_5 - x_7 = 1[/math]
Поскольку [math]b\leqslant a[/math] , из первого равенства следует
[math]x_1 + x_2 + 2x_ + 3x_ + 3x_ + 3x_ + x_4 + x_5 + x_7 + b \leqslant n-1[/math]
Таким образом, для нахождения худшего случая нужно максимизировать
[math]z=x_1 + x_2 + 4x_3 + x_4 + 2x_5 + x_7[/math]
так, чтобы выполнялось равенство
[math]b + x_1 - x_ - x_ - 2x_ - x_5 - x_7 = 1[/math]
[math]x_1 + x_2 + 2x_ + 3x_ + 3x_ + 3x_ + x_4 + x_5 + x_7 + b \leqslant n-1[/math]
Утверждается, что максимальное значение достигается при
[math]x_1 = \dfrac[/math] , [math]x_2 = 0[/math] , [math]x_3 = x_ = \dfrac[/math] , [math]x_4=x_5=x_7=b=0[/math]
В таком случае максимизируемое значение [math]z=\dfrac[/math] . Для доказательства этого утверждения воспользуемся теоремой о двойственности Данцига-фон Неймана, из которой следует, что максимальное значение равно минимальному значению двойной линейной задачи:
[math]\xi_2+\xi_3 \geqslant 1[/math] ,
[math]\xi_3 \geqslant 1[/math] ,
[math]-\xi_2+2\xi_3 \geqslant 4[/math] ,
[math]3\xi_3 \geqslant 4[/math] ,
[math]-\xi_2+3\xi_3 \geqslant 4[/math] ,
[math]-2\xi_2+3\xi_3 \geqslant 4[/math] ,
[math]\xi_3 \geqslant 1[/math] ,
[math]-\xi_2+\xi_3 \geqslant 1[/math] ,
[math]-\xi_2+\xi_3 \geqslant 2[/math] ,
[math]\xi_2+\xi_3 \geqslant 0[/math] .
Для доказательства утверждения достаточно найти пару [math](\xi_2, \xi_3)[/math] , удовлетворяющую этим условиям, при которой [math]\omega=\xi_2+(n-1)\xi_3=\dfrac[/math] . Такая пара — [math](-\dfrac, \dfrac)[/math] .
Для нижней границы построим последовательность, которая может быть отсортирована не менее чем за [math]\dfrac[/math] разворотов.
Число разворотов, необходимое для сортировки последовательности [math]\chi[/math] , не меньше [math]\dfrac<17n>[/math] .
Изначально задача по подгоревших блинах (англ. burnt pancake problem) формулировалась так:
Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.
Другими словами, нужно предложить алгоритм блинной сортировки, в котором каждый элемент будет развёрнут чётное число раз.
Блинная сортировка (от англ. pancake sorting ) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания.
Содержание
Алгоритм
Простейший алгоритм (вариант сортировки выбором) даёт не более переворотов, однако требует поиска наибольшего элемента [1] . В 1979 году Билл Гейтс и Христос Пападимитриу представили свой алгоритм и доказали достаточность переворотов и необходимость [2] . В 1997 году Хейдари и Судборог показали нижнюю границу в . Они представили точные значения вплоть до , для которого требуется 15 переворотов [3] . Значительно превзойти (до ) результат Гейтса и Пападимитриоу получилось только в 2008 году у группы исследователей из университета Техаса в Далласе под руководством Судборога [4] [5] .
Задача о подгоревших блинах
Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.
В 2007 году группа студентов создала биологический компьютер на основе генетически модифицированной кишечной палочки (E. coli), который решал задачу о подгорелых блинах. Роль блинов играли фрагменты дезоксирибонуклеиновой кислоты (3’ и 5’ концы которых были разными сторонами блина). Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента [6] [7] .
Примечания
- ↑Douglas B. WestThe Pancake Problems (1975, 1979, 1973) (англ.) . Архивировано из первоисточника 6 апреля 2012.Проверено 16 августа 2009.
- ↑ 12William H. Gates; Christos H. PapadimitriouBounds 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. VoitAn (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.
См. также
Ссылки
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое "Блинная сортировка" в других словарях:
Сортировка Шелла — (англ. Shell sort) алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными… … Википедия
Сортировка выбором — (Selection sort) алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… … Википедия
Сортировка вставками — Сортировка вставками простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до … Википедия
Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) простой алгоритм сортировки. Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… … Википедия
Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в)… … Википедия
Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… … Википедия
Сортировка расчёской — (англ. comb sort) это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine … Википедия
Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п … Википедия
Устойчивая сортировка — Устойчивая (стабильная) сортировка сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Устойчивость является очень важной характеристикой алгоритма сортировки, но, тем не менее, она… … Википедия
Демонстрация основной операции. Лопатка переворачивает три верхних блина, и результат показан ниже. В задаче о подгоревших блинах теперь будут обожжены их верхние стороны, а не нижние.
Сортировка блинов - это разговорный термин для математической задачи сортировки неупорядоченной стопки блинов по размеру, когда шпатель можно вставить в любую точку стопки и перевернуть все блины над ней. А блинчик номер - минимальное количество переворотов, необходимое для заданного количества блинов. В таком виде проблему впервые обсудили американские геометр Джейкоб Э. Гудман. [1] Один из вариантов проблемы связан с сгорел блины, у которых у каждого блина есть подгоревшая сторона, а все блины, кроме того, должны иметь подгоревшую сторону.
Все методы сортировки требуют сравнения пар элементов. Для традиционных проблема сортировки, обычная изучаемая задача - минимизировать количество сравнений, необходимых для сортировки списка. Количество фактических операций, таких как замена двух элементов, в этом случае не имеет значения. Для задач сортировки блинов, напротив, цель состоит в том, чтобы свести к минимуму количество операций, где единственными разрешенными операциями являются развороты элементов некоторых приставка последовательности. Теперь количество сравнений не имеет значения.
Содержание
Блинные проблемы
Оригинальная блинная проблема
Минимальное количество переворачиваний, необходимое для сортировки любой стопки п было показано, что блины лежат между 15 / 14 п и 18 / 11 п (примерно 1,07п и 1,64п,), но точное значение неизвестно. [2]
Самый простой алгоритм сортировки блинов выполняет не более 2п − 3 переворачивает. В этом алгоритме своего рода сортировка выбора, одним флипом доводим до верха самый крупный еще не рассортированный блин; опустите его в конечное положение еще одним переворотом; и повторите этот процесс для оставшихся блинов.
В 1979 г. Билл Гейтс и Христос Пападимитриу [3] дал верхнюю границу (5п+5) / 3 . Спустя тридцать лет это было улучшено, чтобы 18 / 11 п командой исследователей из Техасский университет в Далласепод руководством профессора-основателя Хэл Садборо. [4] [5]
В 2011 году Лоран Бюльто, Гийом Фертин и Ирена Русу [6] доказал, что задача поиска кратчайшей последовательности флипов для заданной стопки блинов является NP-жесткий, тем самым отвечая на вопрос, который оставался открытым более трех десятилетий.
Проблема подгоревшего блина
В варианте, называемом проблема подгоревшего блина, дно каждого блина в стопке подгорело, и сортировка должна завершаться подгоревшей стороной каждого блина вниз. Это знаковая перестановка, а если блин я "сгоревшей стороной вверх" отрицательный элемент я ставится на место я в перестановке. В 2008 году группа студентов построила бактериальный компьютер который может решить простой пример проблемы сгоревшего блина, запрограммировав Кишечная палочка перевернуть сегменты ДНК, похожие на подгоревшие блины. ДНК имеет ориентацию (5 'и 3') и порядок (промотор перед кодированием). Несмотря на то, что вычислительная мощность, выражаемая с помощью переворотов ДНК, невелика, большое количество бактерий в культуре обеспечивает большую платформу для параллельных вычислений. Бактерии сообщают, когда они решили проблему, став устойчивыми к антибиотикам. [7]
Проблема одинаковой стопки блинов
Это навеяно индийским хлебом (роти или чапати) готовится. Первоначально все роти укладываются в один столбик, и повар переворачивает роти лопаткой так, чтобы каждая сторона каждого роти в какой-то момент касалась основного огня, чтобы поджарить. Возможны несколько вариантов: гриль можно рассматривать как односторонний или двухсторонний, и может быть запрещено или не поджаривать одну и ту же сторону дважды. Эта версия проблемы была впервые исследована Аркой Ройчоудхури. [8]
Блинная задача на струнах
История
Хотя сортировка блинчиков чаще рассматривается как обучающее устройство, она также появляется в приложениях в сетях с параллельными процессорами, в которых она может обеспечить эффективный алгоритм маршрутизации между процессорами. [11] [12]
Связанные проблемы знаковой сортировки обращениями и сортировки обращениями также изучались совсем недавно. В то время как для знаковой сортировки обращениями найдены эффективные точные алгоритмы, [14] Доказано, что проблема сортировки по разворотам трудна даже для аппроксимации с точностью до определенного постоянного множителя, [15] а также доказано, что его можно аппроксимировать за полиномиальное время с точностью до коэффициента аппроксимации 1,375. [16]
Читайте также: