Minimum number of swaps required to sort an array

Software Development
#1

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

Examples:

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

Below is the implementation of the idea.

// Java program to find

// minimum number of swaps

// required to sort an array

import javafx.util.Pair;

import java.util.ArrayList;

import java.util.*;

class GfG

{

// Function returns the

// minimum number of swaps

// required to sort the array

public static int minSwaps( int [] arr)

{

int n = arr.length;

// Create two arrays and

// use as pairs where first

// array is element and second array

// is position of first element

ArrayList <Pair <Integer, Integer> > arrpos =

new ArrayList <Pair <Integer,

Integer> > ();

for ( int i = 0 ; i < n; i++)

arrpos.add( new Pair <Integer,

Integer> (arr[i], i));

// Sort the array by array element values to

// get right position of every element as the

// elements of second array.

arrpos.sort( new Comparator<Pair<Integer,

Integer>>()

{

@Override

public int compare(Pair<Integer, Integer> o1,

Pair<Integer, Integer> o2)

{

if (o1.getKey() > o2.getKey())

return - 1 ;

// We can change this to make

// it then look at the

// words alphabetical order

else if (o1.getKey().equals(o2.getKey()))

return 0 ;

else

return 1 ;

}

});

// To keep track of visited elements. Initialize

// all elements as not visited or false.

Boolean[] vis = new Boolean[n];

Arrays.fill(vis, false );

// Initialize result

int ans = 0 ;

// Traverse array elements

for ( int i = 0 ; i < n; i++)

{

// already swapped and corrected or

// already present at correct pos

if (vis[i] || arrpos.get(i).getValue() == i)

continue ;

// find out the number of node in

// this cycle and add in ans

int cycle_size = 0 ;

int j = i;

while (!vis[j])

{

vis[j] = true ;

// move to next node

j = arrpos.get(j).getValue();

cycle_size++;

}

// Update answer by adding current cycle.

if (cycle_size > 0 )

{

ans += (cycle_size - 1 );

}

}

// Return result

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));

}

}

Output:

2

Time Complexity: O(n Log n)
Auxiliary Space: O(n)