Pancake Sorter Algorithm
A variant of the problem is pertained with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it.
In addition, the most notable paper published by Futurama co-creator David X. Cohen (as David S. Cohen) pertained the burnt pancake problem. The pancake sorting problem was first posed by Jacob E. Goodman, write under the pseudonym" Harry Dweighter" (" harried waiter").Although seen more often as an educational device, pancake sorting also looks in applications in parallel CPU networks, in which it can supply an effective routing algorithm between CPUs.
Whereas efficient exact algorithms have been found for the signed sorting by reversals, the problem of sorting by reversals has been proven to be hard even to estimate to within certain constant factor, and also proven to be approximable in polynomial time to within the estimation factor 1.375.
using System.Collections.Generic;
namespace Algorithms.Sorters.Comparison
{
/// <summary>
/// Class that implements pancake sort algorithm.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class PancakeSorter<T> : IComparisonSorter<T>
{
/// <summary>
/// Sorts array using specified comparer,
/// internal, in-place, stable,
/// time complexity: O(n^2),
/// space complexity: O(1),
/// where n - array length.
/// </summary>
/// <param name="array">Array to sort.</param>
/// <param name="comparer">Compares elements.</param>
///
public void Sort(T[] array, IComparer<T> comparer)
{
var n = array.Length;
// Start from the complete array and one by one
// reduce current size by one
for (var curr_size = n; curr_size > 1; --curr_size)
{
// Find index of the maximum element in
// array[0..curr_size-1]
var mi = FindMax(array, curr_size, comparer);
// Move the maximum element to end of current array
// if it's not already at the end
if (mi != curr_size - 1)
{
// To move to the end, first move maximum
// number to beginning
Flip(array, mi);
// Now move the maximum number to end by
// reversing current array
Flip(array, curr_size - 1);
}
}
}
// Reverses array[0..i]
private void Flip(T[] array, int i)
{
T temp;
var start = 0;
while (start < i)
{
temp = array[start];
array[start] = array[i];
array[i] = temp;
start++;
i--;
}
}
// Returns index of the maximum element
// in array[0..n-1]
private int FindMax(T[] array, int n, IComparer<T> comparer)
{
var mi = 0;
for (var i = 0; i < n; i++)
{
if (comparer.Compare(array[i], array[mi]) == 1)
{
mi = i;
}
}
return mi;
}
}
}
