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
Pancake sorting appears in applications in parallel processor networks, it provides an effective routing algorithm between processors.
It is used when the only allowed operation to sort a sequence is reversing.
Top comments (5)
The code so un-pythonic :) This is shorter (and easier to read, imho):
But the idea is nice :)
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.
Good writing 🤩
Great work
I've built a bot which tries to explain a pancake sorting algorithm in a more active learning manner bot.chib.me/courses/pancake-sorting/