Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Created December 7, 2020 05:50
Show Gist options
  • Save anish000kumar/48a8811c929985e387e2884ecbecd72b to your computer and use it in GitHub Desktop.
Save anish000kumar/48a8811c929985e387e2884ecbecd72b to your computer and use it in GitHub Desktop.
Minimum swaps to sort an array
def minSwaps(arr, N):
newArr = [ (arr[i], i) for i in range(len(arr)) ]
newArr.sort()
ans = 0
for i in range(len(newArr)):
j = newArr[i][1]
while newArr[i][1] != newArr[j][1]:
newArr[i], newArr[j] = newArr[j], newArr[i]
ans += 1
j = newArr[i][1]
return ans
@anish000kumar
Copy link
Author

  1. swaps required to go from initial -> sorted version is same as swaps required from sorted -> initial version
  2. sort the array , while keeping track of indices
  3. Now indices are unsorted, but can be sorted using cyclic sort
  4. sort indices using cyclic sort to get the minimum no. of swaps

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment