PROFILPELAJAR.COM

Одна операция блинной сортировки (вариант с подгоревшими блинами)

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

Алгоритм

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

Задача о подгоревших блинах

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

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

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

Реализация

C#

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;
	}
}

Примечания

↑ Douglas B. West. The Pancake Problems (1975, 1979, 1973) (англ.). Дата обращения: 16 августа 2009. Архивировано 5 апреля 2012 года.
↑ ¹ ² William H. Gates; Christos H. Papadimitriou. Bounds for sorting by prefix reversal (англ.) // Discrete Mathematics. — 1979. — Iss. 27. — P. 47—57. Архивировано 10 июня 2007 года.
↑ Mohammad H. Heydari; I. Hal Sudborough. On the diameter of the pancake network (англ.) // Journal of Algorithms. — Дулут: Academic Press, Inc, 1997. — Vol. 25, iss. 1. — P. 67—94.
↑ Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics (англ.) (17 сентября 2008). Дата обращения: 16 августа 2009. Архивировано 5 апреля 2012 года.
↑ 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. — Vol. 410, iss. 36. — P. 3372—3390.
↑ Karmella A. Haynes, Marian L. Broderick, Adam D. Brown et al. Engineering bacteria to solve the Burnt Pancake Problem (англ.) // Journal of Biological Engineering. — 2008. — Vol. 2, iss. 8. Архивировано 30 июля 2009 года.
↑ Анимационный ролик, объясняющий решение задачи биологическим компьютером (англ.). Дата обращения: 16 августа 2009. Архивировано 5 апреля 2012 года.

См. также

Ханойская башня

Ссылки

Weisstein, Eric W. Pancake Sorting (англ.). MathWorld. Дата обращения: 16 августа 2009.
Alexander Bogomolny. Flipping pancakes (англ.). Дата обращения: 16 августа 2009. Архивировано 5 апреля 2012 года.