정렬 알고리즘 (3): 선택 정렬 (Selection Sort)

1. 선택 정렬이란?

선택 정렬(Selection Sort)은 정렬되지 않은 부분에서 가장 작은 요소를 찾아 정렬된 부분의 끝과 교환하는 방식으로 동작하는 비교 기반 정렬 알고리즘이다. 구현이 간단하지만, 수행 속도가 느려 큰 데이터셋에서는 비효율적이다.

2. 선택 정렬의 동작 원리

선택 정렬은 배열을 순차적으로 탐색하며, 각 단계에서 가장 작은 요소를 찾아 적절한 위치에 배치하는 방식으로 정렬을 수행한다.

2.1 정렬 과정

1. 배열에서 최소값을 찾는다.
2. 최소값을 배열의 첫 번째 요소와 교환한다.
3. 정렬된 부분을 제외하고, 나머지 배열에서 위 과정을 반복한다.
4. 배열 전체가 정렬될 때까지 위 과정을 반복한다.

2.2 예제 코드 (Java)

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;
                }
            }
            
            // 최소값을 현재 위치와 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    // 선택 정렬 실행 및 결과 출력
    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("정렬 전: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
        
        selectionSort(data);
        
        System.out.println("\n정렬 후: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

3. 선택 정렬의 성능 분석

선택 정렬의 시간 및 공간 복잡도를 분석하면 다음과 같다.

3.1 시간 복잡도

• 최선의 경우 (Best Case): O(n²)
• 평균의 경우 (Average Case): O(n²)
• 최악의 경우 (Worst Case): O(n²)

선택 정렬은 입력 데이터의 정렬 여부와 관계없이 항상 O(n²)의 비교 연산이 필요하다.

3.2 공간 복잡도

• 공간 복잡도: O(1) → 추가적인 메모리 사용 없이 배열 내에서 정렬이 이루어짐 (In-place 알고리즘)

4. 선택 정렬의 장점과 단점

4.1 장점

• 구현이 간단하고 직관적이다.
• 추가적인 메모리 공간이 필요하지 않다.
• 데이터 이동 횟수가 적어 쓰기 연산이 적은 환경에서 유리하다.

4.2 단점

• O(n²)의 시간 복잡도를 가지므로 대규모 데이터에는 부적합하다.
• 다른 정렬 알고리즘(퀵 정렬, 병합 정렬)과 비교하면 성능이 떨어진다.

5. 선택 정렬의 활용 및 개선 방법

5.1 활용 사례

• 데이터 크기가 작을 때 단순한 정렬이 필요할 경우
• 쓰기 연산 비용이 높은 환경 (예: 플래시 메모리)

5.2 개선 방법

• 이진 선택 정렬(Binary Selection Sort): 최소값과 최대값을 동시에 선택하여 교환하여 연산 횟수를 줄임.
• 힙 정렬(Heap Sort): 선택 정렬의 개념을 개선하여 힙을 활용하여 정렬 속도를 향상.

6. 결론

선택 정렬은 개념이 간단하고 메모리 사용량이 적은 정렬 알고리즘이지만, O(n²)의 시간 복잡도로 인해 대규모 데이터에는 적합하지 않다. 그러나 정렬 횟수가 제한된 환경이나 작은 데이터셋에서는 활용될 수 있으며, 보다 효율적인 정렬 알고리즘(퀵 정렬, 병합 정렬)과 함께 학습하면 좋다.