Sorting Problem 문서 원본 보기

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

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

==Importance of Sorting==
정렬은 매우 단순한 작업처럼 보이지만, 이는 실제로 매우 중요한 주제이다. 그 이유는 컴퓨터가 많은 시간을 정렬에 사용하기 때문이다. 역사적으로 컴퓨터는 약 25%의 시간을 정렬 알고리즘을 수행하는데 사용한다. 이러한 이유로, 정렬은 가장 잘 연구된 문제 중 하나이다. 

컴퓨터 과학에서 정렬은 수많은 알고리즘이 연구된 주제이며, 따라서 분할 정복(divide-and-conquer), 무작위화(randomized algorithms), 시간 복잡도의 하한(lower bounds) 등과 같은 많은 개념들을 정렬 알고리즘을 공부함을 통해 배울 수 있다. 

또한 데이터가 정렬되어 있으면 탐색, 중복 제거, 순위 계산, 범위 질의(range query) 등이 훨씬 쉽게 해결된다. 이때 단순한 
O(n<sup>2</sup>) 정렬 알고리즘은 데이터가 커지면 사용할 수 없다. 따라서 O(n log(n)) 알고리즘을 사용해야 대규모 데이터 처리를 할 수 있다. 이는 본질적으로 시간 복잡도 측면에서 O(n<sup>2</sup>)와 O(n log(n))이 매우 큰 차이를 보이기 때문이다. Figure 1은 입력의 크기가 100,000일 때 걸리는 시간이 약 1500배나 난다는 것을 보여준다. 

==Pragmatics of Sorting==
===Comparison Functions===
어떤 순열을 정렬하고자 할때, 어떤 기준으로 비교하는지는 중요한 문제이다. 예를 들어 문자열 정렬은 Alphabetizing을 기준으로 이루어 진다. 또한 그 중에서도 텍스트 문자열을 정렬할 때는 단순히 글자 순서뿐 아니라 대소문자, 구두점, 띄어쓰기 등 세부 규칙이 필요하다. 예를 들어 "Big"과 "big"을 동일시 할지 말지, 혹은 "A-B"가 "A B"보다 앞에 있을지 말지이다. 즉, 정렬이 세부적으로 어떤 기준으로 정렬할 지는 두 원소를 비교하는 함수(comparison function)에 달려 있다. 이러한 비교함수는 름차순/내림차순 여부, 대소문자 무시 여부, 사전식 정렬 여부 등을 결정한다.

===Equal Elements===
동일한 키를 가지는 원소들을 다룰 때에는 문제가 발생할 수 있다. 정렬 과정에서 같은 값을 가지는 원소들은 정렬 후 모두 같은 위치 근처에 위치한다. 하지만 이들의 상대적인 위치가 중요한 경우가 존재한다. 예를 들어, 한 학교 내에 있는 학생들의 성명을 성씨를 기준으로 정렬하는 경우, 성은 같더라도 이름이 다른 경우가 존재하기 때문이다. 따라서 주 키(primary key)로 구분이 안 되는 경우, 2차 키(secondary key)를 이용하여 정렬을 세밀화할 수 있다. 이는 비교 함수에서 처리되어야 한다. 이떄 퀵정렬 같은 알고리즘은 동일 원소가 많을 때 성능 저하가 생길 수 있다. 따라서 동일 원소가 많으면 특별한 처리가 필요하다.

===Library Functions===
우리가 프로그램을 구현할 때 정렬 기능을 이용해야 한다면, 프로그래밍 언어가 제공하는 표준 정렬 함수를 사용하는 것이 권장된다. 거의 모든 현대 프로그래밍 언어는 내장 정렬 함수를 제공한다. 이는 직접 구현하는 것보다 빠르고 안전하며, 최적화도 잘 되어 있다. 예를 들어 C언어의 qsort()는 아래와 같은 함수이다.
<syntaxhighlight lang="c">
void qsort(void *base, size_t nel, size_t width, 
           int (*compare)(const void *, const void *));
</syntaxhighlight>
해당 함수에서 base는 배열의 시작 주소, nel은 원소의 개수, width는 각 원소의 크기, compare는 두 원소를 비교하는 함수 포인터이다.
<syntaxhighlight lang="c">
int intcompare(int *i, int *j) {
    if (*i > *j) return 1;
    if (*i < *j) return -1;
    return 0;
}

</syntaxhighlight>
위는 정수 배열을 오름차순 정렬할 때 사용하는 비교 함수입니다.

==알고리즘==
===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\times n=O(n^2)</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])) { //s[j]가 올바른 위치에 있으면 while문 종료
            swap(&s[j], &s[j - 1]); //그렇지 않으면 스왑
            j = j - 1;
        }
    }
}
</syntaxhighlight>
위의 코드의 시간 복잡도를 추론하기 위해서는 내부 while 루프가 얼마나 도는지를 알아야 한다. 최악의 경우에 대해서 고려한다면, 내부의 while 문은 항상 i번 돈다고 할 수 있다. 이때 i < n이고 바깥 while문은 n번 도므로, 삽입 정렬의 시간 복잡도는 <math>O(n^2)</math>이다.

==각주==