[ Algorithm ] Selection Sort(선택 정렬)

선택 정렬(Selection Sort)

선택 정렬은 간단한 정렬 알고리즘 중 하나이다

• 목록을 총 N-1번 훑으면서 다음 과정을 반복한다
  • 첫 번째 요소 0부터 훑으면서 최솟값을 찾아 요소 0과 교환
  • 두 번째는 요소 1부터 훑으면서 최솟값을 찾아 요소 1과 교환
  • 세 번째는 요소 2부터 훑으면서 최솟값을 찾아 요소 2와 교환
  • N-1번째까지 반복
• 최솟값을 찾아 선택한다고 해서 ‘선택 정렬’이라고 부른다.

선택 정렬은 정수 컬렉션에서 반복적으로 최소 요소를 찾아 목록의 앞쪽으로 이동시켜 정렬된 리스트를 만든다. 전체 리스트가 정렬될 때까지 요소를 적절히 교환한다.

특징

• 직관적이고 구현이 간단하다.
• 시간 복잡도: 최악의 경우 O(n^2)
• 공간 복잡도: O(1) (추가 공간 사용 없음, 제자리 정렬)
• 안정적이지 않은(not stable) 정렬 알고리즘이다.

Java 구현

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;
        }
    }
}

예제 문제: Sort Colors

주어진 문제는 빨강, 흰색, 파랑으로 색칠된 n개의 객체가 있는 배열 nums를 정렬하는 것이다. 같은 색의 객체들이 인접하도록 제자리(in-place) 정렬해야 하며, 색상 순서는 빨강, 흰색, 파랑 순이어야 한다.

• 0, 1, 2는 각각 빨강, 흰색, 파랑을 나타낸다.
• 라이브러리의 정렬 함수를 사용하지 않고 해결해야 한다.

해결책

class Solution {
    public void sortColors(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[minIndex] >= nums[j]) {
                    minIndex = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }
}

이 해결책은 선택 정렬을 사용하여 문제를 해결한다. 각 반복에서 현재 위치 이후의 가장 작은 값을 찾아 현재 위치와 교환한다. 이 과정을 배열의 모든 요소에 대해 반복하여 전체 배열을 정렬한다.

선택 정렬은 이 문제에 대해 올바른 해결책을 제공하지만, 대규모 데이터셋에 대해서는 효율적이지 않을 수 있다. 이 특정 문제의 경우, 값이 0, 1, 2로 제한되어 있으므로 계수 정렬(counting sort)과 같은 더 효율적인 알고리즘을 사용할 수 있다.