선택 정렬 (Selection Sort)
개요
선택 정렬은 배열에서 가장 작은 값을 찾아 앞쪽으로 차례대로 정렬하는 알고리즘입니다.
매 회전마다 최소값을 찾아 현재 위치와 한 번만 교환하기 때문에,
스왑 횟수는 적지만 비교는 많습니다.
정렬 방식 설명 (오름차순 기준)
- i번째부터 끝까지 중 가장 작은 값을 찾음
- 그 값을 i번째와 스왑
- 이를 i = 0 ~ n-2까지 반복
예시
배열: {5, 3, 2, 4, 1}
1회전: min = 1 → arr[0] <-> arr[4] → {1, 3, 2, 4, 5}
2회전: min = 2 → arr[1] <-> arr[2] → {1, 2, 3, 4, 5}
3회전: min = 3 → 그대로
4회전: min = 4 → 그대로정렬 완료: {1, 2, 3, 4, 5}
C언어 코드 + 상세 주석
void selection_sort(int arr[], int n) {
int min_idx, temp;
for (int i = 0; i < n - 1; i++) {
// i는 현재 정렬할 위치 (앞에서부터 하나씩)
min_idx = i;
// i번째 값을 현재 최소값이라고 가정
for (int j = i + 1; j < n; j++) {
// i 이후의 모든 원소와 비교
if (arr[j] < arr[min_idx]) {
// 더 작은 값을 발견하면 그 인덱스를 기록
min_idx = j;
}
}
// 최소값이 현재 위치가 아니라면 교환
temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}시간 복잡도
| 케이스 | 시간 복잡도 |
|---|---|
| 최악 | O(n²) |
| 평균 | O(n²) |
| 최선 | O(n²) |
- 비교 횟수는 항상 많음
- 스왑 횟수는 O(n) → 다른 정렬보다 효율적일 수도 있음
특징 요약
- 직관적이고 구현 간단함
- 버블 정렬보다 교환 횟수는 적음
- 성능은 떨어짐 (실무에서는 잘 안 씀)
- 정렬 기준을 반대로 바꾸면 내림차순 정렬도 가능
전체 예제
#include <stdio.h>
void selection_sort(int arr[], int n) {
int min_idx, temp;
for (int i = 0; i < n - 1; i++) {
min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[5] = {5, 3, 2, 4, 1};
printf("정렬 전 배열: ");
print_array(arr, 5);
selection_sort(arr, 5);
printf("정렬 후 배열: ");
print_array(arr, 5);
return 0;
}