Minimum number of swaps required to sort an array

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)