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

![](https://1817027152-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M97UlEWvq7aSC1s7hjT%2F-MAMHDHAw1sQeuATczvv%2F-MAMLO4rmyIfynNB1ltD%2Fimage.png?alt=media\&token=35082fe2-ace4-4792-9742-f0c5728b1a0f)

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.

```java
class Solution {
    static class Pair {
        int v, i;

        Pair(int v, int i) {
            this.v = v;
            this.i = i;
        }
    }

    public int minSwaps(int[] arr, int N) {
        Pair[] copy = new Pair[N];
        for (int i = 0; i < N; i++)
            copy[i] = new Pair(arr[i], i);
        Arrays.sort(copy, (a, b) -> a.v - b.v);
        int count = 0;
        boolean[] visited = new boolean[N];
        // number of swaps = cycle length - 1
        for (int i = 0; i < N; i++) {
            // If element is at correct position
            if (copy[i].i == i || visited[i])
                continue;
            else {
                // Cycle
                int size = 0;
                int index = i;
                while (!visited[index]) {
                    visited[index] = true;
                    index = copy[index].i;
                    size++;
                }
                count += size - 1;
            }
        }
        return count;
    }
}
```
