매번 가장 작은 값을 찾아 맨 앞과 교환하는 선택 정렬을 막대 애니메이션으로 확인하세요. 교환이 n번뿐이라 비용이 큰 환경에서 유리한 이유를 카운터로 비교할 수 있습니다.
알고리즘
배열
비교
0
교환/쓰기
0
스텝
0/1,577
읽기
0
보조 메모리
0
재귀 깊이
1/1
재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요.
의사코드
for i ← 0 to n−1
min ← i
for j ← i+1 to n−1
if a[j] < a[min]
min ← j
swap a[i] ↔ a[min]
시간 복잡도
| 최선 | O(n²) |
|---|---|
| 평균 | O(n²) |
| 최악 | O(n²) |
| 공간 | O(1) |
| 안정 | X |
선택 정렬은 정렬되지 않은 구간에서 가장 작은 값을 찾아(선택) 그 구간의 맨 앞 원소와 교환하는 알고리즘입니다. 보라색 막대가 현재까지 찾은 최솟값의 위치이고, 한 칸씩 앞에서부터 정렬이 확정됩니다.
비교는 입력과 무관하게 항상 n(n−1)/2번 발생해 최선·평균·최악 모두 O(n²)입니다. 반면 교환은 정확히 n−1번으로, 모든 정렬 알고리즘 중 쓰기 횟수가 가장 적은 편입니다. 플래시 메모리처럼 쓰기 비용이 비싼 환경에서 이 특성이 장점이 됩니다.
같은 값을 교환으로 건너뛰며 옮기기 때문에 상대 순서가 깨질 수 있어 불안정 정렬입니다. 위에서 '교환/쓰기' 카운터가 버블 정렬보다 훨씬 적게 올라가는 것을 비교해 보세요. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.