0
$\begingroup$

We have permutation $p$ of elements $1,\ldots, n$. What is the minimal number of operations required to sort this permutation (in ascending order), where permitted operations are:

a) select some number and insert it in any position

b) select two adjacent numbers and swap them

My intuition is that the answer for the first case is: $n-\operatorname{lis}(p)$ where $\operatorname{lis}(p)$ is the longest increasing subsequence of permutation $p$, because these elements can stay in their positions and every other element we can insert in right position using one operation.

For the second, answer will be the number of inversions in permutation $p$ - that is my observation, I don't see any argument, even such naive like this above;

These are only my intuitions, I'm not sure what are the answers. What is the most interesting for me - how to deduce those answers, or if we can guess them, how to prove we found right formulas?

  • 0
    (a) and (b) are disjoint cases.. I don't want to sort this permutation, please read my post carefully - I want to determine what is the minimal number of permitted operations (for (a) and (b) separately) required to sort $p$.2012-10-12

2 Answers 2

1

For (b), notice that a swap increases or decreases the number of inversions by one and that a sorted sequence has no inversions.

Likewise for (a), notice that inserting one number somewhere, at best, increases the length of some monotone subsequence by one (or, at worst, decreases it by a bunch) and a sorted sequence is all monotone.

0

I was writing up my solution but Karolis got it in first. I would add though that (a) is actually harder than (b) since an insertion has a chance to do nothing relating to monotone subsequence.

A general intuition for these proofs is that you notice some property about a sorted list (or I guess, an unpermuted one) and then you consider how the operations get you "closer" to that property. It is a bit unintuitive showing that the minimal number of operations requires you to get "closer", but it's possible to show (most intuitively by contradiction).