선택 정렬(Selection Sort) 이란?

 

 

 

 

 

 

 

 

 

 

선택 정렬(Selection Sort)은 주어진 리스트에서 가장 작은 요소를 찾아서 정렬된 부분에 배치하는 방식입니다. 이 알고리즘은 간단하고 직관적이지만, 성능 면에서는 비효율적일 수 있습니다. 

 

---

 

선택 정렬의 동작 원리

선택 정렬은 아래와 같은 방식으로 작동합니다:

1. 주어진 리스트에서 가장 작은 원소를 찾습니다.
2. 그 원소를 리스트의 첫 번째 원소와 교환합니다.
3. 첫 번째 원소를 제외한 나머지 부분에 대해 동일한 과정을 반복합니다.
4. 이 과정을 리스트의 끝까지 반복하여 정렬된 리스트를 만듭니다.

 

선택 정렬의 단계별 설명

예시로 숫자 배열 [64, 25, 12, 22, 11]을 선택 정렬로 정렬하는 과정을 살펴보겠습니다.

1단계:

• 리스트에서 가장 작은 숫자를 찾습니다. (11)
• 11을 첫 번째 원소인 64와 교환합니다.
• 결과: [11, 25, 12, 22, 64]

2단계:

• 나머지 리스트에서 가장 작은 숫자를 찾습니다. (12)
• 12를 두 번째 원소인 25와 교환합니다.
• 결과: [11, 12, 25, 22, 64]

3단계:

• 나머지 리스트에서 가장 작은 숫자를 찾습니다. (22)
• 22를 세 번째 원소인 25와 교환합니다.
• 결과: [11, 12, 22, 25, 64]

4단계:

• 나머지 리스트에서 가장 작은 숫자를 찾습니다. (25)
• 이미 25는 세 번째 위치에 있으므로 변경할 필요가 없습니다.
• 결과: [11, 12, 22, 25, 64]

5단계:

• 마지막 숫자는 이미 정렬된 상태이므로 교환할 필요가 없습니다.
• 결과: [11, 12, 22, 25, 64]

이 과정에서 리스트는 점진적으로 정렬됩니다.

 

선택 정렬의 시간 복잡도

선택 정렬은 매 단계마다 나머지 요소들 중에서 최소값을 찾는 방식이므로 시간 복잡도를 계산할 때 고려해야 할 중요한 부분은 최소값을 찾는 과정입니다.

• 첫 번째 단계에서는 n개의 요소를 비교하여 최소값을 찾습니다.
• 두 번째 단계에서는 n-1개의 요소를 비교하여 최소값을 찾습니다.
• 세 번째 단계에서는 n-2개의 요소를 비교하여 최소값을 찾습니다.
• 이와 같은 방식으로 최종 단계에서는 2개의 요소를 비교하게 됩니다.

따라서 선택 정렬의 전체 비교 횟수는 다음과 같이 구할 수 있습니다:

n+(n−1)+(n−2)+...+2+1=n(n−1)2n + (n-1) + (n-2) + ... + 2 + 1 = \frac{n(n-1)}{2}n+(n−1)+(n−2)+...+2+1=2n(n−1)​

이 값은 O(n²)로, 선택 정렬의 시간 복잡도는 **O(n²)**입니다. 즉, 리스트의 길이가 길어질수록 성능이 급격히 떨어집니다.

 

 

선택 정렬의 장단점

장점:

• 구현이 매우 간단하고 직관적입니다.
• 추가적인 메모리 공간을 사용하지 않으며, 제자리 정렬(in-place sorting) 방식이므로 공간 복잡도가 O(1)입니다.

단점:

• 시간 복잡도가 O(n²)로 비효율적입니다. 따라서 큰 데이터셋에 대해 사용하기에는 부적합합니다.
• 최선의 경우(이미 정렬된 경우)에도 O(n²)의 시간 복잡도를 보입니다.

 

선택 정렬을 사용할 수 있는 경우

선택 정렬은 작은 데이터셋에 대해서는 괜찮은 성능을 발휘할 수 있습니다. 또한 알고리즘이 간단하고 메모리 사용이 적기 때문에, 메모리 제약이 있는 환경에서 사용될 수 있습니다. 하지만 데이터셋이 커지면 다른 정렬 알고리즘들(예: 병합 정렬, 퀵 정렬)에 비해 비효율적이기 때문에 큰 데이터를 다룰 때는 선택하지 않는 것이 좋습니다.

 

자바로 구현한 선택 정렬 예시

 

public class SelectionSort {

    // 선택 정렬 메서드
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 배열의 각 위치에 대해 반복
        for (int i = 0; i < n - 1; i++) {
            // 가장 작은 값의 인덱스를 찾기 위한 변수
            int minIndex = i;
            
            // i 이후의 요소들 중에서 가장 작은 값을 찾는다.
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 가장 작은 값과 현재 위치의 값을 교환
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = 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);
    }
}

코드 설명

1. selectionSort 메서드:
   • 배열을 받아서 선택 정렬을 수행합니다.
   • 첫 번째 for 루프는 배열의 각 원소에 대해 정렬을 수행합니다.
   • 두 번째 for 루프는 각 위치에 대해 가장 작은 값을 찾습니다.
   • minIndex에 가장 작은 값의 인덱스를 기록하고, i 위치와 minIndex 위치의 값을 교환합니다.
2. printArray 메서드:
   • 배열을 출력하는 간단한 메서드입니다.
3. main 메서드:
   • 예시 배열을 생성하고, 선택 정렬을 수행한 후 정렬된 배열을 출력합니다.

출력 예시

 

원본 배열:
64 25 12 22 11 
정렬된 배열:
11 12 22 25 64

시간 복잡도 분석

• 선택 정렬의 시간 복잡도는 O(n²)입니다. 배열의 각 원소에 대해 나머지 원소들을 비교하는 방식으로 동작하기 때문에, 최악의 경우에도 O(n²)입니다.
• 이 자바 코드는 작은 배열에 대해서는 성능이 괜찮지만, 배열 크기가 커질수록 성능이 저하됩니다.

 

 

 

선택 정렬은 직관적이고 간단한 알고리즘이지만, 성능 면에서는 최악의 경우 O(n²)의 시간 복잡도를 가지므로 큰 데이터셋에 적합하지 않습니다. 그럼에도 불구하고 특정 조건에서 유용하게 사용할 수 있는 정렬 알고리즘입니다.