알고리즘SortO(n²)Comparison
선택 정렬
매 패스마다 최솟값을 찾아 앞으로 가져오는 정렬
시각화 로드 중...
알고리즘 복잡도
최선O(n²)
평균O(n²)
최악O(n²)
공간O(1)
불안정 정렬
개요
Algorithm Overview
선택 정렬(Selection Sort)은 미정렬 구간을 전수 조사하여 가장 작은 최솟값(Minimum)의 위치를 찾은 뒤, 미정렬 구간의 맨 첫 번째 원소와 단 한 번만 교환(Swap)하는 정렬 알고리즘입니다.
01
선택 정렬의 핵심 메커니즘
- 최솟값 탐색 (Find Minimum): 현재 인덱스 $i$부터 배열 끝까지 선형 탐색하여 가장 작은 값의 인덱스(
min_idx)를 찾습니다. - 단일 스왑 (Single Swap): 찾은 최솟값을 $i$번째 원소와 맞바꿉니다. 패스당 스왑 횟수가 정확히 1회로 제한됩니다.
- 정렬 경계 확장: 정렬 완료 경계를 우측으로 한 칸 이동시키며 $n-1$회 반복합니다.
02
복잡도 및 트레이드오프
- 시간 복잡도: 데이터 정렬 상태와 무관하게 항상 $O(n^2)$ 비교 연산을 수행합니다.
- 교환 횟수 최소화: 버블 정렬 대비 스왑 횟수가 최대 $n$회에 불과하여 메모리 쓰기(Write) 비용이 매우 비싼 특수 임베디드 장치에 유용합니다.
- 불안정 정렬 (Unstable Sort): 원거리 스왑으로 인해 동일한 키를 가진 원소의 상대적 순서가 뒤바뀔 수 있습니다.
핵심 단계
- 1
미정렬 영역(0~n-1)에서 최솟값의 인덱스를 찾음
- 2
최솟값을 미정렬 영역의 첫 번째 원소와 교환
- 3
정렬 경계를 오른쪽으로 한 칸 이동
- 4
n-1회 반복 후 완전 정렬 완료
핵심 개념 및 실무 적용 분야
✓교환 비용이 큰 환경(예: 플래시 메모리 쓰기 최소화)
✓알고리즘 비교 학습 (버블 정렬과 비교)