Pancake Sorting

Problem Statement

In the “Pancake Sorting” problem we have given an array of integers A[]. Sort the array by performing a series of pancake flips. In one pancake flip we do the following steps:

• Choose an integer k where 1 <= k <= arr.length.
• Reverse the sub-array arr[0…k-1] (0-indexed).

Input Format

The first and only one line containing an integer N.

Second-line containing N space-separated integer.

Output Format

Print an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10*arr.length() flips will be judged as correct.

Constraints

• 1<=N<=10^3
• 1<=A[i]<=N
• All integers in A[] are unique.

Example

5
3 2 4 1 5

3 4 2 3 2

Algorithm for Pancake Sorting

The main idea is to find the maximum element in the array and place it at the end of the array and decrease the size of the array.

Till the size of the array is greater than 1, decrement size

1. Find the maximum element in the current size array.

2. flip the array till maximum number ie, now the maximum number is at starting of the array.

3. Now, flip the array of current size ie, now the maximum number is at the end of the array.

4. Print the sorted array.

Implementation

C++ Program for Pancake Sorting

#include <bits/stdc++.h>
using namespace std;

bool isSorted(vector<int>& arr)
{
    if(arr.size()==0 || arr.size()==1)
    {
        return 1;
    }
    for(int i=1;i<arr.size();i++)
    {
        if(arr[i-1]>arr[i])
        {
            return 0;
        }
    }
    return 1;
}

void flip(vector<int>& arr,int k)
{
    int i=0,j=k-1;
    while(i<j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j] = temp;
        i++;j--;
    }
}
    
vector<int> pancakeSort(vector<int>& arr) {
    vector<int> res;
    int k=0,j=0,index=-1,large=INT_MIN,n=arr.size();
    while(!isSorted(arr))
    {
        for(int i=0;i<n-j;i++)
        {
            if(large<arr[i])
            {
                large=arr[i];
                index=i;
            }
        }
        // bringing the largest values at head
        k=index+1;
        flip(arr,k);
        res.push_back(k);
        // fliping the head value at its sorted place
        k=n-j;
        flip(arr,k);
        res.push_back(k);
        j++;
        large=INT_MIN;
    }
    return res;
}

int main()
{
   int n;
   cin>>n;
   vector<int> v;
   for(int i=0;i<n;i++)
   {
       int x;
       cin>>x;
       v.push_back(x);
   }
   pancakeSort(v);
   for(auto u: v)
   {
       cout<<u<<" ";
   }
   return 0;
}

Java Program for Pancake Sorting

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class sum
{
    static void pancakeSort(int A[], int n) 
    {
        List<Integer> ans = new ArrayList<>();
        for (int valueToSort = A.length; valueToSort > 0; valueToSort--) 
        {
            int index = sum.find(A, valueToSort);
            if (index == valueToSort - 1)
                continue;
            if (index != 0) 
            {
                ans.add(index + 1);
                sum.flip(A, index + 1);
            }
            ans.add(valueToSort);
            sum.flip(A, valueToSort);
        }
        for(int i=0;i<n;i++) 
  {
      System.out.print(ans.get(i)+" ");
  }
        System.out.println();
    }
    public static void flip(int[] sublist, int k) 
    {
        int i = 0;
        while (i < k / 2) 
        {
            int temp = sublist[i];
            sublist[i] = sublist[k - i - 1];
            sublist[k - i - 1] = temp;
            i += 1;
        }
    }
    public static int find(int[] a, int target) 
    {
        for (int i = 0; i < a.length; i++)
            if (a[i] == target)
                return i;
        return -1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        pancakeSort(a, n);
    }
}

5 
3 2 4 1 5

3 4 2 3 2

Complexity Analysis for Pancake Sorting

Time Complexity

O(n^2) where n is the size of the given array.

• In the algorithm, we run a loop with N iterations.
• Within each iteration, we are dealing with the corresponding prefix of the list. Here we denote the length of the prefix as $k$, e.g. in the first iteration, the length of the prefix is N. While in the second iteration, the length of the prefix is N-1.

Space Complexity

O(n) where n is the size of the given array.

• Within the algorithm, we use a list to maintain the final results, which are proportional to the number of pancake flips.
• For each round of iteration, at most, we would add two pancake flips. Therefore, the maximal number of pancake flips needed would be $2*N$.
• As a result, the space complexity of the algorithm is $\mathcal{O}(N)$. If one does not take into account the space required to hold the result of the function, then one could consider the above algorithm as a constant space solution.