소개
선택 정렬(Selection sort)는 제자리 정렬 알고리즘의 하나로 가장 작은(혹은 가장 큰) 원소를 찾아서 교체하는 알고리즘입니다. 말 그대로 원소를 선택해서 정렬합니다.
정렬 과정
다음과 같이 다섯 개의 정수가 주어졌을 때, 오름 차순으로 정렬해보겠습니다.
+-----+-----+-----+-----+-----+
| 5 | 4 | 1 | 3 | 2 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 5 | 4 | 1 | 3 | 2 |
+-----+-----+-----+-----+-----+
우선 인덱스 0을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 1부터 원소 끝까지 순회하면서 가장 작은 원소를 찾습니다. 그리고 찾은 원소를 가장 처음 원소와 교체합니다.
+-----+-----+-----+-----+-----+
| 1 | 4 | 5 | 3 | 2 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 4 | 5 | 3 | 2 |
+-----+-----+-----+-----+-----+
가장 작은 원소가 처음 원소와 교체됐기 때문에 다음 단계부터는 인덱스 1을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 2부터 원소 끝까지 순회하면서 가장 작은 원소를 인덱스 1의 원소와 교체합니다.
+-----+-----+-----+-----+-----+
| 1 | 2 | 5 | 3 | 4 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 5 | 3 | 4 |
+-----+-----+-----+-----+-----+
이어서 동일한 방법으로 시작 위치를 한 칸씩 증가시키면서 가장 작은 원소와 교체해주면 됩니다.
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 5 | 4 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 5 | 4 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 |
+-----+-----+-----+-----+-----+
알고리즘 분석
비교 횟수
선택 정렬은 한 번의 순회가 끝나면 다음 순회는 비교 대상이 하나씩 줄어듭니다. 전체 원소의 개수가 n 개면, 총 (n−1) 번 검사를 했을 때 한 번 정렬이 완료됩니다.
앞 선 예제에서 총 원소가 5개 이므로, 4+3+2+1=10 번 검사하면 전체 정렬이 완료됩니다. 이를 수식으로 일반화하면 다음과 같습니다.
(n−1)+(n−2)+...+2+1=(n−1)∗n/2=n(n−1)/2
자리 교환 횟수
최선의 경우(이미 정렬된 원소들이 주어지는 경우), 자리 교환이 일어나지 않아서 시간 복잡도에 영향이 없습니다.
그러나 최악의 경우(역순 정렬된 원소들이 주어지는 경우), 순회 횟수 만큼 자리 교환이 일어납니다.
구현
void selection_sort(int *array) {
int temp, minIndex;
for (int i = 0; i < SIZE - 1; i++) {
minIndex = i;
for (int j = i + 1; j < SIZE; j++) {
if (array[minIndex] > array[j])
minIndex = j;
print_array(array);
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
void selection_sort(int *array) {
int temp, minIndex;
for (int i = 0; i < SIZE - 1; i++) {
minIndex = i;
for (int j = i + 1; j < SIZE; j++) {
if (array[minIndex] > array[j])
minIndex = j;
print_array(array);
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
정리
선택 정렬과 거품 정렬은 언뜻 비슷해보입니다. 그러나 거품 정렬은 최악의 경우 인접한 모든 원소마다 자리 교환이 일어나지만, 선택 정렬은 비교만 거품 정렬과 동일하게 할 뿐 교환은 순회 당 한 번입니다. 이러한 이유로 선택 정렬이 거품 정렬 보다 항상 우수합니다.