Pancake Sort 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.
// Sorting of array list using pancake sort
#include <stdlib.h>
#include <stdio.h>
/* Reverses the array */
void flip(int arr[], int i)
{
int temp, start = 0;
while (start < i)
{
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
// Returns index of the maximum element in arr[0..n-1]
int findMax(int arr[], int n)
{
int maxElementIdx, i;
for (maxElementIdx = 0, i = 0; i < n; ++i)
if (arr[i] > arr[maxElementIdx])
maxElementIdx = i;
return maxElementIdx;
}
// Sorts the array using flip operations
int pancakeSort(int *arr, int n)
{
// Start from the complete array and one by one reduce current size by one
for (int curr_size = n; curr_size > 1; --curr_size)
{
// Find index of the maximum element in arr[0..curr_size-1]
int maxElementIdx = findMax(arr, curr_size);
// Move the maximum element to end of current array if it's not already at the end
if (maxElementIdx != curr_size-1)
{
// To move at the end, first move maximum number to beginning
flip(arr, maxElementIdx);
// Now move the maximum number to end by reversing current array
flip(arr, curr_size-1);
}
}
}
// Displays the array, passed to this method
void display(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program to test above function
int main()
{
int arr[] = {23, 10, 20, 11, 12, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Original array: ");
display(arr, n);
pancakeSort(arr, n);
printf("Sorted array: ");
display(arr, n);
return 0;
} 
