선택 정렬

선택 정렬 애니메이션

선택 정렬(選擇整列, 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}$는 최소를 나타낸다.

소스 코드

Java

void selectionSort(int[] list) {
    int i, j, indexMin, temp;
 
    for (i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (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);;

참고 및 관련 문헌

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