선택 정렬 (Selection Sort)

매번 가장 작은 값을 찾아 맨 앞과 교환하는 선택 정렬을 막대 애니메이션으로 확인하세요. 교환이 n번뿐이라 비용이 큰 환경에서 유리한 이유를 카운터로 비교할 수 있습니다.

알고리즘

배열

크기48
비교 중교환/쓰기피벗/기준읽기정렬 확정
속도50×

비교

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번으로, 모든 정렬 알고리즘 중 쓰기 횟수가 가장 적은 편입니다. 플래시 메모리처럼 쓰기 비용이 비싼 환경에서 이 특성이 장점이 됩니다.

같은 값을 교환으로 건너뛰며 옮기기 때문에 상대 순서가 깨질 수 있어 불안정 정렬입니다. 위에서 '교환/쓰기' 카운터가 버블 정렬보다 훨씬 적게 올라가는 것을 비교해 보세요. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.

자주 묻는 질문

선택 정렬의 장점은 무엇인가요?
교환(쓰기) 횟수가 n−1번으로 매우 적습니다. 메모리 쓰기 비용이 비싸거나 객체 이동이 무거운 경우 비교가 많더라도 전체 비용이 유리할 수 있습니다.
선택 정렬은 안정 정렬인가요?
아닙니다. 최솟값과 맨 앞 원소를 교환할 때 사이에 있던 같은 값들의 순서가 바뀔 수 있어 불안정 정렬로 분류됩니다.
버블 정렬과 선택 정렬 중 뭐가 빠른가요?
비교 횟수는 비슷하지만 교환 횟수가 선택 정렬이 압도적으로 적어 일반적으로 선택 정렬이 빠릅니다. 다만 둘 다 O(n²)이라 큰 데이터에서는 다른 알고리즘을 씁니다.

다른 알고리즘 보기