How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order

Question

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)

Answer 1

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.