단순 선택 정렬(straight selection sort)

• 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
• 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다.
  • 안정된 정렬이란 같은 값을 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다.
  • 안정되지 않은 알고리즘은 정렬 후에 같은 값의 요소의 순서가 바뀔 수도 있다.
• 시간 복잡도는 O(n^2)

단순 선택 정렬의 교환 과정

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택한다.
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

// 단순 선택 정렬
static void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;            // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        swap(a, i, min);        // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환
    }
}