Блинная сортировка
Блинная сортировка (от Шаблон:Lang-en) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания.
Алгоритм
Простейший алгоритм (вариант сортировки выбором) даёт не более переворотов, однако требует поиска наибольшего элемента[1]. В 1979 году Билл Гейтс и Христос Пападимитриу представили свой алгоритм и доказали достаточность переворотов и необходимость [2]. В 1997 году Хейдари и Судборог показали нижнюю границу в . Они представили точные значения вплоть до , для которого требуется 15 переворотов[3]. Значительно (до ) превзойти результат Гейтса и Пападимитриу получилось только в 2008 году у группы исследователей из Техасского университета в Далласе под руководством Судборога[4][5].
Задача о подгоревших блинах
Усложнённый вариант представляет собой блинную сортировку последовательности, элементы которой содержат дополнительный бинарный параметр. Эту задачу предложили Билл Гейтс и Христос Пападимитриу в 1979 году[2]. Она стала известна как «задача о подгоревших блинах» (Шаблон:Lang-en):
Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.
В 2007 году группа студентов создала биокомпьютер на основе генетически модифицированной Шаблон:Bt-ruslat, который решал задачу о подгорелых блинах. Роль блинов играли фрагменты дезоксирибонуклеиновой кислоты (3′- и 5′-концы которых обозначали разные стороны блина). Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента[6][7].
Реализация
public static void PancakeSort<T>(IList<T> arr, int cutoffValue = 2)
where T : IComparable
{
for (int i = arr.Count - 1; i >= 0; --i)
{
int pos = i;
// Find position of max number between beginning and i
for (int j = 0; j < i; j++)
{
if (arr[j].CompareTo(arr[pos]) > 0)
{
pos = j;
}
}
// is it in the correct position already?
if (pos == i)
{
continue;
}
// is it at the beginning of the array? If not flip array section so it is
if (pos != 0)
{
Flip(arr, pos + 1);
}
// Flip array section to get max number to correct position
Flip(arr, i + 1);
}
}
private static void Flip<T>(IList<T> arr, int n)
where T : IComparable
{
for (int i = 0; i < n; i++)
{
--n;
T tmp = arr[i];
arr[i] = arr[n];
arr[n] = tmp;
}
}