Selection Sort

selection sort, 선택 정렬

정의

Selection Sort (선택 정렬) 는 매 단계에서 남은 원소 중 최솟값을 찾아 맨 앞으로 보내는 정렬. n-1 번의 단계 후 정렬 완료.

다른 O(n²) 정렬과 달리 교환 횟수가 최대 n-1 번 으로 매우 적다. 교환 비용이 비싼 환경 (예: 큰 객체 swap, 디스크 I/O) 에서 의미 있다.

전체 비교는 정렬 알고리즘 참고.

시각화

알고리즘

selectionSort(arr):
  n = length(arr)
  for i = 0 to n-1:
    minIdx = i
    for j = i+1 to n-1:
      if arr[j] < arr[minIdx]:
        minIdx = j
    swap(arr[i], arr[minIdx])

핵심 동작

배열을 정렬된 부분 과 미처리 부분 으로 나눔. 미처리 부분에서 최솟값을 찾아 정렬된 부분의 끝으로 보냄.

[ 정렬됨 | 미처리 (최솟값 찾기) ]

초기:        [ | 5, 2, 8, 1, 4 ]    min = 1 (idx 3)
1단계:       [1 | 5, 2, 8, 4 ]      min = 2 (idx 2)  ← 5와 1 swap
2단계:       [1, 2 | 5, 8, 4 ]      min = 4 (idx 4)
3단계:       [1, 2, 4 | 5, 8 ]      min = 5 (idx 3)
4단계:       [1, 2, 4, 5 | 8 ]      마지막
완료:        [1, 2, 4, 5, 8]

복잡도

항목	값
시간 (최선)	O(n²) (입력 무관)
시간 (평균)	O(n²)
시간 (최악)	O(n²)
공간	O(1)
비교 횟수	n(n-1)/2 (항상 같음)
교환 횟수	최대 n-1 번
안정성	✗ Unstable
In-place	✓

입력 무관 O(n²)

Insertion/Bubble 과 달리 이미 정렬된 입력에서도 같은 시간 이 든다. 최솟값을 찾기 위해 매번 전체를 스캔하기 때문.

// 이미 정렬됨
[1, 2, 3, 4, 5]
// 단계 1: 4 비교 (min = 1)
// 단계 2: 3 비교 (min = 2)
// ...
// 총 비교: n(n-1)/2, swap: 0

교환 횟수가 적은 이점

매 단계에서 최대 한 번 의 교환. 그래서 n-1 회 이하 의 교환으로 정렬 완료.

알고리즘	비교	교환
Bubble	O(n²)	O(n²)
Insertion	O(n²)	O(n²)
Selection	O(n²)	O(n)

언제 의미가 있는가?

// 큰 객체 배열 정렬
const items = [/* 각 객체가 1MB */];
// Bubble/Insertion: 데이터 이동만 GB 단위
// Selection: n 번의 포인터 교환

C++ 의 std::swap 처럼 swap 비용이 큰 경우 Selection 이 의외로 빠를 수 있다.

안정 정렬이 아닌 이유

[("A", 3), ("B", 1), ("C", 3), ("D", 2)]
// key 로 정렬 시:
// 단계 1: min = 1 (B) → A와 B swap
//   → [("B", 1), ("A", 3), ("C", 3), ("D", 2)]
// 단계 2: min = 2 (D) → A와 D swap
//   → [("B", 1), ("D", 2), ("C", 3), ("A", 3)]
// 결과: A 와 C 의 원래 순서 (A 먼저) 가 뒤바뀜 (C 가 먼저)

같은 key 의 원소가 swap 으로 뒤집힐 수 있다.

안정 변형: Stable Selection Sort

swap 대신 삽입 으로 처리하면 안정 정렬 가능. 단, 시간이 O(n²) 에서 O(n²) 로 변하지 않지만 공간이 O(n) 으로 증가.

Heap Sort 와의 관계

Selection Sort 의 본질은 “남은 부분에서 최솟값 선택”. 이 선택을 효율화한 것이 Heap Sort.

단계	Selection	Heap
최솟값 찾기	O(n) 스캔	O(log n) heap pop
총 시간	O(n²)	O(n log n)

Heap Sort 는 사실상 “Selection Sort 의 효율적 구현”.

Heap Sort 와의 비교 (개념적 진화)

Selection Sort:
  매번 남은 부분 전체 스캔 → O(n) × n = O(n²)

Heap Sort:
  남은 부분을 heap 으로 유지 → O(log n) × n = O(n log n)

작은 입력 + 비싼 교환 케이스

Selection 이 의미 있는 드문 케이스:

// 노드 배열 정렬, 각 노드가 거대한 그래프 객체를 참조
const nodes = [/* 30개, 각각 100KB */];
nodes.sort(byPriority);

이 경우:

• Insertion / Bubble: 비교마다 데이터 이동 → 메모리 트래픽 큼
• Selection: 비교는 많지만 swap 은 30 번 이하 → 데이터 이동 최소

다만 보통의 JS / Python 정렬에서는 의미 없다 (참조만 swap 됨).

함정

1. 거의 정렬된 입력에서도 느림

Insertion Sort 가 O(n) 으로 처리하는 케이스에서 Selection 은 여전히 O(n²). 이 점에서 거의 정렬된 입력에는 Insertion 이 항상 우월.

2. 안정성 없음

같은 키의 원래 순서를 보존해야 하면 사용 불가.

3. 교육 외에는 거의 안 쓰임

실무에서 Selection Sort 를 쓸 일은 사실상 없다. 작은 입력 → Insertion, 큰 입력 → Quick/Merge, in-place + 보장 → Heap.

참고

• 정렬 알고리즘
• Bubble Sort
• Insertion Sort
• Heap Sort
• Knuth, TAOCP Vol. 3 §5.2.3