Interactive Programming Education Platform

Logic Practice

In this guide, we will explore pancake sorting in C++ along with illustrative examples.

When a spatula can be inserted at any point within the stack and utilized to invert every pancake above it, the computational problem of arranging a disorderly stack of pancakes by size is referred to as pancake sorting. The smallest number of flips required to arrange a specific number of pancakes is termed a pancake number.

Its primary objective is to function akin to the selection sort method. The process involves iteratively diminishing the size of the array under consideration by appending the largest element at the final position.

Program Explanation:

✅ Create a method called flip(Arr, i) that flips the order of the array arr's first i members.
✅ Create the function pancakeSort(Arr), which returns the input array sorted. You can use only the flip function to make changes in the array.

Algorithm:

Let the provided array be referred to as Arr with the array size denoted as '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)

Program:

Let's consider an instance to showcase the pancake sorting algorithm in C++:

Example


#include<iostream>
using namespace std;  
void flip(int array[], int i)  
{  
int temp, start = 0;  
while (start < i)  
{  
temp = array[start];  
array[start] = array[i];  
array[i] = temp;  
start++;  
i--;  
}  
}  
int findMax(int array[], int n)  
{  
int m, i;  
for (m = 0, i = 0; i < n; ++i)  
if (array[i] > array[m])  
m = i;  
return m;  
}   
void pancake_Sort(int *array, int n)  
{  
for (int curr_size = n; curr_size > 1; --curr_size)  
{  
int m = findMax(array, curr_size);  
if (m != curr_size-1)  
{  
flip(array, m);   
flip(array, curr_size-1);  
}  
}  
} 
void printArray(int array[], int n)  
{  
for (int i = 0; i < n; ++i)  
cout<< array[i]<<" ";  
}  
int main()  
{  
int array[] = {100, 1, 5, 20, 3, 12, 21};  
int n = sizeof(array)/sizeof(array[0]);  
pancake_Sort(array, n);  
cout<<"Sorted Array "<<endl;  
printArray(array, n);  
return 0;  
}

Output:

Complexity:

Time Complexity:

The pancake sorting algorithm operates with a time complexity of O(n2), where 'n' represents the quantity of elements within the input array.

The most significant item might need a maximum of n flips (reversals) to ascend to the stack's peak under the worst circumstances, succeeded by n-1 flips to relocate the second most substantial item to the subsequent position, and so on. Consequently, the time complexity is quadratic.

Space Complexity:

The pancake sorting algorithm boasts an O(1) space complexity, meaning it consistently demands a set amount of additional memory regardless of the input's scale.

An in-place sorting technique, known as pancake sorting, arranges the elements within the original array without requiring additional memory relative to the input size.

Pancake Sorting In C++