King Arthur has a shelf with $10$ books, numbered $1,2,3,\dots,10$. Over the years, the volumes got disordered. Arthur tries to order the books in the increasing order by exchanging positions of two books at once. Since the books are heavy, he can only switch two volumes each day. Help Merlin to order the books.

E.g., If a permutation is $10, 9, 8, 7, 6, 5, 4, 3, 2, 1$ then we need just 5 switches to sort it in ascending order

Note: in the worst case there will be $9$ switches.

  1. Find the permutation corresponding to the worst case

  2. How to find the minimum number of switches required for a given permutation. (Algorithm & if possible code in either of C, C++, python)

  • $\begingroup$ Whathave you tried ? $\endgroup$ – Aryadeva Aug 1 at 12:51
  • 1
    $\begingroup$ I was able to solve it manually, better say Trial N error ( Answer to Q1. 10, 1, 2, 3, 4, 5, 6, 7, 8, 9). but I wish to know the algorithm $\endgroup$ – Shambhav Agrawal Aug 1 at 13:24
  • $\begingroup$ You should add your attempt to your question that's better to get good answers Agrawal. $\endgroup$ – Aryadeva Aug 1 at 13:31

Decompose your permutation into cycles. Each one is sorted independently and a $k$ cycle takes $k-1$ swaps. If there are $n$ total books it takes the number of cycles less than $n$ swaps to sort the books. You should prove this.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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