[Interview Preparation Kit] Array-4

Problem

You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

[example]

i   arr                         swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

Idea

앞에서부터 맞는 숫자가 있는지 확인,
틀리면, 그 숫자를 제자리로 찾아준다.

Solution

def minimumSwaps(arr):
    swap = 0
    for i in range(len(arr)):
        while(arr[i] != i+1):
            temp = arr[i]
            arr[i] = arr[temp-1]
            arr[temp-1] = temp
            swap += 1
    return swap