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.

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