선택 정렬(Selection Sort) 완벽 분석: 코딩 테스트부터 실무 활용까지!

728x90

1. 선택 정렬(Selection Sort)이란? 용어와 주요 개념

코딩 테스트 단골 손님, 선택 정렬! 하지만 "단순하다"는 말에 속아 제대로 공부하지 않으면 큰 코 다칠 수 있습니다.

선택 정렬은 비교 기반 정렬 알고리즘으로, 배열에서 가장 작은(또는 큰) 값을 찾아 정렬된 위치에 배치하는 과정을 반복합니다. 이름에서 알 수 있듯, 매번 "선택"하여 정렬을 진행하는 방식입니다.

배열에서 가장 작은 (혹은 큰) 요소를 선택하여 알맞은 위치로 옮기는 과정을 반복합니다. 마치 도서관에서 책을 키 순서대로 정리하는 것과 비슷하다고 보면 됩니다.

주요 개념

비교 기반: 두 요소를 비교하여 순서를 결정.
제자리 정렬(In-place Sorting): 추가 메모리 공간을 거의 사용하지 않음(공간 복잡도 O(1)).
불안정 정렬(Unstable Sorting): 동일한 값의 상대적 순서가 보장되지 않음.
시간 복잡도: O(n²)로, 입력 크기 n에 대해 비효율적일 수 있음.

특징

구현 용이 & 단순함 : 코드가 직관적이고 이해하기 쉬워 초보자도 쉽게 구현할 수 있습니다.
제자리 정렬(In-place Sort): 추가적인 메모리 공간을 거의 사용하지 않습니다. (O(1)의 공간 복잡도)
불안정 정렬(Unstable Sort): 동일한 값을 가진 요소들의 상대적인 순서가 바뀔 수 있습니다.
시간 복잡도 & 비교 횟수 고정 : 최선, 평균, 최악의 경우 모두 O(n^2)로, 데이터 크기가 커질수록 성능이 저하됩니다.
스왑 최소화: 각 반복마다 한 번만 스왑(swap) 발생합니다.

2. 선택 정렬 예시와 설명

예시: 배열 [64, 34, 25, 12, 22] 정렬

선택 정렬은 배열에서 최소값을 찾아 맨 앞부터 채워나갑니다. 단계별로 살펴보겠습니다.

단계별 진행

첫 번째 반복: [64, 34, 25, 12, 22] → 최소값 12를 찾아 64와 스왑 → [12, 34, 25, 64, 22]
두 번째 반복: [12, 34, 25, 64, 22] → 최소값 22를 찾아 34와 스왑 → [12, 22, 25, 64, 34]
세 번째 반복: [12, 22, 25, 64, 34] → 최소값 25는 이미 위치에 있음 → [12, 22, 25, 64, 34]
네 번째 반복: [12, 22, 25, 64, 34] → 최소값 34를 찾아 64와 스왑 → [12, 22, 25, 34, 64]

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i; // 최소값 인덱스 초기화
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j; // 더 작은 값 발견 시 인덱스 갱신
                }
            }
            // 스왑
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22};
        selectionSort(arr);
        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

외부 루프(i): 정렬되지 않은 부분의 시작점.
내부 루프(j): 최소값을 찾기 위해 나머지 요소를 탐색.
스왑: 최소값을 현재 위치(i)로 이동.

3. 선택 정렬 관련 질문 & 풀이

질문 1: "K번째로 작은 수 찾기"

문제: 배열에서 K번째로 작은 수를 선택 정렬로 찾아라.
입력: [5, Ascending=True, K=3
출력: 3

풀이

선택 정렬을 활용해 배열을 정렬하고 K번째 값을 반환합니다.

public class KthSmallest {
    public static int findKthSmallest(int[] arr, int k) {
        int n = arr.length;
        for (int i = 0; i < k; i++) { // k번만 반복
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // 스왑
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
        return arr[k - 1]; // k번째 값 반환 (0-based index)
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};
        int k = 3;
        int result = findKthSmallest(arr, k);
        System.out.println("K번째 작은 수: " + result); // 출력: 5
    }
}

선택 정렬을 k번만 수행하면 K번째 작은 값을 찾을 수 있음.
시간 복잡도: O(n * k), 전체 정렬(O(n²))보다 효율적.

질문 2: "중복 요소 제거 후 정렬"

문제: 중복된 요소를 제거하고 오름차순으로 정렬하라.
입력: [4, 2, 4, 1, 3, 2]
출력: [1, 2, 3, 4]

풀이

HashSet으로 중복을 제거한 뒤, 선택 정렬로 정렬합니다.

import java.util.*;

public class RemoveDuplicatesAndSort {
    public static int[] removeDuplicatesAndSort(int[] arr) {
        // HashSet으로 중복 제거
        Set<Integer> set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }
        
        // 배열로 변환
        int[] uniqueArr = new int[set.size()];
        int index = 0;
        for (int num : set) {
            uniqueArr[index++] ==num;
        }
        
        // 선택 정렬
        selectionSort(uniqueArr);
        return uniqueArr;
    }

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

    public static void main(String[] args) {
        int[] arr = {4, 2, 4, 1, 3, 2};
        int[] result = removeDuplicatesAndSort(arr);
        System.out.println("결과: " + Arrays.toString(result)); // 출력: [1, 2, 3, 4]
    }
}

HashSet으로 O(n) 시간에 중복 제거.
선택 정렬로 O(n²) 시간에 정렬.
최종 시간 복잡도: O(n²).

질문 3: 선택 정렬의 시간 복잡도는 얼마인가요? 왜 그런 시간 복잡도를 가지나요?

답변: 선택 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 **O(n^2)**입니다. 그 이유는 다음과 같습니다.

최솟값 찾기: 배열에서 최솟값을 찾기 위해 n번의 비교 연산이 필요합니다.
교환: 최솟값을 찾은 후 교환 연산은 상수 시간 O(1)이 걸립니다.
반복: 위 과정을 n-1번 반복해야 합니다.

따라서 전체 시간 복잡도는 O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n^2)이 됩니다.

4. 실무 코딩에서 선택 정렬 적용 예시

선택 정렬은 실무에서 자주 사용되지는 않지만, 소규모 데이터 정렬이나 교육 목적으로 유용합니다. 예를 들어, Spring Framework 기반의 웹 애플리케이션에서 소규모 리스트를 정렬할 때 적용할 수 있습니다.

데이터 양이 매우 적을 때: 데이터 양이 작으면 O(n^2)의 시간 복잡도가 큰 문제가 되지 않습니다.
메모리 사용량이 제한적일 때: 추가적인 메모리 공간을 거의 사용하지 않으므로 메모리 제약이 있는 환경에서 유용합니다.

Spring Framework의 내부 구현에서 선택 정렬이 직접적으로 사용되는 경우는 드물지만, 비슷한 개념이 활용될 수 있습니다. 예를 들어, 특정 빈(Bean)들을 우선순위에 따라 정렬해야 하는 경우, 빈의 개수가 매우 적다면 선택 정렬과 유사한 방식으로 우선순위가 가장 높은 빈을 선택하여 처리하는 로직을 사용할 수 있습니다.

예시: 사용자 목록 정렬

Spring Boot에서 사용자 목록을 이름순으로 정렬하는 경우:

@Service
public class UserService {
    public List<User> getSortedUsers() {
        List<User> users = userRepository.findAll(); // DB에서 사용자 목록 조회
        int n = users.size();
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (users.get(j).getName().compareTo(users.get(minIdx).getName()) < 0) {
                    minIdx = j;
                }
            }
            Collections.swap(users, i, minIdx);
        }
        return users;
    }
}

소규모 데이터(예: 10~20명)라면 성능 저하 없이 사용 가능.
대규모 데이터라면 Collections.sort()(O(n log n)) 권장.

5. 선택 정렬의 주의사항

장점

구현 간단: 코드가 직관적이고 디버깅 쉬움.
제자리 정렬: 메모리 효율적.
스왑 최소화: 데이터 이동이 적음.

단점

시간 복잡도 높음: O(n²)로 대규모 데이터에 비효율적.
불안정 정렬: 동일 값의 순서가 유지되지 않음.
실무 제한: 대규모 데이터에서는 퀵 정렬, 병합 정렬 등이 더 적합.

6. 결론

선택 정렬은 모든 상황에서 최고의 선택은 아니지만, 학습용으로 최적이며, 단순함과 메모리 효율성이라는 강점을 가지고 있습니다. 코딩 테스트에서는 기본 개념을 묻는 문제에 자주 등장하며, 실제 개발에서는 데이터 양이 적거나 메모리 제약이 있는 경우에 활용될 수 있습니다. 따라서 선택 정렬의 특징을 정확히 이해하고, 상황에 맞게 적절히 사용하는 것이 중요합니다.