선택 정렬(選擇整列, Selection Sort)은 컴퓨터 과학의 정렬 알고리즘 중 하나로, 제자리 정렬(in-place sort) 알고리즘에 해당한다. 주어진 리스트에서 최솟값(또는 최댓값)을 반복적으로 찾아 정렬되지 않은 부분의 맨 앞 요소와 교환하는 방식으로 동작한다.
기본 원리
선택 정렬의 동작 과정은 다음과 같이 요약된다.
- 주어진 리스트에서 최솟값을 찾는다.
- 그 값을 리스트의 맨 앞에 위치한 값과 교체한다. 이 과정을 패스(pass)라고 한다.
- 맨 처음 위치를 제외한 나머지 리스트에 대해 같은 방법을 반복한다.
이 과정을 n개의 요소에 대해 반복하면 전체 리스트가 오름차순으로 정렬된다.
시간 복잡도와 공간 복잡도
비교 연산이 상수 시간에 이루어진다고 가정할 때, n개의 리스트를 선택 정렬로 정렬하는 데 필요한 비교 횟수는 최선, 평균, 최악의 경우 모두 동일하게 다음과 같이 계산된다.
$$ C = \sum_{i=1}^{N-1} (N-i) = \frac{N(N-1)}{2} = O(n^2) $$
여기서 N은 리스트의 요소 수를 의미한다. 즉, 선택 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n²)이다.
교환 횟수는 최대 O(n)으로, 각 패스에서 한 번의 교환이 이루어지기 때문에 교환 측면에서는 비교적 효율적이다. 공간 복잡도는 추가 메모리 사용이 거의 없어 O(1)이다.
특징
선택 정렬은 알고리즘이 단순하고 구현이 쉬우며, 사용 가능한 메모리가 제한적인 환경에서 사용될 때 성능상 이점이 있다. 그러나 시간 복잡도가 O(n²)이므로 데이터의 규모가 큰 경우에는 효율성이 떨어진다.
선택 정렬은 동일한 값을 가진 요소들의 상대적 순서가 보장되지 않을 수 있는 불안정 정렬(unstable sort)의 특성을 지닌다.
다른 정렬 알고리즘과의 비교
- 버블 정렬: 시간 복잡도가 Θ(n²)인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수한 성능을 보인다.
- 삽입 정렬: 삽입 정렬과 유사한 점이 있으나, 선택 정렬은 k+1번째 요소를 찾기 위해 나머지 모든 요소를 탐색하는 반면, 삽입 정렬은 배치에 필요한 만큼의 요소만 탐색하므로 일반적으로 삽입 정렬이 더 효율적으로 실행된다.
- 합병 정렬: 선택 정렬은 합병 정렬과 같은 분할 정복 방식을 사용하지는 않으나, 작은 배열(요소 10~20개 미만)에서는 선택 정렬이 더 빠른 경우가 있다.
개선 방법
선택 정렬의 변형으로는 다음과 같은 방법이 제안되어 있다.
- 이중 선택 정렬: 한 번의 탐색에서 최솟값과 최댓값을 동시에 찾는 방식으로, 탐색 횟수를 절반으로 줄인다.
- 탐색 응용 개선: 한 번의 탐색에서 최솟값과 동일한 값을 가진 요소가 있다면 함께 정렬하는 방식으로, 중복 값이 많은 데이터에서 유용하다.
의사 코드
for i = 0 to n:
a[i]부터 a[n-1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
a[i]와 a[j]의 값을 서로 맞바꾼다.
선택 정렬은 컴퓨터 과학의 기초 정렬 알고리즘으로서 교육 과정에서 널리 다루어지며, 다양한 프로그래밍 언어로 구현된 예제가 존재한다.
