Minimum Swaps

Found here

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. You need to find the minimum number of swaps required to sort the array in ascending order.

In [108]:
def min_swaps(arr):
    n = len(arr) - 1
    count = 0
    for i in range(len(arr)):
        if arr[n-i-1] > arr[n-i]:
            count +=1
            print(arr)
            arr[n-i], arr[n-i-1] = arr[n-i-1], arr[n-i]
            
    print(count)
In [109]:
min_swaps([2, 3, 4, 1, 5])

[2, 3, 4, 1, 5]
[2, 3, 1, 4, 5]
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
4
In [110]:
def min_swaps(arr):
    n = len(arr) - 1
    count = 0
    for i in range(len(arr)):
        if arr[n-i-1] > arr[n-i]:
            if arr[i] != i+1:
                pass
            else:
                count +=1
            print(arr)
            arr[n-i], arr[n-i-1] = arr[n-i-1], arr[n-i]
    print(count)
In [104]:
min_swaps([2, 3, 4, 1, 5])

[2, 3, 4, 1, 5]
[2, 3, 1, 4, 5]
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
2
In [96]:
def min_swaps(arr):
    count = 0
    t = 0
    for i in range(len(arr)):
        if arr[t] == i+1:
            print('nope')
        else:
            test = arr[i] - 1
            arr[i], arr[test] = arr[test], arr[i]
            count += 1
            print(arr)
    print(count)
In [81]:
min_swaps([2, 3, 4, 1, 5])

[3, 2, 4, 1, 5]
nope
[3, 2, 1, 4, 5]
nope
nope
2
In [ ]: