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) = \sum^{n-1}_{i=0} i</math>
 <math>\therefore T(n) = (n-1) + (n-2) + (n-3) + \cdots + 2 + 1 </math>
따라서 최악의 경우(worst case) 해당 알고리즘의 시간 복잡도는 <math>\Theta(n^2)</math>이다. 하지만 이 방식은 조금 지루하고 까다로운 방식이다. 빅 오 표기법은 오직 최대 차항의 차수에만 신경을 쓰면 되기 때문에, 바깥쪽의 루프는 n번, 안쪽의 루프도 최대 n번 돌기 때문에, 선택 정렬(selection sort)은 최악의 경우 <math>n×n=O(n2)</math> 시간이 걸린다는 것을 어렵지 않게 추론할 수 있다. 이때 해당 알고리즘은 이미 정렬돼 있든(최선), 완전히 역순이든(최악) 상관없이, 비교 횟수는 동일하므로, <math>\Theta(n^2)</math>임을 추론할 수 있다. 

===Insertion Sort===
삽입 정렬(Insertion Sort)은 배열의 첫 부분 부터 차근차근 정렬해가는 방식이다. 배열의 정렬되지 않은 부분에서 가장 작은 원소를 배열의 남은 부분의 첫 위치에 삽입하는 것을 반복하는 방식이다. 이를 C 언어 코드로 표현하면 아래와 같다:
<syntaxhighlight lang="c">
void insertion_sort(item_type s[], int n) {
    for (i = 1; i < n; i++) {
        j = i;
        while ((j > 0) && (s[j] < s[j - 1])) {
            swap(&s[j], &s[j - 1]);
            j = j - 1;
        }
    }
}
</syntaxhighlight>
위의 코드의 시간 복잡도를 추론하기 위해서는 내부 while 루프가 얼마나 도는지를 알아야 한다. 최악의 경우에 대해서 고려한다면, 

==각주==