[알고리즘 심층분석 #2] 선택 정렬(Selection Sort) 동작 원리, 시간 복잡도, 불안정 정렬 특성 완벽 정리

기본 정렬 알고리즘 중 버블 정렬 다음으로 자주 접하는 선택 정렬(Selection Sort)입니다.

"버블 정렬과 선택 정렬은 어떻게 다를까?"

"선택 정렬은 왜 교환 횟수가 적은데도 불안정 정렬(Unstable Sort)일까?"

선택 정렬의 기본 개념부터 회전별 동작 과정, 파이썬 코드 구현, 시간·공간 복잡도 유도 과정, 그리고 시험 단골 서술형인 불안정 정렬의 구체적 사례까지 심층 분석해 드립니다!

1. 선택 정렬(Selection Sort)이란?

선택 정렬은 정렬되지 않은 전체 데이터 중 가장 작은 값(최소값, 오름차순 기준)을 '선택'하여 맨 앞에 위치한 데이터와 교환(Swap)하는 과정을 반복하는 알고리즘입니다.

• 핵심 특징: 1회전을 수행할 때마다 정렬되지 않은 영역에서 최솟값을 찾아 정렬된 영역의 맨 뒤로 배치합니다. 따라서 회전이 거듭될수록 앞쪽부터 차례대로 최종 정렬 위치가 확정됩니다.
• 버블 정렬과의 차이점: 버블 정렬은 인접한 원소를 비교할 때마다 매번 교환(Swap)이 일어나지만, 선택 정렬은 전체 탐색을 마친 후 1회전에 단 한 번만 교환을 수행합니다.

선택 정렬의 최소값 선택 및 위치 교환 프로세스. 출처: filo / Getty Images

2. 단계별 동작 예시 (Step-by-Step)

배열 [64, 25, 12, 22, 11]을 오름차순으로 정렬하는 과정을 살펴보겠습니다.

• 1회전:
  • 전체 영역 [64, 25, 12, 22, 11] 중 최솟값인 11을 찾음
  • 맨 앞의 64와 최솟값 11을 교환 -> [11, 25, 12, 22, 64]
  • 👉 1회전 완료: 11 정렬 확정!
• 2회전: (11 제외)
  • 남은 영역 [25, 12, 22, 64] 중 최솟값인 12를 찾음
  • 두 번째 위치인 25와 12를 교환 -> [11, 12, 25, 22, 64]
  • 👉 2회전 완료: 12 정렬 확정!
• 3회전: (11, 12 제외)
  • 남은 영역 [25, 22, 64] 중 최솟값인 22를 찾음
  • 세 번째 위치인 25와 22를 교환 -> [11, 12, 22, 25, 64]
  • 👉 3회전 완료: 22 정렬 확정!
• 4회전: (11, 12, 22 제외)
  • 남은 영역 [25, 64] 중 최솟값 25가 이미 제자리에 있음 (교환 없음) -> [11, 12, 22, 25, 64]
  • 👉 4회전 완료: 전체 정렬 완료!

3. 코드 구현 (Python)

Python

 

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n - 1):
        # i번째 위치에 들어갈 최솟값의 인덱스 저장
        min_idx = i
        
        # i 이후 영역에서 최솟값 탐색
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        # 찾은 최솟값을 i번째 원소와 교환 (1회전에 1번만 교환)
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

4. 복잡도 및 특성 분석 (★시험 유도 포인트)

🔹 시간 복잡도 유도

N개의 데이터가 있을 때, 첫 번째 회전에서는 (N-1)번 비교, 두 번째는 (N-2)번 비교... 마지막은 1번 비교를 수행합니다.

• 총 비교 횟수: (N-1) + (N-2) + ... + 1 = N(N-1) / 2
• 최악의 경우 (Worst Case): 역순 정렬된 상태 -> O(N^2)
• 평균의 경우 (Average Case): O(N^2)
• 최선의 경우 (Best Case): 이미 정렬된 상태라도 최솟값을 찾는 비교 과정을 생략할 수 없으므로 -> O(N^2)

🔹 공간 복잡도

• 기존 배열 내부에서 위치만 교환하는 제자리 정렬(In-Place Sort)에 해당합니다. -> O(1)

5. 시험 단골 질문: 선택 정렬은 왜 불안정 정렬(Unstable Sort)인가?

안정 정렬(Stable Sort): 값이 같은 원소들이 정렬 후에도 기존의 상대적인 순서를 유지함.

불안정 정렬(Unstable Sort): 값이 같은 원소들의 기존 상대적 순서가 깨질 수 있음.

선택 정렬은 떨어져 있는 원소 간의 대규모 교환(Swap)이 일어나기 때문에 동등한 키 값을 가진 원소의 기존 순서가 뒤바뀔 수 있습니다.

💡 불안정 정렬 증명 예시

배열 [5(A), 5(B), 2, 1]을 선택 정렬로 오름차순 정렬해 보겠습니다.

1. 1회전:
   • 전체 중 최솟값은 1입니다.
   • 맨 앞의 5(A)와 1을 교환합니다.
   • 변환 후 배열: [1, 5(B), 2, 5(A)]
2. 결과적으로 정렬 전에는 5(A)가 5(B)보다 앞에 있었지만, 정렬 후에는 5(B)가 5(A)보다 앞에 위치하게 됩니다!
3. 따라서 선택 정렬은 불안정 정렬(Unstable Sort)입니다.

6. 한눈에 끝내는 핵심 요약표 (★시험 필수)

구분	주요 내용 및 특징
기본 매커니즘	정렬 안 된 영역에서 최솟값을 선택하여 맨 앞 원소와 교환
시간 복잡도	최악, 평균, 최선 모두 O(N^2)
공간 복잡도	O(1) (제자리 정렬 - In-Place)
안정성 여부	불안정 정렬 (Unstable Sort)
장점	버블 정렬에 비해 데이터 교환(Swap) 횟수가 O(N)으로 적음
단점	데이터가 이미 정렬되어 있어도 비교 횟수가 줄어들지 않고 O(N^2) 유지