정의
선택 정렬은 배열에서 가장 작은 값을 찾아서 맨 앞의 값과 교환하는 과정을 반복하여 정렬하는 알고리즘입니다.
핵심 특성
- ✓매 라운드마다 남은 배열에서 최솟값을 "선택" - 이름의 유래
- ✓교환 횟수가 적음 - 최대 n-1번만 교환 (메모리 쓰기가 비싼 환경에 유리)
- ✓불안정 정렬 - 같은 값의 순서가 바뀔 수 있음
- ✓입력 데이터에 관계없이 항상 O(n²) - 이미 정렬된 배열도 모든 비교를 수행
활용 사례
이런 상황에서 사용됩니다:
💾
메모리 쓰기가 비싼 환경
플래시 메모리처럼 쓰기 횟수가 제한된 저장장치에서 교환 횟수를 최소화
📚
교육용 알고리즘
정렬 알고리즘의 기본 원리를 이해하기 쉬운 간단한 구조
🔢
작은 데이터셋
데이터 크기가 작을 때는 단순하고 구현이 쉬운 선택 정렬이 효율적
주요 연산
주요 연산들:
최솟값 찾기
O(n)정렬되지 않은 부분에서 가장 작은 값의 위치를 찾습니다.
값 교환
O(1)찾은 최솟값을 현재 정렬 위치의 값과 교환합니다.
복잡도
시간 복잡도
최선
O(n²)
평균
O(n²)
최악
O(n²)
공간 복잡도
O(1)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기