Given an array of size N containing distinct elements from 0 to N-1, find the mini um number of swaps needed to sort the array.
a = [0, 1, 2, 5, 4, 3]
can be sorted by swapping 5 and 3, thus the answer in this case is 1.
An interesting property can be observed for this array.
The elements of the array form a cycle, where an element
n points next to the element
If the entire array is sorted, then there are no cycles as each element will point to itself.
If the entire array is out of place, then there is one cycle of length equal to N-1.
Now the point to be noted is that each cycle of length
l can be sorted by making