i was implementing pancake 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?
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.
The problem of finding the minimum number of flips to pancake-sort an array is still open.
