선택 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{알고리즘 정보
|분류 = [[정렬 알고리즘]]
|그림 = Selection sort animation.gif
|그림설명 = 선택 정렬 애니메이션
|자료구조 = [[배열]]
|최선 = <math>O(n^2)</math> 비교, <math>O(n)</math> 교환
|평균 = <math>O(n^2)</math> 비교, <math>O(n)</math> 교환
|최악 = <math>O(n^2)</math> 비교, <math>O(n)</math> 교환
|공간복잡도 =<math>O(1)</math> 예비
}}

'''선택 정렬'''(選擇整列, selection sort)은 [[정렬 알고리즘#제자리 정렬|제자리 정렬]] 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
# 주어진 리스트 중에 최소값을 찾는다.
# 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
# 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 [[대문자 O 표기법|Θ]](n<sup>2</sup>) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
[[파일:Selection-Sort-Animation.gif|오른쪽|프레임|선택 정렬 애니메이션]]

== 예제 ==
{| class="wikitable"
|-
! 패스 !! 테이블 !! 최솟값
|-
| 0 ||style="color:#ff6666" |['''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
|}

== 의사 코드 ==
<pre>
for i = 0 to n:
    a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    a[i]와 a[j]의 값을 서로 맞바꾼다.
</pre>

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

== 다른 정렬 알고리즘과의 비교 ==
버블 정렬(bubble sort) : 시간 복잡도 Θ ( ''n'' <sup>2</sup> )인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다.

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

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

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

탐색을 응용하여 개선: 한 번의 탐색 때 동일한 값이 있다면 함께 정렬하는 방법이다. 즉, 만약 최솟값을 찾았는데 그 값과 같은 값이 있다면 다음 번 탐색 때 최솟값으로 탐색될 것이기에 이 값도 탐색된 것으로 보고 미리 정렬한다. 같은 값이 많을수록 유용하게 된다.<ref>{{웹 인용|url=https://www.dbpia.co.kr/Journal/articleDetail?nodeId=NODE10583574|제목=탐색을 응용한 선택 정렬의 개선 방법 제안|성=박정식|날짜=2021/06|언어=ko|확인날짜=2021-08-07}}</ref>

== 소스 코드 ==
=== Java ===
<syntaxhighlight lang="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;
    }
}
</syntaxhighlight>

=== [[C (프로그래밍 언어)|C]] ===
<syntaxhighlight lang="cpp">
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;
    }
}
</syntaxhighlight>

=== [[Objective Caml]]([[OCaml]]) ===
<syntaxhighlight lang="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);;
</syntaxhighlight>

=== [[파이썬]] ===
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 참고 및 관련 문헌 ==
* Ellis Horowitz, Sartaj Sahni, Dinesh Mehta: Fundamentals of Data structures in C++, Computer science press.
{{각주}}

== 같이 보기 ==
* [[선택 알고리즘]]
* [[도널드 커누스]]
* [[로버트 세지윅]]

{{정렬 알고리즘}}
{{토막글|컴퓨터 과학}}

[[분류:정렬 알고리즘]]
[[분류:비교 정렬]]