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