Sorting Problem

상위 문서: 알고리즘 설계와 분석

개요

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

알고리즘

Selection Sort

선택 정렬(Selection Sort) 알고리즘이란 남아 있는 정렬되지 않은 원소들 중에서 가장 작은 것을 반복적으로 찾아서 배열의 정렬된 부분의 끝에 두는 것이다. 이를 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]);
    }
}

위 알고리즘에서 바깥쪽 for 루프는 n번 돈다. 안쪽의 루프는 바깥 루프의 인덱스가 i일 때, n−(i+1)번 돈다. 이에 따라 if 문이 실행되는 정확한 횟수는 아래와 같다.

[math]\displaystyle{ 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]\displaystyle{ \therefore T(n) = (n-1) + (n-2) + (n-3) + \cdots + 2 + 1  }[/math]

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

Insertion Sort

삽입 정렬(Insertion Sort)은 배열의 첫 부분 부터 차근차근 정렬해가는 방식이다. 배열의 정렬되지 않은 부분에서 가장 작은 원소를 배열의 남은 부분의 첫 위치에 삽입하는 것을 반복하는 방식이다. 이를 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;
        }
    }
}

위의 코드의 시간 복잡도를 추론하기 위해서는 내부 while 루프가 얼마나 도는지를 알아야 한다. 최악의 경우에 대해서 고려한다면,