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?

  • 2
    (b) is a special case of (a), isn't it?2012-10-12
  • 0
    http://en.wikipedia.org/wiki/Insertion_sort Might be of use for a, and: http://en.wikipedia.org/wiki/Bubble_sort for b, both are pretty standard algorithms.2012-10-12
  • 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