선택 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
선택 정렬
선택 정렬 애니메이션
선택 정렬 애니메이션
분류 정렬 알고리즘
자료구조 배열
최선 시간복잡도 비교, 교환
평균 시간복잡도 비교, 교환
최악 시간복잡도 비교, 교환
공간복잡도 예비

선택 정렬(選擇整列, 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]의 값을 서로 맞바꾼다.

복잡도[편집]

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

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

소스 코드[편집]

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.