# Analysis of Pan-cake sorting

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort).

However it is mentioned that the A[i] has to be a permutation of [1, 2, ..., A.length].

My question is, what if A[i] is not a permutation of [1,2,..., A.length]? How to solve that?

• Sorry tedd but I do not see the point, i.e., for any arrangement of symbols you can always create a permutation by simply mapping each symbol in the arrangement with a natural number representing its desired location. As all symbols should be in different locations, a permutation naturally arises so that this problem is definitely a permutation state space problem. Maybe I missed some point though ... – Carlos Linares López Nov 28 '19 at 22:19

Let's suppose the input array is $$A = [3,1,4,5,2]$$. When sorting this array using pancake sorting, only flips of prefixes of the array are allowed. Flipping the first four elements, i.e. replacing $$3145$$ by $$5413$$, gives $$A = [5,4,1,3,2]$$. Then, flipping all five elements gives $$[2,3,1,4,5]$$, which brings the largest element to its correct position. By repeating this process to bring the next largest element to the last-but-one position, and so on, the array can be sorted.
The number of flips required to sort an array of length $$n$$ is at most $$2n-3$$. This is because bringing the largest $$n-2$$ elements to their correct positions can be done using at most $$2n-4$$ flips (because at most two flips are required for each element, as mentioned in previous paragraph). Finally, the elements in the first two positions can be sorted using at most one flip.