Pancake Sort Algorithm | Prefix Reversal Sorting Method

Description

Pancake Sort is a sorting algorithm that works by repeatedly flipping portions of the array, similar to flipping pancakes with a spatula. The algorithm finds the maximum element in the unsorted portion of the array, brings it to the top with one flip, and then flips it to its correct position with another flip. This process continues until the entire array is sorted. The algorithm gets its name from the analogy of a cook sorting a stack of pancakes by size, where they can only use a spatula to flip some pancakes from the top of the stack. While not practical for real-world applications due to its O(n²) complexity, Pancake Sort is an interesting theoretical sorting algorithm that demonstrates problem-solving with a limited set of operations.

How It Works

Find the largest element in the unsorted portion of the array
Use the first flip to move this element to the top of the array
Use a second flip to move the element to its correct position at the end
Reduce the size of the unsorted portion by 1
Repetir los pasos 1-4 hasta que todo el arreglo esté ordenado

Visualization

Speed:

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

Quick Info

Pancake Sort