선택 정렬 (Selection Sort)

동작
복잡도
특징
구현 예제
참고문헌
주석

동작

배열 안에서 가장 작은 항목을 찾는다.
가장 작은 항목을 첫 항목과 자리바꿈한다.
배열 안에서 두 번째로 작은 항목을 찾는다.
두 번째로 작은 항목을 두 번째 항목과 자리바꿈한다.
…

복잡도

명제 A. 선택 정렬은 길이 N의 배열에 대해 $\sim { N^2 \over 2 }$ 번의 비교와 N 번의 교환을 수행한다. ¹
알고리즘 [개정4판]. 2장. 247쪽. ↩

이 알고리즘은 각각의 항목에 대해 다음과 같은 일을 한다.

$N - 1 - i$ 회의 비교를 한다.
1 회의 교환을 한다.

그러므로

$(N - 1) + (N - 2) + . . . + 2 + 1 + 0 = \frac{N (N - 1)}{2}$ 회의 비교를 한다.
- 틸다 표기법으로는 $\sim { N^2 \over 2 }$ .
- 빅 오 표기법(Big O notation)으로는 $O(N^2)$ .
$N$ 회의 교환을 한다.

특징

선택 정렬은 이미 정렬된 배열을 입력으로 받아도, 랜덤하게 나열된 배열을 입력으로 받아도 정렬에 걸리는 시간이 같다.
교환 작업의 횟수가 N 번이다.
- 교환 횟수는 배열의 크기에 선형으로 비례( $O(N)$ )하며, 어지간한 정렬 알고리즘보다 작은 메모리 공간을 차지한다.

구현 예제

/**
 * 선택 정렬.
 * 길이 N인 배열에 대해 ~N^2 / 2 번의 비교와 N 번의 교환을 수행한다.
 */
public class SelectionSort {
  /**
   * 선택 정렬 알고리즘을 사용해 a를 오름차순으로 정렬한다.
   *
   * @param a 정렬 대상 배열
   */
  public static void sort(int[] a) {
    final int n = a.length;

    for (int i = 0; i < n; i++) {

      // 가장 작은 항목의 인덱스를 찾는다
      int min = i;
      for (int j = i + 1; j < n; j++) {
        if (a[j] < a[min]) {
          min = j;
        }
      }

      // 인덱스의 앞부분부터 가장 작은 항목으로 바꿔 나간다
      int temp = a[i];
      a[i] = a[min];
      a[min] = temp;
    }
  }
}

참고문헌

알고리즘 [개정4판] / 로버트 세지윅, 케빈 웨인 저/권오인 역 / 길벗 / 초판발행 2018년 12월 26일

주석

알고리즘 [개정4판]. 2장. 247쪽. ↩