[Algorithm] 선택정렬(Selection Sort)

설명

• 가장 작은 것을 선택해서 가장 앞으로 보내는 방식
• 시간 복잡도 : O(N^2)
• 참고
  • https://youtu.be/8ZiSzteFRYc

예시

1. 초기값

• 1 10 5 8 7

2. 맨 앞을 기준값(i)으로 지정하고, 기준값부터 시작해서 제일 작은 값(m)을 탐색

• 1(i)(m) 10 5 8 7

3. i와 m 위치 변경

• 1 10 5 8 7

4. i를 다음 위치로 이동하고 2 과정 동일하게 진행

• 1 10(i) 5(m) 8 7

5. i와 m 위치 변경

• 1 5(i) 10(m) 8 7

6. 위 과정 반복

코드

public class Solution {
    public static int[] sort(int[] data) {
        for (int i = 0; i < data.length; i++) {
            int minValue = Integer.MAX_VALUE;
            int minIndex = -1;

            // 제일 작은 값 탐색
            for (int j = i; j < data.length; j++) {
                if (minValue > data[j]) {
                    minValue = data[j];
                    minIndex = j;
                }
            }

            // 기준 값과 작은 값 위치 변경
            int temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }

        return data;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#data -> #result"() {
        expect:
        Solution.sort(data as int[]) == result

        where:
        data                            | result
        [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}