Prove that it is always optimal to swap any element into its final position.

Think of the array as a permutation, and consider cycles in the permutation. Define $$$f(A)$$$ as the sum of one minus the size of each cycle, where fixed points (elements in their final positions) are not counted. The $$$f$$$ value of a sorted array is $$$0$$$. Prove that any swap decreases $$$f$$$ by at most $$$1$$$, and there's always an operation that decreases $$$f$$$ by $$$1$$$.

How can you use knowledge of graph theory to easily determine how many swaps it takes to sort each group of elements?

Stop posting blogs for questions which're already google-able