[Array] HackerRank Algorithms in Java ‘Minimum Swaps 2’ solution

Problem

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order. For example, given the array arr = [7,1,3,2,4,5,6] we perform the following steps:

i	arr	swap (indices)
0	[7, 1, 3, 2, 4, 5, 6]	swap (0,3)
1	[2, 1, 3, 7, 4, 5, 6]	swap (0,1)
2	[1, 2, 3, 7, 4, 5, 6]	swap (3,4)
3	[1, 2, 3, 4, 7, 5, 6]	swap (4,5)
4	[1, 2, 3, 4, 5, 7, 6]	swap (5,6)
5	[1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

Solution

가장 적게 스왑을 하는 알고리즘으로 선택 정렬을 선택하였다.

• 주어진 입력값이 1부터 시작하며 오름차순으로 정렬하기 때문에 배열의 인덱스 값과 배열의 값을 비교하며 정렬한다. arr[i] != i + 1
• 정렬이 필요한 경우 원래 해당 위치에 와야 하는 숫자를 찾아 바꿔준다.
• 바꾼 횟수를 세고 출력한다.

Code

    // Complete the minimumSwaps function below.
    static int minimumSwaps(int[] arr) {
        int swapCnt = 0, tmp, idx = 0;
        
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] != i + 1) {
                for(int j = i + 1; j < arr.length; j++) {
                    if(arr[j] == i + 1) {
                        idx = j; break;
                    }
                }
                tmp = arr[i];
                arr[i] = arr[idx];
                arr[idx] = tmp;
                swapCnt++;
            }
        }
        return swapCnt;
    }