Pancake Sorting in C++
In computer science and mathematics, pancake sorting is the task of sorting a stack of pancakes into a particular order, typically from the largest at the bottom to the smallest at the top or vice versa. Its main objective is to flip the pancakes as few times as possible while still placing them in the proper order.
To flip pancakes, you must first put a spatula (or other similar object) into the stack at a certain point, lift the pancakes above the spatula, and flip them over. It is comparable to grabbing a section of the stack and flipping the pancakes in that portion.
Algorithm:
- Start with the pancake stack that is not sorted.
- Do the following for each pancake in the stack, going from the largest to the smallest:
- In the remaining stack, locate the index of the largest unsorted pancake. To accomplish this, start at the top of the stack and scan down to the size of the remaining stack.
- Use a flip operation to raise the largest unsorted pancake to the top of the stack if it isn't there already. A spatula or other similar object can be used for this.
- Now, the biggest pancake will be on top of the stack following the flip. After that, flip the object to the appropriate spot in the sorted sequence. As of this moment, the amount of the remaining stack is in the correct position. By doing this, you can be confident that the biggest pancake will be at the bottom of the stack that is still unsorted.
- From largest to smallest, repeat step 2 for each pancake in the stack.
- The stack will be arranged in the desired order once all the pancakes have been examined.
- Through a series of flips, this algorithm will sort the stack of pancakes.
- This algorithm's worst-case time complexity is O(n2), where n is the total number of pancakes in the stack. It can be optimized in practice to reduce the number of flips.
Program of pancake sorting:
Let's take an example to demonstrate the pancake sorting in C++:
#include <iostream>
#include <vector>
using namespace std;
// Helper function to reverse the order of elements in a vector
void reverse(vector<int>& arr, int start, int end) {
while (start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}
}
// Find the index of the maximum element in the vector up to the given index
int findMaxIndex(vector<int>& arr, int endIndex) {
int maxIndex = 0;
for (int i = 1; i <= endIndex; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
// Pancake sorting algorithm
void pancakeSort(vector<int>& arr) {
int n = arr.size();
for (int size = n; size > 1; size--) {
int maxIndex = findMaxIndex(arr, size - 1);
// If the maximum element is not already at the top, flip it to the top
if (maxIndex != size - 1) {
// First, move the maximum element to the beginning
if (maxIndex != 0) {
cout << "Flip " << maxIndex + 1 << " ";
reverse(arr, 0, maxIndex);
}
// Then, move it to the correct position
cout << "Flip " << size << " ";
reverse(arr, 0, size - 1);
}
}
}
int main() {
vector<int> pancakes = {3, 1, 2, 4, 6, 5};
cout << "Original Stack: ";
for (int val: pancakes) {
cout << val << " ";
}
cout << endl;
pancakeSort(pancakes);
cout << "\nSorted Stack: ";
for (int val: pancakes) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Explanation:
1. Source Stack:
- In this example, the pancake input stack is first defined as a pancake vector of numbers.
2. Loop for sorting pancakes:
- A loop at the heart of the algorithm iterates from the largest pancake size (equal to the number of pancakes) down to 1.
- The size variable, which has a starting value of n (the size of the stack) and decreases with each iteration, governs this loop.
3. Where to Find the Biggest Unsorted Pancake:
- The program to locate the largest unsorted pancake in the current region of the stack (up to index size - 1) during each iteration of the loop uses the findMaxIndex function.
- It shows which pancake is the biggest and needs to be sorted first.
4. Making pancake flips:
- The algorithm flips a series of pancakes to shift the largest unsorted pancake to its proper position in the sorted order if it is not already at the top of the stack (maxIndex is not equal to size - 1):
- It might flip the largest pancake first to position it at the top of the stack. It used the reverse function.
- After that, the largest pancake is flipped once more to be placed correctly within the remaining unsorted area of the stack.
5. Steps Displaying:
- The program displays the action taken at each flip phase. For instance, it prints "Flip 3" to show that the top three pancakes in the stack have been flipped.
- It enables you to see the flips in order and watch how the biggest pancakes are sorted one at a time.
6. Iterate Until Sorted:
- Until the entire stack is sorted, the loop iterates continuously.
- It makes sure that the largest unsorted pancake is placed correctly in each iteration, leading to a stack that is completely sorted in the end.
7. Displaying the Sorted Stack:
- In sorted order, the program displays the stack of pancakes after the loop's final iteration.
Finding the largest unsorted pancake and flipping it a few times to move it to the right location are the keys to successfully sorting pancakes. This process is repeated until all of the pancakes are sorted. The code keeps track of the index of the largest unsorted pancake, flips the necessary pancakes to achieve sorting, and visualises each step.