선택 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
선택 정렬 애니메이션

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

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

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

선택 정렬 애니메이션

예제[편집]

패스 테이블 최소값
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 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);;

참고 및 관련 문헌[편집]

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