# Pancake Sort

- Pancake Sort Algorithm
- Pancake Sort Example
- Pancake Sort Algorithm Implementation
- 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()`

##### Initialize the size of the unsorted subarray as

`curr = n-1`

and iteratively reduce its size by`1`

.##### Find the index of maximum element

`mi`

in the unsorted subarray.##### Flip

`A[0, ... , mi]`

using`flip(A,mi)`

to move maximum element`A[i]`

at the index`0`

.##### Flip

`A[0, ... , i]`

using`flip(A,i)`

to move the maximum element`A[i]`

at its correct position.

`Flip()`

##### Swap the element at the first index

`f`

with that at the last index`e`

.##### Increment

`f`

and decrement`e`

.##### Repeat above steps until

`f`

<=`e`

.

## 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

`Flip(mi)` |
[7, 1, 2, 5, 3, 6, 4] |

`Flip(6)` |
[ 4, 6, 3, 5, 2, 1, 7] |

- Second Iteration

`mi`

= 1, `curr`

= 6

`Flip(mi)` |
[6, 4, 3, 5, 2, 1, 7] |

`Flip(5)` |
[1, 2, 5, 3, 4, 6, 7] |

- Third Iteration

`mi`

= 2, `curr`

= 5

`Flip(mi)` |
[5, 2, 1, 3, 4, 6, 7] |

`Flip(4)` |
[4, 3, 1, 2, 5, 6, 7] |

- Fourth Iteration

`mi`

= 0, `curr`

= 4

`Flip(mi)` |
[4, 3, 1, 2, 5, 6, 7] |

`Flip(3)` |
[2, 1, 3, 4, 5, 6, 7] |

- Fifth Iteration

`mi`

= 2, `curr`

= 3

`Flip(mi)` |
[3, 1, 2, 4, 5, 6, 7] |

`Flip(2)` |
[2, 1, 3, 4, 5, 6, 7] |

- Sixth Iteration

`mi`

= 0, `curr`

= 2

`Flip(mi)` |
[2, 1, 3, 4, 5, 6, 7] |

`Flip(1)` |
[1, 2, 3, 4, 5, 6, 7] |

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^{2}). 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^{2}.

- 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^{2}).

- 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.