algorithm
Масленица
Поиск…
Основная информация о Pancake
Масленица - это разговорный термин для математической проблемы сортировки неупорядоченной стопки блинов в порядке размера, когда шпатель может быть вставлен в любую точку стека и используется, чтобы перевернуть все блины над ним. Число блинов - это минимальное количество флип, необходимых для данного количества блинов.
В отличие от традиционного алгоритма сортировки, который пытается сортировать с наименьшим количеством сравнений, цель состоит в том, чтобы отсортировать последовательность как можно меньше разворотов.
Идея состоит в том, чтобы сделать что-то похожее на Selection Sort. Мы по одному помещаем максимальный элемент в конце и уменьшаем размер текущего массива на единицу.
Расселение проблемы:
- Необходимо заказать блины от самых маленьких (сверху) до самых больших (внизу), стартовый стек можно организовать в любом порядке.
- Я могу выполнять флип, переворачивая весь стек.
- Чтобы перевернуть конкретный блины на дно стека, сначала нужно перевернуть его вверх (затем перевернуть его на дно).
- Чтобы заказать каждый блин, потребуется один флип вверх и один флип вниз до его окончательного местоположения.
Интуитивный алгоритм:
Найдите самый крупный блайнд и переверните его на дно (вам может потребоваться сначала перевернуть его в верхнюю часть стека).
Повторите шаг 1 до тех пор, пока не будет упорядочен стек.
Вот и все, двухэтапный алгоритм будет работать.
Пример алгоритма сортировки блинов:
Вспомогательное пространство: O(1)
Сложность времени: O(n^2)
Реализация C #
public class PancakeSort
{
private static void SortPancake(int[] input, int n)
{
for (var bottom = n - 1; bottom > 0; bottom--)
{
var index = bottom;
var maxIndex = input[bottom];
int i;
for (i = bottom - 1; i >= 0; i--)
{
if (input[i] > maxIndex)
{
maxIndex = input[i];
index = i;
}
}
if (index == bottom) continue;
var temp = new int[n];
var j = 0;
for (i = bottom; i > index; i--,j++)
{
temp[j] = input[i];
}
for (i = 0; i < index; i++, j++)
{
temp[j] = input[i];
}
if (temp.Length > j) temp[j] = input[index];
for (i = 0; i <= bottom; i++)
{
input[i] = temp[i];
}
}
}
public static int[] Main(int[] input)
{
SortPancake(input, input.Length);
return input;
}
}