Get this book -> Problems on Array: For Interviews and Competitive Programming
Reading time: 30 minutes | Coding time: 15 minutes
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.
Pancake sort is called so because it resembles sorting pancakes on a plate with a spatula, where you can only use the spatula to flip some of the top pancakes in the plate.
Unlike traditional sorting algorithms, which attempt to sort with the fewest comparisons, pancake sort tries to sort the sequence in as few reversals as possible.
Explanation :
The idea behind pancake sort is similar to Selection Sort. In every iteration, we find the maximum element in the sequence and place it at the end, and reduce the size of the sequence by one.
Given an array of integers Arr:
- Write a function flip(Arr, i) that reverses the order of the first i elements in the array arr.
- Write a function pancakeSort(Arr) that sorts and returns the input array. You are allowed to use only the function flip in order to make changes in the array.
Algorithm :
Let the given array be Arr[] and size of the array be 'n'
- Start from the current size 'n' and reduce the current size by one while it is greater than one. Let the current size be c. Do the following for every 'c'.
- Find the index 'i' of the maximum element in Arr[0....c-1].
- Call flip(Arr,i)
- Call flip(Arr,c-1)
Example :
Array representation of the above diagram :
initial pancake order : [3, 5, 2, 1, 7, 6, 4]
First flip : [3, 5, 2, 1, 7, 6, 4]
after first flip : [7, 1, 2, 5, 3, 6, 4]
Second flip : [7, 1, 2, 5, 3, 6, 4]
after second flip : [4, 6, 3, 5, 2, 1, 7]
Third flip : [4, 6, 3, 5, 2, 1, 7]
after third flip : [6, 4, 3, 5, 2, 1, 7]
Fourth flip : [6, 4, 3, 5, 2, 1, 7]
after fourth flip : [1, 2, 5, 3, 4, 6, 7]
Fifth flip : [1, 2, 5, 3, 4, 6, 7]
after fifth flip : [5, 2, 1, 3, 4, 6, 7]
Sixth flip : [5, 2, 1, 3, 4, 6, 7]
after sixth flip : [4, 3, 1, 2, 5, 6, 7]
Seventh flip : [4, 3, 1, 2, 5, 6, 7]
after seventh flip : [2, 1, 3, 4, 5, 6, 7]
Eight flip : [2, 1, 3, 4, 5, 6, 7]
after eighth flip : [1, 2, 3, 4, 5, 6, 7]
For visualisation of the algorithm, watch the following video : Pancake sorting visualisation
Implementation
- C
- C++
- Python
C
#include <stdlib.h>
#include <stdio.h>
/* Reverses arr[0..i] */
void flip(int arr[], int i)
{
int temp, start = 0;
while (start < i)
{
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
// Returns index of the maximum element in arr[0..n-1]
int findMax(int arr[], int n)
{
int mi, i;
for (mi = 0, i = 0; i < n; ++i)
if (arr[i] > arr[mi])
mi = i;
return mi;
}
// The main function that sorts given array using flip operations
int pancakeSort(int *arr, int n)
{
for (int curr_size = n; curr_size > 1; --curr_size)
{
// Find index of the maximum element in arr[0..curr_size-1]
int mi = findMax(arr, curr_size);
//Move the maximum element to end of current array if it's not already at the end
if (mi != curr_size-1)
{
//To move at the end, first move maximum number to beginning
flip(arr, mi);
// Now move the maximum number to end by reversing current array
flip(arr, curr_size-1);
}
}
}
// A utility function to print n array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
}
// Driver program to test above function
int main()
{
int arr[] = {23, 10, 20, 11, 12, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
pancakeSort(arr, n);
puts("Sorted Array ");
printArray(arr, n);
return 0;
}
C++
#include<bits/stdc++.h>
using namespace std;
/* Reverses arr[0..i] */
void flip(int arr[], int i)
{
int temp, start = 0;
while (start < i)
{
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
// Returns index of the maximum element in arr[0..n-1]
int findMax(int arr[], int n)
{
int mi, i;
for (mi = 0, i = 0; i < n; ++i)
if (arr[i] > arr[mi])
mi = i;
return mi;
}
// The main function that sorts given array using flip operations
int pancakeSort(int *arr, int n)
{
for (int curr_size = n; curr_size > 1; --curr_size)
{
// Find index of the maximum element in arr[0..curr_size-1]
int mi = findMax(arr, curr_size);
// Move the maximum element to end of current array if it's not already at the end
if (mi != curr_size-1)
{
// To move at the end, first move maximum number to beginning
flip(arr, mi);
// Now move the maximum number to end by reversing current array
flip(arr, curr_size-1);
}
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout<< arr[i]<<" ";
}
// Driver program to test above function
int main()
{
int arr[] = {23, 10, 20, 11, 12, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
pancakeSort(arr, n);
cout<<"Sorted Array "<<endl;
printArray(arr, n);
return 0;
}
Python
# Reverses arr[0..i]
def flip(arr, i):
start = 0
while start < i:
temp = arr[start]
arr[start] = arr[i]
arr[i] = temp
start += 1
i -= 1
# Returns index of the maximum element in arr[0..n-1]
def findMax(arr, n):
mi = 0
for i in range(0,n):
if arr[i] > arr[mi]:
mi = i
return mi
# The main function that sorts given array using flip operations
def pancakeSort(arr, n):
curr_size = n
while curr_size > 1:
# Find index of the maximum element in arr[0..curr_size-1]
mi = findMax(arr, curr_size)
# Move the maximum element to end of current array if it's not already at the end
if mi != curr_size-1:
# To move at the end, first move maximum number to beginning
flip(arr, mi)
# Now move the maximum number to end by reversing current array
flip(arr, curr_size-1)
curr_size -= 1
# A utility function to print an array of size n
def printArray(arr, n):
for i in range(0,n):
print ("%d"%( arr[i]),end=" ")
# Driver program
arr = [23, 10, 20, 11, 12, 6, 7]
n = len(arr)
pancakeSort(arr, n);
print ("Sorted Array ")
printArray(arr,n)
Complexity :
The number of flips required to sort the array is in the order of 'n'. In the best case, the array is sorted and no flips are required. In the worst case, the array consists of alternating smallest and largest numbers ([0, 9, 1, 8, 2, 7, 3, 6, 5, 4]) and requires 2n-3 flips. Therefore, in terms of number of flips the time complexity is O(n).
Since the only operation considered here is "flip", the comparisons become irrelevant. So, the comparison operations for finding the maximum element of the current array is ignored and time complexity is only represented in terms of the number of flips, also known as the pancake number.
- Worst case time complexity:
Θ(n) - Average case time complexity:
Θ(n) - Space complexity:
Θ(n)
Applications
- Pancake sorting appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.
- It is used when the only allowed operation to sort a sequence is reversing.
