## DEV Community is a community of 695,394 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

eduAlgo

# PANCAKE SORTING

Selenophile

Pancake sort is a sorting algorithm in which the only allowed operation is to "flip" one end of the list. It is inplace but not stable.

Just like the name, it means the same as sorting pancakes on a plate with a spatula, where you can only flip some of the top pancakes in the plate using spatula.

Given an unsorted array, sort the given array. You are allowed to do only following operation on array:

``````flip(arr, n): Reverse array from 0 to n
``````

Our aim is to sort the sequence in as few reversals as possible i.e. shortest ways possible.

## Explanation

The idea is to do something similar to Selection Sort. We one by one place maximum element at the end and reduce the size of current array by one.

Let given array be arr[] and size of array be i.

Start from current size equal to n and reduce current size by one while it’s greater than 1. Let the current size be current_size. Do the following for every current_size

▪︎ Find index of the maximum element in arr[0..current_size-1]. Let the index be ‘mid’
▪︎Call flip(arr, mid)
▪︎Call flip(arr, current_size-1)

``````# program to sort array using pancake sort
# Reverses arr[0..n] */

def flip(arr, n):
start = 0
while start < n:
temp = arr[start]
arr[start] = arr[n]
arr[n] = temp
start += 1
n -= 1

# to return index of the maximum

def findMax(arr, i):
mid = 0
for i in range(0,i):
if arr[n] > arr[mid]:
mid = i
return mid
#Main function
def pancakeSort(arr, i):
# Starting from the main array

current_size = i
while current_size > 1:
# Find index of the maximum element

mid = findMax(arr, current_size)

#then current size is reduced one by one
# maximum element is moved to the end

if mid != current_size-1:
# To move at the end, we first move maximum number to the beginning

flip(arr, mid)
#now we reverse the array and maximum element is moved to the end

flip(arr, current_size-1)
current_size -= 1
# Function to print an array of size i

def printArray(arr, i):
for i in range(0,i):
print ("%d"%( arr[n]),end=" ")

# Driver program
arr = [8,6,3,2,5,9,1,4,7,10]
i = len(arr)
pancakeSort(arr, i);
print ("The Sorted Array is")
printArray(arr,i)

``````

Output:
The Sorted Array is: 1 2 3 4 5 6 7 8 9 10

Time Complexity: O(nlogn)

## Applications

1. Pancake sorting appears in applications in parallel processor networks, it provides an effective routing algorithm between processors.

2. It is used when the only allowed operation to sort a sequence is reversing.

## Discussion (5)

The code so un-pythonic :) This is shorter (and easier to read, imho):

``````argmax = lambda lst, n: max((v, i) for i, v in enumerate(lst[:n]))[1]
flip = lambda arr, n: arr[0:n][::-1] + arr[n:]

def pancakesort(data):
n = len(data)
while n:
m = argmax(data, n)
data = flip(data, m + 1)
data = flip(data, n)
n -= 1
rerturn data

print(panckakesort(data))
``````

But the idea is nice :)

Carlos A.

This one looks interesting, the first lines are confusing but it work. The code on the article shows error in line 20. Typo with the variables.

Abhijit Tripathy

Good writing 🤩

Aniket Singh

Great work