Table of Contents
Problem Statement
“Pancake Sorting Problem” is based on pancake sorting. Given an unsorted array, we need to write a program that uses only flip operation to sort the array. Flip is the operation that reverses the array.
Input Format
The first line containing an integer N.
Second-line containing N space-separated integers.
Output Format
The first and only one line containing N space-separated integers denotes the sorted array.
Constraints
- 1<=n<=10^3
- 1<=a[i]<=10^6
Example
9 40 35 12 30 35 20 6 90 80
6 12 20 30 35 35 40 80 90
Approach
We need to write an algorithm that has the time complexity of O(nlogn). If we use the pancake sorting algorithm the time taken will be O(nlogn) because in a loop we will find the maximum element which takes O(n) time. To reduce the time complexity we will use insertion sort, binary search, and flip operation.
The main idea is to find the smallest element ie, arr[j] which is greater than arr[i] in arr[0,..i-1] using binary search. Now, we need to insert arr[i] just before arr[j] by using the flip operation.
Algorithm for Pancake Sorting Problem
1. Find the index of smallest element which is greater than arr[i] in arr[0..i-1] ie, j = ceilSearch(arr, 0, i-1, arr[i]), Here 0 is the starting index, (i-1) is the ending index
ceilSearch Algorithm:
The smallest number which is greater than the given number is known as the ceiling of that number
- If the given element(arr[i]) is less than or equal to the first element in the array of a given size, then return the index of the first element.
- If the element is greater than the last element, then return -1 ie, there is no greater element.
- Here, If the element is the same as the mid element, then return the mid index.
- If the element is greater than the mid element, then either the next element to the mid element is the ceiling of the arr[i], or the ceiling lies in the arr[mid+1….high].
- If the element is less than the mid element, then either the previous element to the mid element is the ceiling of the arr[i], or the ceiling lies in arr[low….mid-1].
2. Now, we need to insert the element arr[i] before arr[j] using flip operations
- flip the elements from index 0 to index j-1.
- Now, flip the elements from index 0 to index i-1.
- flip the elements from index 0 to index i.
- flip the elements from index 0 to index j.
3. Print the sorted array.
Implementation
C++ Program for Pancake Sorting Problem
#include<bits/stdc++.h>
using namespace std;
int ceilSearch(int arr[], int low, int high, int x)
{
int mid;
if(x <= arr[low])
return low;
if(x > arr[high])
return -1;
mid = (low + high)/2;
if(arr[mid] == x)
return mid;
if(arr[mid] < x)
{
if(mid + 1 <= high && x <= arr[mid+1])
return mid + 1;
else
return ceilSearch(arr, mid+1, high, x);
}
if(mid - 1 >= low && x > arr[mid-1])
{
return mid;
}
else
{
return ceilSearch(arr, low, mid - 1, x);
}
}
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--;
}
}
void sorting(int arr[], int size)
{
int i, j;
for(i = 1; i < size; i++)
{
int j = ceilSearch(arr, 0, i-1, arr[i]);
if (j != -1)
{
flip(arr, j-1);
flip(arr, i-1);
flip(arr, i);
flip(arr, j);
}
}
}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sorting(a, n);
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}Java Program for Pancake Sorting Problem
import java.util.Scanner;
class sum
{
public static int ceilSearch(int arr[], int low, int high, int x)
{
int mid;
if(x <= arr[low])
return low;
if(x > arr[high])
return -1;
mid = (low + high)/2;
if(arr[mid] == x)
return mid;
if(arr[mid] < x)
{
if(mid + 1 <= high && x <= arr[mid+1])
return mid + 1;
else
return ceilSearch(arr, mid+1, high, x);
}
if(mid - 1 >= low && x > arr[mid-1])
{
return mid;
}
else
{
return ceilSearch(arr, low, mid - 1, x);
}
}
public static 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--;
}
}
public static void sorting(int arr[], int size)
{
int i;
for(i = 1; i < size; i++)
{
int j = ceilSearch(arr, 0, i-1, arr[i]);
if (j != -1)
{
flip(arr, j-1);
flip(arr, i-1);
flip(arr, i);
flip(arr, j);
}
}
}
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();
}
sorting(a, n);
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
}
}
5 67 2 43 13 87
2 13 43 67 87
Complexity Analysis for Pancake Sorting Problem
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 , 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 .
- As a result, the space complexity of the algorithm is . 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.