Sorting a permutation with minimum cost

Question

I am given a permutation of elements {1, 2, 3, ..., N} and I have to sort it using a swap operation. An operation which swaps elements x, y has cost min(x,y).

I need to find out the minimum cost of sorting the permutation. I tought about a greedy going from N to 1 and putting each element on it's position using a swap operation, but this is not a good idea.

Answer 1

Would this be optimal:

Find element 2
If it is not at correct place already

    Find element at position 2
    If swapping that with 2 puts both to right place

        Swap them
        Cost = Cost + min(2, other swapped element)

repeat

   Find element 1
   If element 1 is at position 1

      Find first element that is in wrong place
      If no element found

          set sorted true

      else

         Swap found element with element 1
         Cost = Cost + 1

   else

      Find element that should go to the position where 1 is
      Swap found element with element 1
      Cost = Cost + 1

until sorted is true

Answer 2

If seeks are trivial, then the minimum number of swaps will be determined by the number of cycles. It would follow a principle similar to Cuckoo Hashing. You take the first value in the permutation, and look at the value at the index of the value at the original index. If those match, then swap for a single operation.

[3 2 1] : Value 3 is at index one, so look at the value at index 3.
[3 2 1] : Value 1 is at index 3, so a two index cycle exists. Swap these values.

If not, push the first index onto a stack and seek the index for the value of the second index. There will eventually be a cycle. At that point, start swapping by popping values off the stack. This will take a number of swaps equal to n-1, where n is the length of the cycle.

[3 1 2] : Value 3 is at index one, so look at the value at index 3.
[3 1 2] : Value 2 is at index 3, so add 3 to the stack and seek to index 2. Also store 3 as the beginning value of the cycle.
[3 1 2] : Value 1 is at index 2, so add 2 to the stack and seek to index 1.
[3 1 2] : Value 3 is the beginning of the cycle, so swap pop 2 off the stack and swap values 1 and 2.
[1 3 2] : Pop 3 off the stack and swap 2 and 3, resulting in a sorted list with 2 swaps.
[1 2 3]

With this algorithm, the maximum number of swaps will be N-1, where N is the total number of values. This occurs when there is an N length cycle.

EDIT : This algorithm gives the minimum number of swaps, but not necessarily the minimum value using the min(x, y) function. I haven't done the math, but I believe that the only time when swap(x, y) = {swap(1, x), swap(1, y), swap(1, x)} shouldn't be used is when x in {2,3} and n < 2; Should be easy enough to write that as a special case. It may be better to check and place 2 and 3 explicitly, then follow the algorithm mentioned in the comments to achieve sorting in two operations.

EDIT 2 : Pretty sure this will catch all cases.

while ( unsorted ) {
    while ( 1 != index(1) )
        swap (1 , index (1) )

    if (index(2) == value@(2))
        swap (2, value@(2) )

    else
        swap (1 , highest value out of place)
}