1
$\begingroup$

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?

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

1 Answer 1

Reset to default
4
$\begingroup$

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.

The sequence is known as AA058986.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for letting me know of this problem. It seems also that the f(n) = 2n - 3 could work with my current work. $\endgroup$
    – user79780
    Nov 6, 2017 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.