|
최선, 평균, 최악의 경우일 때에 선택 정렬에 소요되는 비교의 횟수를 <math>C</math>라고 했을 때, 이를 수식으로 나타내면 다음과 같다.
:<math>X_{min}=X_{ave}=X_{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개 미만)에서 더 빠릅니다. 따라서 충분히 작은 하위 목록에만 삽입 정렬 혹은 선택 정렬을 이용해서 최적화하는 것이 좋습니다.
== 소스 코드 ==
<source 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;
}
}
</source>
=== [[C (프로그래밍 언어)|C]] ===
=== [[Objective Caml|jective Caml]]([[OCaml |l]]) === ▼<source 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;
}
}
</source>
▲=== [[Objective Caml]]([[OCaml]]) ===
<source 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);;
</source>
=== [[파이썬]] ===
<source 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
</source>
== 참고 및 관련 문헌 ==
* Ellis Horowitz, Sartaj Sahni, Dinesh Mehta: Fundamentals of Data structures in C++, Computer science press.
{{정렬 알고리즘}}
{{토막글|컴퓨터 과학}}
| 