선택 정렬 (Selection Sort)

들어가는 말

선택 정렬은 매 회차마다 오름차순이면 미정렬 구간에서 최솟값을, 내림차순이면 최댓값을 찾아 그 구간의 맨 앞과 교환하는 방식으로 배열을 정렬한다.
값을 직접 선택해서 앞으로 가져오기 때문에 선택 정렬이라고 부른다.
시간 복잡도가 O(n²)라 효율적인 알고리즘은 아니지만, 동작 방식이 직관적이라 정렬 알고리즘의 기본 구조를 이해하기 좋다.

정렬 과정 살펴보기

7 4 9 2 6을 오름차순으로 정렬해 보자.

1회차

처음에는 배열 전체가 아직 정렬되지 않은 구간이다.
첫 번째 값 7을 최솟값으로 정한 뒤, 나머지 값과 차례대로 비교하면서 더 작은 값을 찾는다.
이때 교환은 해당 회차의 모든 비교가 끝난 뒤 최대 한 번만 이루어진다.

단계	비교	판단	최솟값	배열 상태
1회차 시작 전	-	첫 번째 값 7을 최솟값으로 지정	7	7 4 9 2 6
1회차 1번째	7과 4	4가 더 작으므로 최솟값 변경	4	7 4 9 2 6
1회차 2번째	4와 9	4가 더 작으므로 최솟값 유지	4	7 4 9 2 6
1회차 3번째	4와 2	2가 더 작으므로 최솟값 변경	2	7 4 9 2 6
1회차 4번째	2와 6	2가 더 작으므로 최솟값 유지	2	7 4 9 2 6
교환	7과 2	최솟값이 첫 번째 자리에 오도록 교환	2	2 4 9 7 6

1회차가 끝나면 가장 작은 값 2의 자리가 확정된다.

2회차

2의 자리는 이미 확정되었으므로 4 9 7 6에서 최솟값을 찾는다.

단계	비교	판단	최솟값	배열 상태
2회차 시작 전	-	두 번째 값 4를 최솟값으로 지정	4	2 4 9 7 6
2회차 1번째	4와 9	4가 더 작으므로 최솟값 유지	4	2 4 9 7 6
2회차 2번째	4와 7	4가 더 작으므로 최솟값 유지	4	2 4 9 7 6
2회차 3번째	4와 6	4가 더 작으므로 최솟값 유지	4	2 4 9 7 6
교환	-	최솟값이 제자리에 있으므로 유지	4	2 4 9 7 6

2회차가 끝나면 4의 자리가 확정된다.

3회차

2와 4의 자리는 이미 확정되었으므로 9 7 6에서 최솟값을 찾는다.

단계	비교	판단	최솟값	배열 상태
3회차 시작 전	-	세 번째 값 9를 최솟값으로 지정	9	2 4 9 7 6
3회차 1번째	9와 7	7이 더 작으므로 최솟값 변경	7	2 4 9 7 6
3회차 2번째	7과 6	6이 더 작으므로 최솟값 변경	6	2 4 9 7 6
교환	9와 6	최솟값이 세 번째 자리에 오도록 교환	6	2 4 6 7 9

3회차가 끝나면 6의 자리가 확정된다.

4회차

2, 4, 6의 자리는 이미 확정되었으므로 7 9에서 최솟값을 찾는다.

단계	비교	판단	최솟값	배열 상태
4회차 시작 전	-	네 번째 값 7을 최솟값으로 지정	7	2 4 6 7 9
4회차 1번째	7과 9	7이 더 작으므로 최솟값 유지	7	2 4 6 7 9
교환	-	최솟값이 제자리에 있으므로 유지	7	2 4 6 7 9

4회차가 끝나면 7의 자리가 확정된다.
원소 5개 중 4개의 자리가 확정되면 남은 값의 자리도 자연스럽게 정해지므로 정렬이 끝난다.

회차별 정렬 과정 요약

회차	비교 횟수	교환 횟수	확정되는 값	배열 상태
시작 전	-	-	-	7 4 9 2 6
1회차	4번	1번	2	2 4 9 7 6
2회차	3번	0번	4	2 4 9 7 6
3회차	2번	1번	6	2 4 6 7 9
4회차	1번	0번	7	2 4 6 7 9

시간 복잡도

선택 정렬은 각 회차마다 미정렬 구간의 최솟값을 찾기 위해 해당 구간의 모든 원소를 확인한다.
배열에 원소가 n개 있다면 1회차에서는 n - 1번, 2회차에서는 n - 2번 비교하며 회차가 진행될수록 비교 횟수가 한 번씩 줄어든다.
따라서 전체 비교 횟수는 다음과 같다.

$$(n - 1) + (n - 2) + \cdots + 2 + 1 = \frac{n(n - 1)}{2} = \frac{n^2 - n}{2}$$

예를 들어 원소가 5개라면 4 + 3 + 2 + 1 = 10번 비교한다.

이 비교 횟수는 배열의 정렬 상태와 무관하다.
이미 정렬된 배열이라도 미정렬 구간의 최솟값을 확인하려면 매 회차 남은 원소를 끝까지 비교해야 하기 때문이다.
그러므로 최선, 평균, 최악의 경우 모두 시간 복잡도는 O(n²)이다.

비교와 달리 두 원소의 교환은 한 회차에 최대 한 번만 일어나며, 최솟값이 이미 올바른 자리에 있다면 교환은 일어나지 않는다.
그러나 교환 횟수와 관계없이 전체 비교 횟수는 변하지 않으므로 시간 복잡도에는 영향을 주지 않는다.

소스 코드

#include <stdio.h>

int main(void)
{
    int arr[] = { 7, 4, 9, 2, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < size - 1; i++)
    {
        int min_index = i;

        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }

        if (min_index != i)
        {
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
    }

    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]); // Result: 2 4 6 7 9
    }

    return 0;
}

구현 설명

바깥 반복문의 i는 0부터 시작하는 회차 인덱스로, 이번 회차에서 값을 확정할 위치와 같다.
원소 size개 중 size - 1개의 자리만 확정하면 되므로 바깥 반복문은 size - 1번 실행한다.

min_index는 현재까지 찾은 가장 작은 원소의 인덱스다.
회차가 시작되면 i 위치의 원소를 최솟값으로 가정하므로 min_index를 i로 초기화한다.

안쪽 반복문의 j는 최솟값과 비교할 원소의 인덱스다.
i 위치의 원소는 이미 최솟값으로 가정했고 i보다 앞에 있는 원소의 자리는 이전 회차에서 확정되었으므로 j는 i + 1부터 시작한다.
배열의 마지막 원소까지 확인해야 하므로 안쪽 반복문의 조건식은 j < size가 된다.
arr[j]가 현재 최솟값인 arr[min_index]보다 작으면 min_index를 j로 갱신한다.

안쪽 반복문이 끝나면 min_index에는 미정렬 구간에서 가장 작은 원소의 인덱스가 저장되어 있다.
min_index가 i와 다르면 최솟값이 올바른 자리에 없으므로 arr[i]와 arr[min_index]를 교환한다.
두 인덱스가 같으면 최솟값이 이미 올바른 자리에 있으므로 교환하지 않는다.