선택 정렬 (Selection Sort)

배열의 모든 요소를 하나씩 확인하면서, 현재 위치에 와야 할 가장 작은(혹은 가장 큰) 요소를 찾아 그 위치에 배치하는 방식입니다.

1. 동작 방식

선택 정렬은 다음과 같은 단계를 반복하여 정렬을 수행합니다.

1. 최소값(또는 최대값) 찾기: 배열의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 찾습니다.
2. 위치 교환: 찾아낸 최소값(또는 최대값)을 정렬되지 않은 부분의 첫 번째 요소와 교환합니다.
3. 반복: 위 과정을 정렬되지 않은 다음 부분을 대상으로 반복합니다. 배열 전체가 정렬될 때까지 이 과정을 계속합니다.

2. 예제

선택 정렬 이용 오름차순으로 정렬하는 과정 설명 초기 배열: [64, 25, 12, 22, 11]

1단계: 첫 번째 요소(인덱스 0) 위치 결정

• 정렬되지 않은 부분: [64, 25, 12, 22, 11]
• 이 중에서 가장 작은 값은 11입니다.
• 11을 현재 위치(인덱스 0)의 64와 교환합니다.
• 결과: [11, 25, 12, 22, 64] (11은 정렬 완료)

2단계: 두 번째 요소(인덱스 1) 위치 결정

• 정렬되지 않은 부분: [25, 12, 22, 64] (11은 이미 정렬됨)
• 이 중에서 가장 작은 값은 12입니다.
• 12를 현재 위치(인덱스 1)의 25와 교환합니다.
• 결과: [11, 12, 25, 22, 64] (11, 12는 정렬 완료)

3단계: 세 번째 요소(인덱스 2) 위치 결정

• 정렬되지 않은 부분: [25, 22, 64] (11, 12는 이미 정렬됨)
• 이 중에서 가장 작은 값은 22입니다.
• 22를 현재 위치(인덱스 2)의 25와 교환합니다.
• 결과: [11, 12, 22, 25, 64] (11, 12, 22는 정렬 완료)

4단계: 네 번째 요소(인덱스 3) 위치 결정

• 정렬되지 않은 부분: [25, 64] (11, 12, 22는 이미 정렬됨)
• 이 중에서 가장 작은 값은 25입니다.
• 25를 현재 위치(인덱스 3)의 25와 교환합니다. (자기 자신과 교환)
• 결과: [11, 12, 22, 25, 64] (11, 12, 22, 25는 정렬 완료)

마지막 요소는 자동으로 정렬되므로 더 이상 비교할 필요가 없습니다.

최종 정렬된 배열: [11, 12, 22, 25, 64]

3. Java 코드 예시

코드 설명:

• selectionSort(int[] arr): 선택 정렬을 수행하는 메인 함수입니다.
• 바깥쪽 for 루프 (for (int i = 0; i < n - 1; i++)): 배열의 i번째 인덱스에 올바른 값을 채워 넣는 과정을 n-1번 반복합니다. 마지막 요소는 자동으로 정렬되므로 n-1까지 반복합니다.
• 안쪽 for 루프 (for (int j = i + 1; j < n; j++)): i번째 인덱스 이후의 모든 요소들을 탐색하여 가장 작은 값(minIndex)의 인덱스를 찾습니다.
• if (minIndex != i): 만약 찾은 가장 작은 값이 현재 위치(i)의 값과 다르다면, 두 값을 교환(swap)합니다. 이렇게 함으로써 불필요한 교환을 줄일 수 있습니다.

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 배열의 모든 요소를 순회하면서 정렬
        for (int i = 0; i < n - 1; i++) {
            // 현재 정렬되지 않은 부분에서 가장 작은 값의 인덱스를 찾음
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 가장 작은 값을 찾았으면 현재 위치(i)와 교환
            // 단, minIndex가 i와 다를 경우에만 교환 (효율성)
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    // 배열을 출력하는 헬퍼 함수
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("정렬 전 배열:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("정렬 후 배열:");
        printArray(arr);

        int[] arr2 = {5, 1, 4, 2, 8};
        System.out.println("\\n정렬 전 배열 (두 번째 예시):");
        printArray(arr2);

        selectionSort(arr2);

        System.out.println("정렬 후 배열 (두 번째 예시):");
        printArray(arr2);
    }
}

4. 시간 복잡도 (Time Complexity)

선택 정렬의 시간 복잡도는 입력 데이터의 초기 상태와 관계없이 항상 동일합니다.

• 최선 (Best Case): O(N2)
• 평균 (Average Case): O(N2)
• 최악 (Worst Case): O(N2)

설명: 선택 정렬은 이중 루프를 사용합니다.

• 바깥쪽 루프는 n-1번 반복합니다.
• 안쪽 루프는 바깥쪽 루프의 i 값에 따라 n-1번, n-2번, ..., 1번 반복합니다.
• 총 비교 횟수는 (N−1)+(N−2)+...+1=N(N−1)/2 이 됩니다.
• 이는 대략 $O(N^2)$에 해당합니다.
• 교환 횟수는 최대 N-1번 발생합니다.
• 따라서 비교 횟수가 지배적이므로 시간 복잡도는 $O(N^2)$입니다.

5. 공간 복잡도 (Space Complexity)

• O(1) (In-place sort)

설명: 선택 정렬은 정렬을 위해 추가적인 저장 공간을 거의 사용하지 않습니다. 배열 내에서 요소들의 위치만 바꾸는 방식(In-place)으로 정렬이 이루어집니다. temp 변수 하나만 사용하므로 상수 공간 복잡도를 가집니다.

6. 선택 정렬의 사용 예제 및 장단점

장점:

• 구현이 매우 간단합니다.
• 추가적인 메모리 공간이 거의 필요 없습니다 (O(1)).
• 데이터의 이동(교환) 횟수가 다른 O(N2) 정렬 알고리즘(예: 버블 정렬, 삽입 정렬)에 비해 적습니다. 이는 데이터 이동 비용이 큰 경우 (예: 큰 레코드 정렬)에 유리할 수 있습니다. 각 패스마다 최대 1번의 스왑만 발생합니다.

단점:

• 시간 복잡도가 O(N2) 이므로 데이터의 양이 많아질수록 성능이 급격히 저하됩니다. 따라서 대규모 데이터셋에는 적합하지 않습니다.
• 데이터가 거의 정렬되어 있는 경우에도 모든 요소를 비교해야 하므로 성능 향상이 없습니다. (버블 정렬이나 삽입 정렬은 어느 정도 정렬된 데이터에 대해 더 빠를 수 있습니다.)
• 불안정 정렬(Unstable Sort)입니다. 동일한 값을 가진 요소들의 상대적인 순서가 정렬 후에도 유지되지 않을 수 있습니다.

사용 예제: 선택 정렬은 위에서 언급한 장점 때문에 다음과 같은 경우에 사용을 고려해 볼 수 있습니다.

1. 데이터셋의 크기가 매우 작은 경우: 예를 들어, 요소의 개수가 수십 개 이내일 때는 $O(N^2)$의 성능 저하가 크게 체감되지 않으며, 구현의 단순성이 더 중요할 수 있습니다.
2. 메모리 제약이 심한 환경: 추가적인 메모리 할당이 어려운 임베디드 시스템 등에서는 O(1) 공간 복잡도가 큰 장점이 될 수 있습니다.
3. 데이터 이동(swap) 횟수를 최소화해야 하는 경우: 데이터 하나의 크기가 매우 커서 교환하는 비용이 큰 경우 (예: 하드 디스크에 저장된 대용량 레코드 정렬)에는 선택 정렬이 다른 O(N2) 정렬 알고리즘보다 유리할 수 있습니다. (물론 이런 경우엔 더 효율적인 O(NlogN) 정렬 알고리즘을 사용합니다.)