선택 정렬

선택 정렬

선택 정렬 애니메이션
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$O(n^{2})$ 비교, $O(n)$ 교환
최선 시간복잡도	$O(n^{2})$ 비교, $O(n)$ 교환
평균 시간복잡도	$O(n^{2})$ 비교, $O(n)$ 교환
공간복잡도	$O(1)$ 예비

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

선택 정렬 애니메이션

예제

패스	테이블	최솟값
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

의사 코드

for i = 0 to n:
    a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    a[i]와 a[j]의 값을 서로 맞바꾼다.

복잡도

최선, 평균, 최악의 경우일 때에 선택 정렬에 소요되는 비교의 횟수를 $C$라고 했을 때, 이를 수식으로 나타내면 다음과 같다.

$C_{min}=C_{ave}=C_{max}=\sum _{i=1}^{N-1}{N-i}={\frac {N(N-1)}{2}}=O(n^{2})$

수식에서 $N$은 테이블(또는 리스트)의 자료 수를 나타내며, $C_{ave}$는 평균, $C_{max}$는 최대, $C_{min}$는 최소를 나타낸다.

다른 정렬 알고리즘과의 비교

버블 정렬(bubble sort) : 시간 복잡도 Θ ( n ² )인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다.

삽입 정렬(insertion sort) : 삽입 정렬은 k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점에서 유사하다. 하지만 선택 정렬은 k+1 번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입 정렬은 k+1 번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있다.

합병 정렬(merge sort) : 선택 정렬은 합병 정렬과 같은 분할 정복 알고리즘을 사용하지만 일반적으로 큰 배열보다 작은 배열(요소 10~20개 미만)에서 더 빠르다. 따라서 충분히 작은 하위 목록에만 삽입 정렬 혹은 선택 정렬을 이용해서 최적화하는 것이 좋다.

다양한 개선 방법

이중 선택 정렬: 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다.

탐색을 응용하여 개선: 한 번의 탐색 때 동일한 값이 있다면 함께 정렬하는 방법이다. 즉, 만약 최솟값을 찾았는데 그 값과 같은 값이 있다면 다음 번 탐색 때 최솟값으로 탐색될 것이기에 이 값도 탐색된 것으로 보고 미리 정렬한다. 같은 값이 많을수록 유용하게 된다.

소스 코드

Java

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

C

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

Objective Caml(OCaml)

let rec ssort = function
	| [] -> []
	| h::t -> (ssort (etcList (findMax h t) (h::t))) @ [(findMax h t)]
and findMax a = function
	| [] -> a
	| h::t -> if a>h then (findMax a t) else (findMax h t)
and etcList a = function
	| [] -> []
	| h::t -> if h=a then t else h :: (etcList a t);;

파이썬

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

참고 및 관련 문헌

• Ellis Horowitz, Sartaj Sahni, Dinesh Mehta: Fundamentals of Data structures in C++, Computer science press.

같이 보기

• 선택 알고리즘
• 도널드 커누스
• 로버트 세지윅