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

개요

선택 정렬(Selection Sort)은 정렬되지 않은 부분에서 가장 작은(또는 큰) 값을 선택해 맨 앞의 값과 교환하는 방식으로 정렬을 수행하는 알고리즘이다. 반복적으로 최솟값을 선택하고 정렬된 영역 뒤에 배치하면서 전체 배열을 정렬해나간다. 구현이 간단해 정렬 알고리즘 입문용으로 적합하며, 메모리 사용이 적은 것이 특징이다.

---

1. 개념 및 정의

선택 정렬은 다음과 같은 방식으로 동작한다:

• 전체 배열에서 가장 작은 값을 찾아 첫 번째 위치와 교환
• 두 번째부터 끝까지 반복하여 두 번째로 작은 값을 두 번째 위치로 이동
• 이런 식으로 n-1번 반복해 정렬 완료

---

2. 동작 원리

단계	설명
1단계	i번째 인덱스를 기준으로 최솟값을 찾음
2단계	최솟값과 i번째 값을 교환(swap)
3단계	i를 1 증가시키고 배열 끝까지 반복

배열이 커질수록 비교는 많아지지만, 교환은 n번 이하로 제한된다.

---

3. 파이썬 구현 예시

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 사용 예시
print(selection_sort([64, 25, 12, 22, 11]))

가장 작은 값을 찾고 한 번의 교환만으로 순서를 확정짓는다.

---

4. 시간 및 공간 복잡도

케이스	시간 복잡도
최선	O(n²)
평균	O(n²)
최악	O(n²)

• 공간 복잡도: O(1) (제자리 정렬)
• 교환 횟수: 최대 n번 (버블/삽입 정렬보다 적음)

---

5. 특징 및 장단점

항목	설명
구현 난이도	낮음 (간단한 구조)
안정 정렬 여부	X (동일 값의 순서 보장 X)
메모리 효율	O (in-place 정렬)
교환 효율	매우 높음 (최소화됨)
속도	느림 (n² 비교)

데이터 이동 비용이 높은 시스템에서는 선택 정렬이 유리할 수 있다.

---

6. 시각적 예시 (단계별 변화)

초기 배열: [64, 25, 12, 22, 11]

• 1회차: [11, 25, 12, 22, 64]
• 2회차: [11, 12, 25, 22, 64]
• 3회차: [11, 12, 22, 25, 64]
• 4회차: [11, 12, 22, 25, 64] → 완료

---

7. 다른 정렬 알고리즘과 비교

알고리즘	시간 복잡도	안정 정렬	특징
선택 정렬	O(n²)	X	비교는 많지만 교환은 적음
버블 정렬	O(n²)	O	전체 요소 스왑 반복
삽입 정렬	O(n²)	O	정렬된 영역에 삽입
퀵 정렬	O(n log n)	X	가장 빠른 비안정 정렬
병합 정렬	O(n log n)	O	안정적이지만 메모리 추가 필요

선택 정렬은 가장 단순하면서 비교 기반 정렬의 기본 구조를 잘 보여준다.

---

8. 활용 사례

분야	활용 예시
교육용	정렬 알고리즘 학습용 예시
시스템 프로그래밍	교환 횟수를 줄이고자 할 때
알고리즘 비교 실험	기본 정렬 알고리즘 성능 비교

실제 환경에서는 대용량 데이터보다는 학습 목적이나 이론 비교에 활용된다.

---

9. 결론

선택 정렬은 간단한 구조 덕분에 알고리즘 입문용으로 널리 사용되며, 비교 정렬의 핵심 원리를 이해하는 데 유용하다. 효율성은 낮지만 교환 횟수가 적고 구현이 간단하여, 작은 데이터나 정렬 횟수를 최소화하고자 하는 상황에 적합하다. 알고리즘의 기본기를 다지기 위한 필수 학습 알고리즘이다.