PANCAKE SORTING

#computerscience #algorithms #datastructures

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)

Massimo Santini • Feb 21 '21 • 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))

But the idea is nice :)