Sorting the Pancakes in Python

Today, we will learn how to use Python to solve the Pancake Sorting problem.

Here is the problem: We have a set of pancakes made by a diner. The problem with the stack is that each pancake is in a different size (no two pancakes share the same size). You were assigned by the diner to sort these pancakes. However, you can only do one operation: flip a part of the stack by selecting a pancake in the stack and flipping the sub stack formed. Kind of like flipping a pancake with a spatula but with several pancakes. As an example:

Before trying to program the solution, we can think about it conceptually.

To start, we can set numbers for the pancakes. For this example, one will be the smallest, and three will be the largest:

3

1

2

How would we sort this? One strategy is to get the largest size at the bottom first, and then the next sizes. First, we flip the entire stack to get three at the bottom:

2

1

3

We can then flip the top two pancakes to get the two in the middle:

1

2

3

We now have the list sorted.

To implement this, we need some helper functions. The first function can be for flipping a stack. We start with the definition:

def flipPancakes(array, n):

count=0

the count variable will be used for keeping track of what pancake are we on now.

We can now go ahead with the while loop:

while count<n:

array[count], array[n] = array[n], array[count]

n=n-1

count=count+1

All this does is swap the places of a pancake and its corresponding one, and changing the indices to do the next swap.

We now need a function to give us the index of the first element in the next to-be-flipped sub stack.

The code for this function is simple; we check each index and see if the previous one is less than the current one. If it is, we found our index. If it is not, we move on:

def maxIndex(array, n):

index=0

for i in range(n);

if array[i]>array[index]:

index=i

return index

Now for the main code, which will be enclosed in a function so that we can use it anywhere in the program. The array to be sorted will be passed as a parameter and the length determined using the len() function:

def sortThePancakes(array):

pancakeCount=len(array)

Now for the while loop. The loop uses the two functions made earlier to simplify the process:

while pancakeCount>1:

The max index function:

max_index=max_Index(array, pancakeCount)

if max_index!=pancakeCount:

And the pancake sorting function:

flipPancakes(array, max_index)

flipPancakes(array, pancakeCount-1)

pancakeCount=pancakeCount-1

We then call the function using sortThePancakes(array), where array is the list of numbers to be sorted.

We have solved the pancake problem. This algorithm does not have to apply for just unpredictable pancakes. Because This algorithm works with numbers, it can be applied to work with any set. However, with humongous lists, the algorithm can take time.