> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/minimum-number-of-swaps-required-to-sort-an-array.md).

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

![](/files/-MAMLO4rmyIfynNB1ltD)

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;
    }
}
```