# 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
```

This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.

``` Graph for {4, 3, 2, 1}
```

The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly a cycle with 3 nodes will only require 2 swap to do so.

``` Graph for {4, 5, 2, 1, 5}
```

Hence,

• ans = Σi = 1k(cycle_size – 1)
• where k is the number of cycles

Below is the implementation of the idea.

div class="responsive-tabs">

## C++

 `// C++ program to find  minimum number of swaps ` `// required to sort an array ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Function returns the minimum number of swaps ` `// required to sort the array ` `int` `minSwaps(``int` `arr[], ``int` `n) ` `{ ` `    ``// Create an array of pairs where first ` `    ``// element is array element and second element ` `    ``// is position of first element ` `    ``pair<``int``, ``int``> arrPos[n]; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``{ ` `        ``arrPos[i].first = arr[i]; ` `        ``arrPos[i].second = i; ` `    ``} ` ` `  `    ``// Sort the array by array element values to ` `    ``// get right position of every element as second ` `    ``// element of pair. ` `    ``sort(arrPos, arrPos + n); ` ` `  `    ``// To keep track of visited elements. Initialize ` `    ``// all elements as not visited or false. ` `    ``vector<``bool``> vis(n, ``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[i].second == 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] = 1; ` ` `  `            ``// move to next node ` `            ``j = arrPos[j].second; ` `            ``cycle_size++; ` `        ``} ` ` `  `        ``// Update answer by adding current cycle.  ` `        ``if` `(cycle_size > 0) ` `        ``{ ` `            ``ans += (cycle_size - 1); ` `        ``} ` `    ``} ` ` `  `    ``// Return result ` `    ``return` `ans; ` `} ` ` `  `// Driver program to test the above function ` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 5, 4, 3, 2}; ` `    ``int` `n = (``sizeof``(arr) / ``sizeof``(``int``)); ` `    ``cout << minSwaps(arr, n); ` `    ``return` `0; ` `} `

## Java

 `// 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 > arrpos = ` `                  ``new` `ArrayList > (); ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `             ``arrpos.add(``new` `Pair (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>() ` `        ``{ ` `            ``@Override` `            ``public` `int` `compare(Pair o1, ` `                               ``Pair 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)); ` `    ``} ` `} ` `// This code is contributed by Saksham Seth `

[/sourcecode]

## Python3

 `# Python3 program to find  minimum number  ` `# of swaps required to sort an array ` ` `  `# Function returns the minimum  ` `# number of swaps required to sort the array ` `def` `minSwaps(arr): ` `    ``n ``=` `len``(arr) ` `     `  `    ``# Create two arrays and use  ` `    ``# as pairs where first array  ` `    ``# is element and second array ` `    ``# is position of first element ` `    ``arrpos ``=` `[``*``enumerate``(arr)] ` `     `  `    ``# Sort the array by array element  ` `    ``# values to get right position of  ` `    ``# every element as the elements  ` `    ``# of second array. ` `    ``arrpos.sort(key ``=` `lambda` `it:it[``1``]) ` `     `  `    ``# To keep track of visited elements.  ` `    ``# Initialize all elements as not  ` `    ``# visited or false. ` `    ``vis ``=` `{k:``False` `for` `k ``in` `range``(n)} ` `     `  `    ``# Initialize result ` `    ``ans ``=` `0` `    ``for` `i ``in` `range``(n): ` `         `  `        ``# alreadt swapped or  ` `        ``# alreadt present at  ` `        ``# correct position ` `        ``if` `vis[i] ``or` `arrpos[i][``0``] ``=``=` `i: ` `            ``continue` `             `  `        ``# find number of nodes  ` `        ``# in this cycle and ` `        ``# add it to ans ` `        ``cycle_size ``=` `0` `        ``j ``=` `i ` `        ``while` `not` `vis[j]: ` `             `  `            ``# mark node as visited ` `            ``vis[j] ``=` `True` `             `  `            ``# move to next node ` `            ``j ``=` `arrpos[j][``0``] ` `            ``cycle_size ``+``=` `1` `             `  `        ``# update answer by adding ` `        ``# current cycle ` `        ``if` `cycle_size > ``0``: ` `            ``ans ``+``=` `(cycle_size ``-` `1``) ` `    ``# return answer ` `    ``return` `ans ` ` `  `# Driver Code      ` `arr ``=` `[``1``, ``5``, ``4``, ``3``, ``2``] ` `print``(minSwaps(arr)) ` ` `  `# This code is contributed ` `# by Dharan Aditya `

Output:

```2
```

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

Related Article :
Number of swaps to sort when only adjacent swapping allowed

## tags:

Arrays Graph Sorting Arrays Sorting Graph