선택 정렬 (Selection Sort)

개념

가장 작은 값을 찾아 맨 앞부터 차례대로 채워나가는 정렬

남은 부분에서 최솟값을 선택(Select)하여 정렬

---

시간복잡도

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

---

특징

장점

• 구현 간단: 이해하기 쉬운 정렬
• 제자리 정렬: 추가 메모리 불필요
• 교환 횟수 적음: 최대 n-1번의 교환

단점

• 매우 느림: O(n²) 시간복잡도
• 불안정 정렬: 같은 값의 순서가 바뀔 수 있음
• 비효율적: 이미 정렬되어 있어도 O(n²)

---

구현 방법

기본 구현

def selection_sort(arr):
    n = len(arr)
 
    for i in range(n - 1):
        # 최솟값의 인덱스 찾기
        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]))
# [11, 12, 22, 25, 64]

---

내림차순 구현

def selection_sort_desc(arr):
    n = len(arr)
 
    for i in range(n - 1):
        # 최댓값의 인덱스 찾기
        max_idx = i
 
        for j in range(i + 1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j
 
        # 최댓값을 현재 위치와 교환
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
 
    return arr
 
# 테스트
print(selection_sort_desc([64, 25, 12, 22, 11]))
# [64, 25, 22, 12, 11]

---

동작 과정

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

1회전: (최솟값 11 찾기)
[11, 25, 12, 22, 64]  ← 11과 64 교환

2회전: (최솟값 12 찾기)
[11, 12, 25, 22, 64]  ← 12와 25 교환

3회전: (최솟값 22 찾기)
[11, 12, 22, 25, 64]  ← 22와 25 교환

4회전: (최솟값 25 찾기)
[11, 12, 22, 25, 64]  ← 이미 정렬됨

완료: [11, 12, 22, 25, 64]

---

템플릿

def selection_sort_template(arr):
    n = len(arr)
 
    # i: 정렬된 부분의 끝 (0부터 n-2까지)
    for i in range(n - 1):
        # 최솟값의 인덱스 초기화
        min_idx = i
 
        # j: 미정렬 부분에서 최솟값 찾기
        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

---

핵심 요약

개념	설명
원리	최솟값 선택 후 앞으로 이동
시간복잡도	O(n²) - 항상 동일
공간복잡도	O(1)
안정성	불안정 정렬
교환 횟수	최대 n-1번

---

다른 정렬과 비교

정렬	시간복잡도 (평균)	공간복잡도	안정성	교환 횟수
선택 정렬	O(n²)	O(1)	불안정	최대 n-1
버블 정렬	O(n²)	O(1)	안정	최대 n²/2
삽입 정렬	O(n²)	O(1)	안정	최대 n²/2
병합 정렬	O(n log n)	O(n)	안정	-
퀵 정렬	O(n log n)	O(log n)	불안정	-

---

주의사항

1. 불안정 정렬

# 같은 값의 순서가 바뀔 수 있음
arr = [(5, 'a'), (3, 'b'), (5, 'c'), (2, 'd')]
# 정렬 후: (5, 'c')가 (5, 'a')보다 앞에 올 수 있음

2. 최적화의 한계

# 이미 정렬되어 있어도 O(n²)
# 조기 종료 불가능
# 버블 정렬처럼 최선의 경우 O(n)으로 개선 안 됨

3. 사용 권장 사항

# 교환 비용이 매우 클 때만 고려
# 예: 큰 객체의 물리적 이동이 비쌀 때
# 일반적으로는 삽입 정렬이나 다른 정렬 사용 권장

---

자주 나오는 문제 유형

1. K번째 작은 수 찾기

문제: 배열에서 K번째로 작은 수 찾기

def find_kth_smallest(arr, k):
    n = len(arr)
 
    # k-1번만 선택 정렬 수행
    for i in range(k):
        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[k - 1]
 
# 테스트
print(find_kth_smallest([7, 10, 4, 3, 20, 15], 3))  # 7
 
# 시간복잡도: O(k × n)

핵심: K번만 선택 정렬을 수행하면 됨

---

2. 선택 정렬 최적화 (양방향 선택)

문제: 최솟값과 최댓값을 동시에 찾아 양쪽 끝에 배치

def selection_sort_bidirectional(arr):
    left = 0
    right = len(arr) - 1
 
    while left < right:
        min_idx = left
        max_idx = right
 
        # 최솟값과 최댓값 동시에 찾기
        for i in range(left, right + 1):
            if arr[i] < arr[min_idx]:
                min_idx = i
            if arr[i] > arr[max_idx]:
                max_idx = i
 
        # 최솟값을 왼쪽 끝으로
        arr[left], arr[min_idx] = arr[min_idx], arr[left]
 
        # max_idx가 left를 가리키고 있었다면 갱신
        if max_idx == left:
            max_idx = min_idx
 
        # 최댓값을 오른쪽 끝으로
        arr[right], arr[max_idx] = arr[max_idx], arr[right]
 
        left += 1
        right -= 1
 
    return arr
 
# 테스트
print(selection_sort_bidirectional([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]
 
# 시간복잡도: O(n²) - 비교 횟수는 절반으로 감소

핵심: 한 번의 순회로 최솟값과 최댓값 모두 처리

---

3. 교환 횟수 세기

문제: 선택 정렬 중 발생하는 교환 횟수 세기

def selection_sort_count_swaps(arr):
    n = len(arr)
    swap_count = 0
 
    for i in range(n - 1):
        min_idx = i
 
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
 
        # 교환이 필요한 경우에만
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            swap_count += 1
 
    return arr, swap_count
 
# 테스트
result, swaps = selection_sort_count_swaps([64, 25, 12, 22, 11])
print(f"정렬 결과: {result}")
print(f"교환 횟수: {swaps}")  # 4
 
# 최대 교환 횟수: n-1

핵심: 각 회전마다 최대 1번의 교환만 발생

---

추천 연습 문제

기초

• 백준 2750번 - 수 정렬하기
• 백준 23881번 - 알고리즘 수업 - 선택 정렬 1

---

선택 정렬 vs 버블 정렬

특성	선택 정렬	버블 정렬
교환 횟수	최대 n-1번	최대 n²/2번
비교 횟수	n(n-1)/2번	n(n-1)/2번
안정성	불안정	안정
최선의 경우	O(n²)	O(n) (최적화 시)
사용 시기	교환 비용이 클 때	거의 정렬된 경우

---

언제 사용할까?

사용 가능

• 교환 비용이 매우 클 때: 큰 객체의 물리적 이동이 비쌀 때
• 메모리가 제한적일 때: O(1) 공간복잡도
• 작은 데이터: n < 10 정도

사용 불가

• 일반적인 경우: 삽입 정렬이 더 나음
• 거의 정렬된 경우: 삽입 정렬이 O(n)
• 대용량 데이터: 병합 정렬, 퀵 정렬 사용
• 안정 정렬 필요 시: 병합 정렬, 삽입 정렬 사용

결론: 교환 비용이 매우 클 때만 고려, 그 외엔 다른 정렬 사용!