[정렬] 선택 정렬(Selection Sort)

- 선택 정렬의 원리는 입력 원소들 중에서 최대 원소를 선택한다.

- 이 최대 원소를 제외한 나머지 입력 원소들 중 최대 원소를 선택한다.

- 이러한 작업을 반복한다.

이처럼 최대 원소를 찾아 가장 마지막 원소와 교환한다.

 

다음은 선택 정렬 알고리즘이다.

selectionSort(A[], n) {
    for last ← downto 2 { // 1
        A[1...last] 중 가장 큰 수 A[k]를 찾는다 // 2
        A[K] ↔ A[last]; A[k]와 A[last]값을 교환 // 3
    }
}

- 1의 for 루프는 n-1번 반복한다.

- 2에서 가장 큰 수를 찾기 위한 비교 횟수 = 첫 번째 반복 시 n-1, 두 번째 반복 시 n-2,...,

  n-2번째 반복시 2, n-1번째 반복시 1

  => 이 비교하는 횟수가 전체 수행 시간을 좌우함

- 3의 교환은 상수 시간 작업

 

따라서,

T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

시간 복잡도는 O(n^2)가 된다.