Pancake sorting…

Pancake sorting is 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. A pancake number is the minimum number of flips required for a given number of pancakes.

Unlike traditional sorting algorithms, which attempt to sort with the fewest comparisons, pancake sort tries to sort the sequence in as few reversals as possible.

The idea behind pancake sort is similar to Selection Sort. In every iteration, we find the maximum element in the sequence and place it at the end, and reduce the size of the sequence by one.

Given an array of integers Arr:

• Write a function flip(Arr, i) that reverses the order of the first i elements in the array arr.
• Write a function pancakeSort(Arr) that sorts and returns the input array. You are allowed to use only the function flip in order to make changes in the array.

Algorithm :

Let the given array be Arr[] and size of the array be n

• Start from the current size n and reduce the current size by one while it is greater than one. Let the current size be c. Do the following for every c.
  1. Find the index i of the maximum element in Arr[0....c-1].
  2. Call flip(Arr,i)
  3. Call flip(Arr,c-1)

Array representation of the above diagram :

initial pancake order : [3, 5, 2, 1, 7, 6, 4]

First flip : [3, 5, 2, 1, 7, 6, 4]
after first flip : [7, 1, 2, 5, 3, 6, 4]

Second flip : [7, 1, 2, 5, 3, 6, 4]
after second flip : [4, 6, 3, 5, 2, 1, 7]

Third flip : [4, 6, 3, 5, 2, 1, 7]
after third flip : [6, 4, 3, 5, 2, 1, 7]

Fourth flip : [6, 4, 3, 5, 2, 1, 7]
after fourth flip : [1, 2, 5, 3, 4, 6, 7]

Fifth flip : [1, 2, 5, 3, 4, 6, 7]
after fifth flip : [5, 2, 1, 3, 4, 6, 7]

Sixth flip : [5, 2, 1, 3, 4, 6, 7]
after sixth flip : [4, 3, 1, 2, 5, 6, 7]

Seventh flip : [4, 3, 1, 2, 5, 6, 7]
after seventh flip : [2, 1, 3, 4, 5, 6, 7]

Eight flip : [2, 1, 3, 4, 5, 6, 7]
after eighth flip : [1, 2, 3, 4, 5, 6, 7]

Below, the Python code that implements the algorithm explained:

…and the output:

Each pancake therefore requires two flips, which would give a total of \(2n\) flips required. But the last two pancakes require at most one flip; if they are already in order, no flips are needed, and if they are out of order, only one flip is needed. So this algorithm requires at most \(2(n – 2) + 1 = 2n – 3\) flips in the worst case, which means that \(P_n \leq 2n – 3\).