선택 정렬

소개

선택 정렬(Selection sort)는 제자리 정렬 알고리즘의 하나로 가장 작은(혹은 가장 큰) 원소를 찾아서 교체하는 알고리즘입니다. 말 그대로 원소를 선택해서 정렬합니다.

정렬 과정

다음과 같이 다섯 개의 정수가 주어졌을 때, 오름 차순으로 정렬해보겠습니다.

+-----+-----+-----+-----+-----+
|  5  |  4  |  1  |  3  |  2  |
+-----+-----+-----+-----+-----+

우선 인덱스 0을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 1부터 원소 끝까지 순회하면서 가장 작은 원소를 찾습니다. 그리고 찾은 원소를 가장 처음 원소와 교체합니다.

+-----+-----+-----+-----+-----+
|  1  |  4  |  5  |  3  |  2  |
+-----+-----+-----+-----+-----+

가장 작은 원소가 처음 원소와 교체됐기 때문에 다음 단계부터는 인덱스 1을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 2부터 원소 끝까지 순회하면서 가장 작은 원소를 인덱스 1의 원소와 교체합니다.

+-----+-----+-----+-----+-----+
|  1  |  2  |  5  |  3  |  4  |
+-----+-----+-----+-----+-----+

이어서 동일한 방법으로 시작 위치를 한 칸씩 증가시키면서 가장 작은 원소와 교체해주면 됩니다.

+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  5  |  4  |
+-----+-----+-----+-----+-----+

+-----+-----+-----+-----+-----+
|  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;
  }
}

정리

선택 정렬과 거품 정렬은 언뜻 비슷해보입니다. 그러나 거품 정렬은 최악의 경우 인접한 모든 원소마다 자리 교환이 일어나지만, 선택 정렬은 비교만 거품 정렬과 동일하게 할 뿐 교환은 순회 당 한 번입니다. 이러한 이유로 선택 정렬이 거품 정렬 보다 항상 우수합니다.