Pancake Sort

1. Pancake Sort Algorithm
2. Pancake Sort Example
3. Pancake Sort Algorithm Implementation
4. Pancake Sort Algorithm Complexity

Pancake sort is a reversal based sorting algorithm. It is based on the real-life problem of resembling pancakes on a plate with the help of a spatula. It gets its name from the flip operation used in the algorithm analogous to flipping pancakes. Unlike most sorting algorithms that try to minimize the number of comparisons required to perform the sort, it tries to sort the array in minimum reversals. Just like selection sort, it also places the maximum element at the end.

Pancake Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

PancakeSort()

Flip()

Pancake Sort Example

Suppose we have the array: (3, 5, 2, 1, 7, 6, 4). We will sort it using the pancake sort algorithm.

• First Iteration

mi = 4, curr = 7

• Second Iteration

mi = 1, curr = 6

• Third Iteration

mi = 2, curr = 5

• Fourth Iteration

mi = 0, curr = 4

• Fifth Iteration

mi = 2, curr = 3

• Sixth Iteration

mi = 0, curr = 2

We get the final sorted array as 1, 2, 3, 4, 5, 6, 7.

Pancake Sort Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;
void flip(int arr[], int i) {
  int temp, start = 0;
  while (start < i) {
    temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    start++;
    i--;
  }
}

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

void pancakeSort(int arr[], int n) {
  for (int i = n; i > 1; i--) {
    int mi = findMax(arr, i);
    if (mi != i - 1) {
      flip(arr, mi);
      flip(arr, i - 1);
    }
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  pancakeSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Pancake Sort Algorithm Complexity

Time Complexity

• Average Case

On average, n-i comparisons are made in the ith pass of pancake sort. So if there are n iterations, then the average time complexity can be given by :

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

Hence the time complexity is of the order of [Big Theta]: O(n²). It can also be calculated by counting the number of loops. There are a total of two loops of n iterations making complexity: n*n = n².

• Worst Case

The worst-case occurs when the elements are alternating small and large elements. A total of 2n-3 flips are required. The number of flips required is of the order of O(n). The worst-case time complexity is [Big O]: O(n²).

• Best Case

The best-case occurs when the array is already sorted, and no flips are required. The best-case time complexity is [Big Omega]: O(n).

Space Complexity

Space Complexity for this algorithm is O(n) because no extra memory other than a temporary variable is required.