Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
(b) is a special case of (a), isn't it? –  Henning Makholm Oct 12 '12 at 17:51
    
en.wikipedia.org/wiki/Insertion_sort Might be of use for a, and: en.wikipedia.org/wiki/Bubble_sort for b, both are pretty standard algorithms. –  Alex J Best Oct 12 '12 at 18:03
    
(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$. –  xan Oct 12 '12 at 18:12
add comment

2 Answers

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.

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.