Minimum number of swaps required to sort an array

I was reading one interesting post on GeeksForGeeks at https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

I found it very informative. I thought of explaining this problem in my words.

Problem statement:

Given an array of n distinct elements, find the minimum number of swaps required to sort the array.

Example:

Input: {4, 3, 2, 1}
Output: 2
Explanation: Swap index 0 with 3 and 1 with 2 to 
              form the sorted array {1, 2, 3, 4}.

Input: {1, 5, 4, 3, 2}
Output: 2

Solution to this problem lies in sorting this array and observing how many elements have changed their position. For the elements who has not changed their position no swap is needed. For the elements who have changed their positions there will be cycles like following image(from GeeksForGeeks.com)

In the above image there are two cycles of two elements each. To sort this array we need two swaps, one for each cycle. Now look at following image (from GeeksForGeeks.com)

The above array contains two cycles one with 2 elements and one with 3 elements. We need one swap for correcting two element cycle and two swaps for correcting 3 element cycle. 

We need N-1 swaps for correcting a N element cycle. If we have a cycle a->b->c->d->e->a then this 5 element cycle can be corrected by 4 swaps:

1. (a, b)
2. (b, c) note b will be at a's original place
3. (c, d) note c will be at a's original place
4. (d, e) note d will be at a's original place

After 4th swap you notice e is at a's original place already so no swap is needed.

For counting number of swap we can calculate cycle size either forward or backward. If we have a cycle a->b->c->d->e->a .We can start at a's original place in sorted array and see that element e is present there, now we see which element it present at e's original place ,we find d there then we look at d's original place then we find c there. If we continue this way we find a at b's original place when we look for a's original place we find that it was already visited so we break out of the loop. This gives us size of the cycle. We mark all elements of this cycle visited so we don't get into this cycle one again.

Following is the code from GeeksForGeeks:

import java.util.*;
import java.io.*;

class GfG
{
	// Function returns the
	// minimum number of swaps
	// required to sort the array
	public static int minSwaps(int[] nums)
	{
		int len = nums.length;
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0;i<len;i++)
			map.put(nums[i], i);
			
		Arrays.sort(nums);
		
		// To keep track of visited elements. Initialize
		// all elements as not visited or false.
		boolean[] visited = new boolean[len];
		Arrays.fill(visited, false);
		
		// Initialize result
		int ans = 0;
		for(int i=0;i<len;i++) {
		
			// already swapped and corrected or
			// already present at correct pos
			if(visited[i] || map.get(nums[i]) == i)
				continue;
				
			int j = i, cycle_size = 0;
			while(!visited[j]) {
				visited[j] = true;
				
				// move to next node
				j = map.get(nums[j]);
				cycle_size++;
			}
			
			// Update answer by adding current cycle.
			if(cycle_size > 0) {
				ans += (cycle_size - 1);
			}
		}
		return ans;
	}
}

// Driver class
class MinSwaps
{
	// Driver program to test the above function
	public static void main(String[] args)
	{
		int []a = {1, 5, 4, 3, 2};
		GfG g = new GfG();
		System.out.println(g.minSwaps(a));
	}
}
// This code is contributed by Saurabh Johari