동작

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

복잡도

명제 A. 선택 정렬은 길이 N의 배열에 대해 번의 비교와 N 번의 교환을 수행한다. 1

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

  • 회의 비교를 한다.
  • 1 회의 교환을 한다.

그러므로

  • 회의 비교를 한다.
    • [[tilde-approximations]]{틸다 표기법}으로는 .
    • [[big-O-notation]]으로는 .
  • 회의 교환을 한다.

특징

  • 선택 정렬은 이미 정렬된 배열을 입력으로 받아도, 랜덤하게 나열된 배열을 입력으로 받아도 정렬에 걸리는 시간이 같다.
  • 교환 작업의 횟수가 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쪽.