토픽 6 / 82

선택 정렬 (Selection Sort)

매번 최소값(또는 최대값)을 찾아 정렬된 부분 끝에 배치하는 정렬 알고리즘

목적: 단순 정렬, 교환 횟수 최소화

특징: 단순, 불안정 정렬, 제자리 정렬, 교환 O(n)

동작: n-1번 패스 수행. 각 패스에서 미정렬 부분 전체를 순회하여 최소값의 위치를 찾고, 미정렬 부분의 첫 번째 요소와 교환. 정렬된 부분이 앞에서부터 1개씩 확장

시간 복잡도: 최선·평균·최악 O(n²) - 항상 모든 요소 비교

공간 복잡도: O(1) - 제자리

교환 횟수: O(n) - 버블보다 적음

장점: 단순, 제자리, 교환 적음

단점: 느림(O(n²)), 불안정, 비적응적(정렬 여부 무관)

적용사례: 교육, 메모리 쓰기 비용 높을 때, 소규모 데이터

비교: 선택(교환적음/불안정) vs 삽입(안정/적응적) vs 버블(교환많음)

연관: 정렬, 버블 정렬, 삽입 정렬, O(n²)