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.
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)
The Sorted Array is: 1 2 3 4 5 6 7 8 9 10
Time Complexity: O(nlogn)
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.