선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

선택 정렬은 원리가 가장 간단한 정렬 알고리즘 중의 하나이다. 우선 배열 A[1..n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 이 방식을 n 번째 원소부터 2번째 원소까지 하게 되면 배열은 정렬되게 되는데, 이것이 바로 선택 정렬이다.

선택정렬의 수도코드는 다음과 같다.

selectionSort(A[], n) {

for  last  <- n 에서 2까지 반복 {

A[1..last] 중 가장 큰 수 A[k] 찾기

A[k] 와 A[last]의 값을 교환

}

}

선택정렬은 위치 변경 횟수를 줄임으로써, 버블 정렬을 일부 개선한 기법이다.

비교 횟수도 버블 정렬과 같고, 시간 복잡도 역시 O(n^2)이지만, 자리 이동 측면에서는 선택 정렬이 더 효율적이다.

- 최악 시간 복잡도 => O(n^2) 비교, O(n) 교환

- 최선 시간 복잡도 => O(n^2) 비교, O(n) 교환

- 평균 시간 복잡도 => O(n^2) 비교, O(n) 교환

- 공간 복잡도 => O(1)