# Minimum amount of swaps needed to sort a stack

Given a stack, what is the minimum amount of swaps needed to sort it? Since the bottom of it stays intact and we slowly move to the upper part of it, if the stack contains n elements, the amount of swaps f(n) would be

f(n) < n

for n = 1, 2, 3, 4, is that correct? I cannot find a more accurate way to express it. Also, how do we calculate the f(n) for n > 4?

• It is not clear what you want to do. Can you define what 'swap' means in your problem? Nov 6, 2017 at 1:45
• @klaus You can "flip" the "cakes" of the stack in order to sort them
– user79780
Nov 6, 2017 at 12:33

Your problem is known as Pancake sorting and it is not true that $f(n) < n$. The minimum number of swaps is between $\frac{15n}{14}$ and $\frac{18n}{11}$.
Currently we know empirically that $P_{17} = 19$, which is the Pancake number, giving lower bound of 19 flips in the stack of 17 elements.
• Thank you for letting me know of this problem. It seems also that the f(n) = 2n - 3 could work with my current work.