Arrays: Given an array, find minimum number of swaps required to sort the array

Problem Statement:

You are given an array.

You need to find the minimum number of swaps required to sort the array.

Example:

Input: arr[] = { 7, 1, 3, 2, 4, 5, 6 }
Output: 5

Case 0   [7, 1, 3, 2, 4, 5, 6]   swap (0, 3)
Case 1   [2, 1, 3, 7, 4, 5, 6]   swap (0, 1)
Case 2   [1, 2, 3, 7, 4, 5, 6]   swap (3, 4)
Case 3   [1, 2, 3, 4, 7, 5, 6]   swap (4, 5)
Case 4   [1, 2, 3, 4, 5, 7, 6]   swap (5, 6)
Case 5   [1, 2, 3, 4, 5, 6, 7]

Solution Explanation:

Solution is very simple.

For each index in the array, do following:

1. Check if the current element is not in the correct position or not.

2. If the element is not in its correct position, swap the element with the element which has occupied its place.

3. else check for next index.

Time Complexity: O(N)
Space Complexity: O(1)

Code Solution

#include <iostream>
using namespace std;

int solution(int arr[],int n)
{
	int count = 0;
	int i = 0;
	
	while (i < n) 
	{

		if (arr[i] != i + 1)
		{

			while (arr[i] != i + 1) 
			{
				int temp = 0;
                
                // swap the elements
                // to its correct position
				temp = arr[arr[i] - 1];
				arr[arr[i] - 1] = arr[i];
				arr[i] = temp;
				count++;
			}
		}

		i++;
	}
	return count;
}

int main() 
{
	int arr[] = {7, 1, 3, 2, 4, 5, 6 };

	int n = sizeof(arr)/sizeof(arr[0]);
	
	cout << solution(arr,n) ;
}

Output

5