Pancake Sort Program with Explanation and Code

2025-11-19 pancake sort flipping sort prefix reversal sort algorithm explanations python pancake sort c pancake sort php pancake sort javascript pancake sort csharp pancake sort array flipping algorithm

Pancake Sort is a flipping-based sorting algorithm that repeatedly reverses prefixes of an array to position the largest remaining element. This page explains the concept clearly and provides complete code examples in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Pancake Sort?

Pancake Sort is a comparison-based sorting algorithm that sorts an array by repeatedly reversing prefixes (flipping elements), similar to flipping a stack of pancakes with a spatula. The largest unsorted element is brought to the front using one flip, then placed at its correct position using another flip. This process is continued until the entire array is sorted.

Steps to Solve

  1. Find the largest element in the unsorted portion of the array.
  2. Flip the array up to that index to bring the element to the front.
  3. Flip the array up to the end of the unsorted portion to move the largest element to its correct position.
  4. Reduce the size of the unsorted portion by one.
  5. Repeat the process until the full array is sorted.
  6. Return the sorted array.

Key Points

  • Sorting is performed using only “flip” operations.
  • Time complexity: O(n²) in worst and average cases.
  • In-place sorting algorithm (no extra space required).
  • Inspired by the real-world act of flipping pancakes.
  • Simple but not efficient for large datasets.
  • Good for demonstrating prefix-reversal algorithms.

Program Code


def flip(arr, k):
    arr[:k] = arr[:k][::-1]

def find_max(arr, n):
    max_index = 0
    for i in range(n):
        if arr[i] > arr[max_index]:
            max_index = i
    return max_index

def pancake_sort(arr):
    n = len(arr)
    for size in range(n, 1, -1):
        max_index = find_max(arr, size)

        if max_index != size - 1:
            flip(arr, max_index + 1)
            flip(arr, size)

arr = list(map(int, input("Enter numbers: ").split()))
pancake_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

void flip(int arr[], int k) {
    int start = 0;
    while (start < k) {
        int temp = arr[start];
        arr[start] = arr[k];
        arr[k] = temp;
        start++;
        k--;
    }
}

int findMax(int arr[], int n) {
    int maxIndex = 0;
    for (int i = 1; i < n; i++)
        if (arr[i] > arr[maxIndex])
            maxIndex = i;
    return maxIndex;
}

void pancakeSort(int arr[], int n) {
    for (int size = n; size > 1; size--) {
        int maxIndex = findMax(arr, size);

        if (maxIndex != size - 1) {
            flip(arr, maxIndex);
            flip(arr, size - 1);
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    pancakeSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function flip(arr, k) {
  let start = 0;
  while (start < k) {
    [arr[start], arr[k]] = [arr[k], arr[start]];
    start++;
    k--;
  }
}

function findMax(arr, n) {
  let maxIndex = 0;
  for (let i = 1; i < n; i++)
    if (arr[i] > arr[maxIndex])
      maxIndex = i;
  return maxIndex;
}

function pancakeSort(arr) {
  for (let size = arr.length; size > 1; size--) {
    let maxIndex = findMax(arr, size);

    if (maxIndex !== size - 1) {
      flip(arr, maxIndex);
      flip(arr, size - 1);
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
pancakeSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {
    static void Flip(int[] arr, int k) {
        int start = 0;
        while (start < k) {
            int temp = arr[start];
            arr[start] = arr[k];
            arr[k] = temp;
            start++;
            k--;
        }
    }

    static int FindMax(int[] arr, int n) {
        int maxIndex = 0;
        for (int i = 1; i < n; i++)
            if (arr[i] > arr[maxIndex])
                maxIndex = i;
        return maxIndex;
    }

    static void PancakeSort(int[] arr) {
        for (int size = arr.Length; size > 1; size--) {
            int maxIndex = FindMax(arr, size);

            if (maxIndex != size - 1) {
                Flip(arr, maxIndex);
                Flip(arr, size - 1);
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        PancakeSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function flip(&$arr, $k) {
    $start = 0;
    while ($start < $k) {
        $temp = $arr[$start];
        $arr[$start] = $arr[$k];
        $arr[$k] = $temp;
        $start++;
        $k--;
    }
}

function findMax($arr, $n) {
    $maxIndex = 0;
    for ($i = 1; $i < $n; $i++)
        if ($arr[$i] > $arr[$maxIndex])
            $maxIndex = $i;
    return $maxIndex;
}

function pancakeSort(&$arr) {
    $n = count($arr);
    for ($size = $n; $size > 1; $size--) {
        $maxIndex = findMax($arr, $size);

        if ($maxIndex != $size - 1) {
            flip($arr, $maxIndex);
            flip($arr, $size - 1);
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
pancakeSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1