동작

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

복잡도

명제 A. 선택 정렬은 길이 N의 배열에 대해 \(\sim { N^2 \over 2 }\) 번의 비교와 N 번의 교환을 수행한다. 1

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

  • \(N - 1 - i\) 회의 비교를 한다.
  • 1 회의 교환을 한다.

그러므로

  • \((N-1) + (N-2) + ... + 2 + 1 + 0 = { N(N-1) \over 2 }\) 회의 비교를 한다.
    • [[/tilde-approximations]]{틸다 표기법}으로는 \(\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일

주석

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