DEV Community

loading...
Cover image for PANCAKE SORTING
eduAlgo

PANCAKE SORTING

Aditi Jha
Selenophile
Updated on ・2 min read

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
Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

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)

Collapse
mapio profile image
Massimo Santini • Edited

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))
Enter fullscreen mode Exit fullscreen mode

But the idea is nice :)

Collapse
gerbosan profile image
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.

Collapse
abhijit2505 profile image
Abhijit Tripathy

Good writing 🤩

Collapse
aniketsingh98571 profile image
Aniket Singh

Great work

Collapse
chibisov profile image
Gennady Chibisov

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/