선택 정렬

위키백과 ― 우리 모두의 백과사전.

선택 정렬은 내부정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

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

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

[편집] 예제

다음의 테이블[9 1 6 8 4 3 2 0]이 주어질 때 선택 정렬을 해보면 다음과 같다.

패스	테이블	최소값
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 (int i = 0; i < n; i++) 
{
    examine a[i] to a[n - 1] and suppose the smallest integer is at a[j];
    // a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    interchange a[i] and a[j];
    // a[i]와 a[j]의 값을 서로 맞바꾼다.
}

[편집] 복잡도

최선, 평균, 최악의 경우일 때에 선택 정렬에 소요되는 비교의 횟수를 C라고 했을 때, 이를 수식으로 나타내면 다음과 같다. 수식에서 N은 테이블(또는 리스트)의 자료 수를 나타내며, ave는 평균, max는 최대, min는 최소를 나타낸다. $C_{min}=C_{ave}=C_{max}=\sum_{i=1}^{N-1}{N-i}=\frac{N(N-1)}{2}=O(n^2)$

[편집] 소스코드

[편집] Java example

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++ example

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 example

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.

분류: 정렬 알고리즘

See also ebooksgratis.com: no banners, no cookies, totally FREE.