본문으로 이동

선택 정렬

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

선택 정렬
선택 정렬 애니메이션
분류정렬 알고리즘
자료 구조배열
최악 시간복잡도 비교, 교환
최선 시간복잡도 비교, 교환
평균 시간복잡도 비교, 교환
공간복잡도 예비

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

복잡도

[편집]

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

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

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

[편집]

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

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

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

다양한 개선 방법

[편집]

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

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

소스 코드

[편집]

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;
    }
}
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;
    }
}
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.
  1. 박정식 (2021/06). “탐색을 응용한 선택 정렬의 개선 방법 제안”. 2021년 8월 7일에 확인함. 

같이 보기

[편집]