Pancake Sort
Description
Pancake Sort is a unique sorting algorithm that operates by repeatedly flipping (reversing) portions of the array, drawing its name from the analogy of sorting a stack of pancakes by size using only a spatula. Unlike traditional sorting algorithms that can swap any two elements, Pancake Sort is restricted to a single operation: reversing the order of elements from the beginning of the array up to a chosen position.
The algorithm works by systematically moving the largest unsorted element to its correct position through a two-flip process. First, it locates the maximum element in the unsorted portion and flips the array from the start to that position, bringing the maximum to the front. Then, it performs a second flip to move this element from the front to its final sorted position at the end of the unsorted portion. This process repeats, with the unsorted portion shrinking by one element each iteration, until the entire array is sorted.
While Pancake Sort has a time complexity of O(n²) and is not efficient for practical applications, it serves as an interesting theoretical problem in computer science. It demonstrates how sorting can be achieved with a highly restricted set of operations and has applications in certain specialized hardware architectures where only prefix reversal operations are available. The algorithm also poses interesting questions about the minimum number of flips required to sort any given sequence.
How It Works
The Pancake Sort algorithm follows a systematic approach to sort an array using only flip operations. Here's a detailed breakdown of the process:
- Find the maximum element: Scan through the unsorted portion of the array (initially the entire array) to locate the position of the largest element. This requires comparing each element to find the maximum.
- First flip - Bring to top: If the maximum element is not already at the beginning of the array, perform a flip operation from index 0 to the position of the maximum element. This reverses the order of all elements up to and including the maximum, effectively moving it to the front of the array.
- Second flip - Move to position: Now that the maximum element is at the front, perform another flip from index 0 to the end of the unsorted portion. This places the maximum element in its final sorted position at the end of the current unsorted segment.
- Reduce unsorted portion: Decrease the size of the unsorted portion by one, as the largest element is now in its correct position and doesn't need to be considered in subsequent iterations.
- Repeat until sorted: Continue steps 1-4, each time working with a smaller unsorted portion, until only one element remains. At this point, the entire array is sorted in ascending order.
Visualization
Click Start to begin visualization
Implementation
def flip(arr, i):
start = 0
while start < i:
arr[start], arr[i] = arr[i], arr[start]
start += 1
i -= 1
def find_max(arr, k):
max_index = 0
for i in range(k):
if arr[i] > arr[max_index]:
max_index = i
return max_index
def pancake_sort(arr):
n = len(arr)
for curr_size in range(n, 1, -1):
# Find maximum in the unsorted subarray
max_idx = find_max(arr, curr_size)
if max_idx != curr_size - 1:
# If the maximum is not at the end
if max_idx != 0:
# Bring maximum to the top
flip(arr, max_idx)
# Move maximum to its final position
flip(arr, curr_size - 1)
return arr
# Usage example
if __name__ == "__main__":
arr = [23, 10, 20, 11, 12, 6, 7]
print("Original array:", arr)
pancake_sort(arr)
print("Sorted array:", arr)
#include <iostream>
#include <vector>
class PancakeSort {
private:
static void flip(std::vector<int>& arr, int i) {
int start = 0;
while (start < i) {
std::swap(arr[start], arr[i]);
start++;
i--;
}
}
static int findMax(std::vector<int>& arr, int k) {
int max_index = 0;
for (int i = 0; i < k; ++i)
if (arr[i] > arr[max_index])
max_index = i;
return max_index;
}
public:
static void sort(std::vector<int>& arr) {
int n = arr.size();
for (int curr_size = n; curr_size > 1; --curr_size) {
// Find maximum in the unsorted portion
int max_idx = findMax(arr, curr_size);
if (max_idx != curr_size - 1) {
// If maximum is not at the end
if (max_idx != 0)
// Bring maximum to the top
flip(arr, max_idx);
// Move maximum to its final position
flip(arr, curr_size - 1);
}
}
}
};
// Usage example
int main() {
std::vector<int> arr = {23, 10, 20, 11, 12, 6, 7};
std::cout << "Original array: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
PancakeSort::sort(arr);
std::cout << "Sorted array: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
return 0;
}
public class PancakeSort
{
private static void Flip(int[] arr, int i)
{
int start = 0;
while (start < i)
{
(arr[start], arr[i]) = (arr[i], arr[start]);
start++;
i--;
}
}
private static int FindMax(int[] arr, int k)
{
int maxIndex = 0;
for (int i = 0; i < k; i++)
if (arr[i] > arr[maxIndex])
maxIndex = i;
return maxIndex;
}
public static void Sort(int[] arr)
{
int n = arr.Length;
for (int currSize = n; currSize > 1; currSize--)
{
// Find maximum in the unsorted portion
int maxIdx = FindMax(arr, currSize);
if (maxIdx != currSize - 1)
{
// If maximum is not at the end
if (maxIdx != 0)
// Bring maximum to the top
Flip(arr, maxIdx);
// Move maximum to its final position
Flip(arr, currSize - 1);
}
}
}
// Usage example
public static void Main(string[] args)
{
int[] arr = { 23, 10, 20, 11, 12, 6, 7 };
Console.WriteLine("Original array: " + string.Join(" ", arr));
Sort(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", arr));
}
}
Complexity Analysis
| Case | Time Complexity |
|---|---|
| Best | O(n) |
| Average | O(n²) |
| Worst | O(n²) |
Advantages and Disadvantages
Advantages
- Simple to understand and implement
- In-place sorting (no extra space needed)
- Can be useful in specialized hardware where only flipping operations are allowed
Disadvantages
- Poor time complexity of O(n²)
- Not practical for large datasets
- Requires two flips for most operations