non--stop's blog

minimum swaps required to sort an array
By non--stop, history, 6 years ago, In English

question suggest some approach and reason behind it

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply