보통
Selection Sort
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 선택정렬(nums):2 반복 i = 0 … n-2:3 최소 = i4 반복 j = i+1 … n-1:5 만약 nums[j] < nums[최소]: 최소 = j6 nums[i] ↔ nums[최소] // 최솟값을 앞으로
변수
- i
- 0
- 최소
- 0
1 / 190 번째 자리에 놓을 최솟값을 남은 구간에서 찾습니다.
남은 구간에서 최솟값을 골라 앞으로 보내며 정렬한다 — 교환이 적다(최대 n−1번).
왜 헷갈리는가
버블·삽입 정렬과 함께 O(n²)라 실무 대량 정렬엔 안 쓴다. 특징은 '비교는 많지만 교환(쓰기)이 극도로 적다'는 점 — 쓰기 비용이 비싼 상황에서 의미가 있다.
핵심 아이디어
매 회전마다 아직 정렬 안 된 구간을 전부 훑어 최솟값을 찾고, 그 구간의 맨 앞과 한 번만 교환한다.
복잡도
시간 O(n²)(비교), 교환은 O(n)·공간 O(1). 불안정 정렬(같은 값 순서가 바뀔 수 있음).
실무에서 어디에 쓰나
대량 정렬은 내장 함수를 쓰되, '쓰기 최소화'가 필요한 특수 상황에서 개념이 쓰인다.
- 쓰기 비용이 큰 매체: 플래시/EEPROM처럼 쓰기 횟수를 아껴야 할 때
- Top-k 선택: '가장 작은/큰 k개만' 뽑을 때 선택 과정만 부분 사용
- 교육: 비교 vs 교환 비용을 분리해 이해하는 기준선
- 임베디드: 아주 작은 n에서 단순·예측가능한 정렬
흔한 실수
안정성이 필요한데 선택 정렬 쓰기(불안정). 교환이 적다고 전체가 빠르다고 오해(비교는 여전히 O(n²)).
기억할 것
- 비교 O(n²), 교환은 최대 n−1번.
- 쓰기 비용이 클 때 의미.
- 불안정 정렬.
- Top-k 선택의 부분 동작.