Log In

Sorting

Posted on: February 19th, 2014 by
4

You are given an array of n distinct integers. A swap is interchanging the value of two positions in the array. What is the minimum number of swaps required to sort the array?

For example: If the array is [2,1,3], we need only 1 swap (swap 1 and 2). If the array is [2,3,1], we need 2 swaps (swap 2 and 3, then swap 1 and 3).

- via Stack Overflow


4 Responses to Sorting

  1. Kerstin had this to say about that:

    Interpret your array as a permutation, and write it in cycle notation. Then the number of swaps needed is the sum of the lengths of all cycles except the one-cycles.

  2. Kerstin had this to say about that:

    Oops, slight mistake. What you want is
    sum_{all cycles} (length of cycle - 1)

    • Lizard had this to say about that:

      This is one way to sort the array, but how do we know this is the minimum number of swaps needed?

      • admin had this to say about that:

        @Lizard: Proof: After each swap, the number of permutation cycles can increase by at most 1.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}