Sorting Problem 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] 

==개요==
해당 문제는 알고리즘의 기본이라고 할 수 있는 정렬 알고리즘에 대해 다룬다. 정렬 알고리즘은 입력으로는 n개의 수 <math>a_1, ..., a_n</math>으로 이루어진 수열이 주어지며, 이때 출력은 해당 수열을 재배열하여 <math> a'_1 \le a'_2 \le ... \le a'_n</math>이 되도록 하는 것이다.

==알고리즘==
===Selection Sort===
선택 정렬(Selection Sort) 알고리즘이란 남아 있는 정렬되지 않은 원소들 중에서 가장 작은 것을 반복적으로 찾아서 배열의 정렬된 부분의 끝에 두는 것이다. 이를 C언어 코드로 표현하면 아래와 같다.
<syntaxhighlight lang="c">
void selection_sort(item_type s[], int n) {
    int i, j;   /* counters */
    int min;    /* index of minimum */
    for (i = 0; i < n; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (s[j] < s[min]) {
                min = j;
            }
        }
        swap(&s[i], &s[min]);
    }
}
</syntaxhighlight>
위 알고리즘에서 바깥쪽 for 루프는 n번 돈다. 안쪽의 루프는 바깥 루프의 인덱스가 i일 때, n−(i+1)번 돈다. 이에 따라 if 문이 실행되는 정확한 횟수는 아래와 같다.
 <math>T(n) = \sum^{n-1}_{i=0} \sum^{n-1}_{j=i+1} 1 = \sum^{n-1}_{i=0} (n-i-1)</math>
 <math>\therefore T(n) = (n−1) + (n−2) + (n−3) + \cdots + 2 + 1 </math>

===Insertion Sort===
<syntaxhighlight lang="c">

</syntaxhighlight>

==각주==