Sorting Problem

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

개요

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

Importance of Sorting

Figure 1. Difference between O(n²) and O(n log(n))

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

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

또한 데이터가 정렬되어 있으면 탐색, 중복 제거, 순위 계산, 범위 질의(range query) 등이 훨씬 쉽게 해결된다. 이때 단순한 O(n²) 정렬 알고리즘은 데이터가 커지면 사용할 수 없다. 따라서 O(n log(n)) 알고리즘을 사용해야 대규모 데이터 처리를 할 수 있다. 이는 본질적으로 시간 복잡도 측면에서 O(n²)와 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()는 아래와 같은 함수이다.

void qsort(void *base, size_t nel, size_t width, 
           int (*compare)(const void *, const void *));

해당 함수에서 base는 배열의 시작 주소, nel은 원소의 개수, width는 각 원소의 크기, compare는 두 원소를 비교하는 함수 포인터이다.

int intcompare(int *i, int *j) {
    if (*i > *j) return 1;
    if (*i < *j) return -1;
    return 0;
}

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

Application of Sorting

정렬 문제가 수많은 사람들에 의해서 연구되고, 컴퓨터가 연산 시간의 많은 부분을 정렬에 할애하는 것은 정렬이 매우 많은 활용도를 가지기 때문이다. 해당 문단에서는 정렬이 응용이 되는 중요한 몇 가지 방식에 대해 설명한다.

Searching

정렬의 가장 대표적인 응용은 이진 탐색(Binary Search)이다. 이진 탐색은 정렬된 배열에서 어떤 원소가 있는지 검사할 때, O(log n) 시간에 가능하게 한다. 데이터가 정렬되어 있지 않으면 O(n)의 시간 복잡도를 가지는 선형 탐색밖에 못 하므로, 정렬 후 탐색하는 것이 훨씬 효율적이다. 따라서 "탐색 전처리(Search preprocessing)”은 정렬의 가장 중요한 응용 중 하나이다.

Closest Pair

Closest Pair 문제는 n개의 숫자가 주어졌을 때, 서로 가장 가까운 두 수를 찾는 것이다. 정렬하지 않은 경우, O(n²)의 시간 복잡도 동안 모든 쌍을 비교해야 한다. 이때 가장 가까운 쌍은 정렬된 배열에서 인접한 두 원소 중에 반드시 존재한다. 이러한 사실을 이용하면, Closest Pair 문제는 전체를 정렬한 뒤 O(n)의 시간 복잡도 동안 한 번만 선형 스캔하면 해결된다. 따라서 Closest Pair 문제의 시간 복잡도는 아래와 같이 계산 된다:

$O(nlog(n))$(정렬) + $O(n)$(선형 검사) = $O(nlog(n))$

Element Uniqueness

Element Uniqueness 문제는 n개의 원소가 주어졌을 때, 모두 다른 값인지 아니면 중복된 값이 있는지 확인하는 문제이다. 배열을 정렬하면, 동일한 값들은 반드시 연속해서 나타나므로, 따라서 정렬 후 선형 스캔을 하면서 인접한 원소가 같은지만 확인하면 된다. 사실상 사실상 “Closest Pair” 문제의 특수한 경우이다.

Mode

최빈값(Mode) 문제는 n개의 아이템 중 가장 많이 등장하는 원소를 찾는 문제이다. 배열을 정렬하면 동일한 값들이 연속해서 나타난다. 이에 따라 해당 문제를 해결하기 위해서는, 선형 스캔을 하며 “같은 값이 몇 번 연속하는지(run length)”를 세어 최댓값을 찾으면 된다. 즉, 인접 구간들의 길이를 비교하면 최빈값을 알 수 있다.

이때 어떤 원소 k가 몇 번 나타나는지 확인하려면, O(log(n))의 이진 탐색으로 k−ϵ과 k+ϵ의 위치를 찾은 뒤, 그 구간 길이를 계산할 수 있다. 어찌 되었건 간에, 시간 복잡도는

$O(nlog(n))$(정렬) + $O(n)$(스캔) = $O(nlog(n))$

Median and Selection

Selection 문제는 집합에서 k번째로 큰 원소를 찾는 것이다. 이때 중간값(median)은 k를 n/2로 설정하여 구할 수 있다. 해당 문제도 정렬을 활용하면 간단하다. 배열을 정렬하면, k번째 원소를 한 번의 인덱싱으로 O(1)에 찾을 수 있기 때문이다. 따라서 해당 방법의 시간 복잡도는 O(n log(n))이다. 실제로는 "Median of Medians" 알고리즘 같은 특별한 방법으로 O(n)에 중간값을 구할 수 있지만, 아이디어는 여전히 "부분 정렬(partial sorting)"과 관련이 있다.

Finding Convex Hulls

Figure 2. Finding Convex Hull

Finding Convex Hulls 문제는 2차원 평면 위에 n개의 점이 주어졌을 때, 이 모든 점을 내부 혹은 껍질(hull)에 포함하는 가장 작은 볼록 다각형(convex polygon)을 찾는 문제이다. 직관적으로는 Figure 2와 같이 볼록 껍질을 찾는다는 것은 고무 밴드를 점들을 둘러싸듯이 잡아당겼을 때 생기는 외곽선을 찾는 것과 같다. 이는 컴퓨터 기하학(Computational Geometry)의 기본 문제 중 하나이며, 더 복잡한 알고리즘(최근접 점 문제, Voronoi diagram 등)의 기본 원형이다. 이를 해결하기 위해서는 아래와 같은 방법을 채택할 수 있다:

1. 점들을 x좌표 기준으로 정렬한다.
2. 왼쪽에서 오른쪽으로 점들을 추가하며 현재 껍질(hull)을 갱신한다.
3. 이때 오른쪽 끝 점은 항상 껍질의 일부이므로, 순차적으로 추가하며 안쪽에 들어가는 점들을 제거한다.

해당 알고리즘에서 정렬의 역할은 점들을 미리 정렬하여 매번 모든 점이 껍질 안에 있는지 검사할 필요가 없도록 하는 것이다. 또한 새로운 점을 추가할 때 껍질에 영향을 주는지 효율적으로 판정할 수 있다. 따라서 정렬 후, 선형 시간에 껍질을 구축할 수 있으므로 해당 알고리즘의 시간 복잡도는 O(n log(n))이다.

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 문이 실행되는 정확한 횟수는 아래와 같다.

$T(n)=\sum _{i=0}^{n-1}\sum _{j=i+1}^{n-1}1=\sum _{i=0}^{n-1}(n-i-1)=\sum _{i=0}^{n-1}i$
$\therefore T(n)=(n-1)+(n-2)+(n-3)+\cdots +2+1$

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

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])) { //s[j]가 올바른 위치에 있으면 while문 종료
            swap(&s[j], &s[j - 1]); //그렇지 않으면 스왑
            j = j - 1;
        }
    }
}

위의 코드의 시간 복잡도를 추론하기 위해서는 내부 while 루프가 얼마나 도는지를 알아야 한다. 최악의 경우에 대해서 고려한다면, 내부의 while 문은 항상 i번 돈다고 할 수 있다. 이때 i < n이고 바깥 while문은 n번 도므로, 삽입 정렬의 시간 복잡도는 $O(n^2)$이다.

Heap Sort

Selection sort 알고리즘은 더욱 효율적인 데이터 구조를 사용하여 개선할 수 있다. 먼저, selection sort는 아래와 같은 흐름을 가진다:

• for i = 1 to n : 배열의 크기 n에 대해, i번째 위치에 들어갈 원소를 선택하는 과정을 반복한다.
  1. A 단계: 남아 있는 원소들 중에서 가장 작은 값을 찾는다. 남아 있는 원소의 개수는 n - i + 1이다.
  2. B 단계: 찾은 최소값을 배열에서 꺼내어 앞으로(즉, i번째 자리)에 둔다.

이때 A, B 단계의 시간 복잡도를 각각 T(A), T(B)라고 하면, 전체 알고리즘의 시간 복잡도는 O(n(T(A)+T(B)))이다. 이때 우리는 시간 복잡도 T(A) = O(n²)를 개선할 수 있다. 그 방법은 Heap과 같은 자료구조를 사용하여, 최소(최대) 원소에 대한 접근의 시간 복잡도를 O(n)이 아닌 O(log(n))이 걸리도록 하는 것이다. 이는 아래와 같은 구조를 가지는 알고리즘이다:

1. Heapify로 배열을 힙으로 만든 뒤, → O(n)
2. extract_min(또는 extract_max)을 반복해서 정렬한다. → O(n log(n))

void heapsort_(item_type s[], int n) {
    int i;
    priority_queue q;
    make_heap(&q, s, n);          // 배열을 힙으로 변환
    for (i = 0; i < n; i++) {
        s[i] = extract_min(&q);   // 매번 최소값 꺼내어 배열에 저장
    }
}

Mergesort

Mergesort는 재귀적인 알고리즘으로, 큰 문제를 작은 문제로 나누어 해결하는 방식을 취한다. 이는 배열을 두 그룹으로 나눈 뒤, 각각을 재귀적으로 정렬하고, 마지막에 두 정렬된 리스트를 합쳐서 최종적으로 정렬된 리스트를 얻는 방법이다. 이는 “Divide and Conquer(분할 정복)”이라는 알고리즘 개념의 전형적인 예시이다. 아래는 mergesort를 구현한 코드이다:

// 인자: s는 배열, low와 high는 정렬 구간의 시작과 끝 인덱스
void mergesort_(item_type s[], int low, int high) {
    int middle;
    if (low < high) {
        middle = (low + high) / 2; // 배열을 두 구간으로 나눔
        // 왼쪽 구간(low ~ middle)과 오른쪽 구간(middle+1 ~ high)을 재귀적으로 정렬
        mergesort_(s, low, middle); 
        mergesort_(s, middle + 1, high);
        merge(s, low, middle, high); //merge() 함수로 두 구간을 합병
    }
}

Mergesort의 핵심적인 성능은 두 개의 정렬된 리스트를 얼마나 효율적으로 합치는가에 달려 있다. 이때 합치는 과정은, 가장 작은 원소를 두 리스트의 맨 앞에서 비교해 하나씩 빼내고, 그 과정을 반복하는 것이다. 예를 들어, 두 리스트 A = {5,7,12,19}, B = {4,6,13,15}를 합칠 경우:

1. 먼저 4 vs 5 비교 → 4 선택
2. 5 vs 6 비교 → 5 선택
3. 6 vs 7 비교 → 6 선택
4. 이런 식으로 n-1번 비교, 즉 O(n) 시간에 합칠 수 있다.

이를 구현하기 위해서 코드로 나타내면 아래와 같다:

void merge(item_type s[], int low, int middle, int high) {
    int i;
    queue buffer1, buffer2;
    init_queue(&buffer1);
    init_queue(&buffer2);

    // 왼쪽, 오른쪽 구간의 데이터를 각각 큐에 저장
    for (i = low; i <= middle; i++) enqueue(&buffer1, s[i]);
    for (i = middle + 1; i <= high; i++) enqueue(&buffer2, s[i]);

    i = low;
    // 두 큐가 비어있지 않은 동안 앞 원소를 비교
    while (!(empty_queue(&buffer1)) || empty_queue(&buffer2)) {
        if (headq(&buffer1) <= headq(&buffer2))
            s[i++] = dequeue(&buffer1);
        else
            s[i++] = dequeue(&buffer2);
    }

    // 남은 원소들 처리
    while (!empty_queue(&buffer1)) s[i++] = dequeue(&buffer1);
    while (!empty_queue(&buffer2)) s[i++] = dequeue(&buffer2);
}

Figure 3. Mergesort Time Complexity.png

앞서 설명했듯이, 각 단계에서 합병(merge) 과정은 O(n) 시간이 걸린다. 이때 분할 작업은 주어진 배열을 log₂(n) 단계로 나누기 때문에 전체 시간 복잡도는 O(n log(n))의 시간복잡도이다. 이는 figure 3를 참고하여 더욱 쉽게 이해할 수 있다.

Divide and Conquer

Mergesort는 대표적인 devide and conquer 알고리즘인데, 이는 큰 문제를 작은 문제들로 나누어서 해결하고, 그 결과를 이용하여 큰 문제도 푸는 알고리즘이다. 이 절차는 아래와 같다:

1. Divide: 문제를 두 개의 작은 문제로 나눔.
2. Conquer: 각 부분 문제를 재귀적으로 해결.
3. Combine: 두 해를 합쳐서 전체 문제의 해를 구함.

Mergesort에서 정렬 문제를 풀기 위해서 필요한 시간을 T(n)이라고 하고, 크기 n 문제를 반으로 쪼갠 뒤 왼쪽 절반과 오른쪽 절반을 각각 정렬하는 데 걸리는 시간을 2T(n/2)라고 하자. 마지막으로 두 개의 정렬된 리스트를 병합(merge)하는 과정에서 걸리는 시간을 $\mathrm{\Theta }$(n)이라고 하면, 아래와 같은 점화식을 도출할 수 있다.

$T(n)=2T(n/2)+\mathrm{\Theta }(n)=\mathrm{\Theta }(nlog(n))$

이를 일반화 하면 아래와 같다:

$T(n)=a\cdot T(n/b)+f(n)$

위에서 a는 분할할 때 문제의 개수, n/b는 분할된 각 문제의 크기, f(n)은 부분 문제의 해를 합치는데 걸리는 비용을 의미한다. 일반화한 이 식을 통해 T(n)의 점근적인 시간 복잡도를 구하는 방법이 있는데, 이를 마스터 정리라고 한다. 이는 아래와 같다:

• Case 1: $f(n)=O(n^{lo{g}_{b}a-ϵ}),$ for some $ϵ>0$
  • 즉, 합치는 비용이 부분 문제 비용보다 작다. 이 경우, $T(n)=\mathrm{\Theta }(n^{lo{g}_{b}a})$
• Case 2: $f(n)=\mathrm{\Theta }(n^{lo{g}_{b}a}),$
  • 즉, 합치는 비용이 부분 문제 비용과 비슷하다. 이 경우, $T(n)=\mathrm{\Theta }(n^{lo{g}_{b}a}\cdot log(n))$
• Case 3: $f(n)=\mathrm{\Omega }(n^{lo{g}_{b}a+ϵ}),$ for some $ϵ>0$
  • 즉, 합치는 비용이 부분 문제 비용보다 크다. 이 경우, $T(n)=\mathrm{\Theta }(f(n))$
  • 단, 정규성 조건이 필요하다: $a\cdot f(n/b)\le c\cdot f(n)$ for some $c<1$

즉, 이는 올바른 devide conquer 알고리즘의 사용을 위해서는 구현한 알고리즘의 병합 비용이 부분 문제 해결 비용을 압도하지 않아야 한다는 것을 의미한다.

External Sorting

많은 정렬 알고리즘(QuickSort, HeapSort 등)은 모든 데이터를 메인 메모리(RAM)에 올려놓고 정렬한다고 가정한다. 하지만 실제 대규모 데이터는 수십 GB ~ TB 단위이기 때문에, 메모리에 전부 저장한 채로 알고리즘을 실행할 수 없다. 이 경우, 디스크(HDD/SSD)에 저장된 상태에서 정렬해야 하는데, 디스크 접근 속도는 RAM보다 수천~수만 배 느리다. 따라서 랜덤 액세스(Random Access) 방식보다는 순차 액세스(Sequential Access) 방식이 훨씬 빠르다.

랜덤 액세스란 저장 장치의 어느 위치든 “임의로” 바로 접근하는 방식이다. 예를 들면, 어떤 파일이나 데이터의 2004번째 데이터에 직접 바로 접근하는 것이다. 메모리(RAM)는 진짜 랜덤 액세스를 수행할 수 있지만, 디스크(HDD/SSD)에서는 해당 데이터의 위치를 찾기 위해서 물리적으로 탐색(Seek)하는 과정이 필요하다. 반면, 순차 액세스란 데이터를 “앞에서부터 차례차례” 읽거나 쓰는 방식이다. 이때 RAM에서는 랜덤과 순차 차이가 거의 없지만, 디스크에서는 둘 사이에 매우 큰 차이가 발생한다.

Mergesort가 디스크를 사용하는 외부 정렬에서 효율적인 이유는 순차 액세스 기반으로 작동하기 때문이다. 각 run 파일을 “앞에서부터 쭉” 읽고, 결과를 “앞에서부터 쭉” 쓰면 된다. 이는 디스크에 불필요한 탐색 절차를 요구하지 않는다. 반대로 QuickSort 같은 알고리즘은 중간 위치를 계속 참조해야 해서 랜덤 액세스 패턴이 많다.

Quicksort

Quicksort는 내부 정렬(internal sorting) 알고리즘 중 가장 빠른 알고리즘으로 알려져 있다. Quicksort의 핵심 아이디어는 분할(Partitioning)인데, 이는 하나의 원소(pivot)를 기준으로, pivot보다 작은 값들은 왼쪽에, pivot보다 큰 값들은 오른쪽에 두도록 배열을 나누는 것이다. 예를 들어 pivot = 10일 때,

• Before: 17, 12, 6, 19, 23, 8, 5, 10
• After: 6, 8, 5, 10, 23, 19, 12, 17

이때 중요한 것은 pivot은 한 번 자리를 잡으면 최종 정렬된 배열에서의 위치가 확정된다는 것이다. 예를 들어, 위의 after에서의 10의 위치는 정렬이 완료된 후에도 바뀌지 않는다. 즉, 한번 고정된 pivot의 위치는 더 이상 움직일 필요가 없다. 또한 분할 후에는 pivot 기준으로 왼쪽에는 항상 pivot보다 작은 값들만, 오른쪽에는 큰 값들만 존재한다. 따라서, 왼쪽 부분 배열과 오른쪽 부분 배열만 각각 독립적으로 정렬하면 전체 배열이 정렬된다.

따라서 중요한 것은 어떻게 분할을 수행하는지이다. 배열은 pivot 기준으로 한 번 선형 스캔(linear scan) 하면서 분할된다. 분할의 목적은 배열을 pivot 값 기준으로 두 그룹으로 나누는 것이다:

• pivot의 왼쪽: pivot보다 작은 값들
• pivot의 오른쪽: pivot보다 큰 값들
• pivot: 둘 사이에 정확히 위치를 확정

이 과정에서 분할 과정에서는 배열을 pivot 기준으로 한 번 선형 스캔(linear scan) 하면서, 아래의 세 가지 영역을 유지한다:

• < pivot (왼쪽 경계): 이미 처리된 값 중 pivot보다 작은 값
• > pivot (오른쪽 경계): pivot보다 큰 값 (아직 다 정리되진 않았지만 위치상 오른쪽으로 보냄)
• Unexplored (미탐색 영역): 아직 검사하지 않은 원소

이러한 quicksort는 아래와 같은 코드를 통해 구현된다:

void quicksort(item_type s[], int l, int h) {
    int p;   // partition index
    if ((h - l) > 0) { //배열 크기가 1 이하이면 재귀 종료
        p = partition(s, l, h); 
        quicksort(s, l, p - 1);
        quicksort(s, p + 1, h);
    }
}

위에서 partition() 함수는 pivot 기준으로 배열을 두 부분으로 나누고, pivot 위치를 반환한다. 이후 pivot 왼쪽 구간과 오른쪽 구간을 각각 재귀적으로 정렬하여 전체 배열을 정렬한다. 이때 partition() 함수는 아래와 같이 구현된다:

int partition(item_type s[], int l, int h) {
    int i, p, firsthigh;
    p = h;  // 마지막 원소를 pivot으로 선택
    firsthigh = l; // pivot보다 크거나 같은(high) 값들이 시작되는 위치.
    // 배열을 처음부터 끝까지 스캔하면서 pivot보다 작은 값들을 앞으로 몰아넣음.
    for (i = l; i < h; i++) { 
        if (s[i] < s[p]) {
            swap(&s[i], &s[firsthigh]);
            firsthigh++;
        }
    }
    swap(&s[p], &s[firsthigh]); // pivot을 올바른 위치에 두기
    return firsthigh;
}

Time Complexity Analysis

Figure 4. Best Case for Quicksort

Quicksort는 입력으로 받아들인 배열에 따라 그 시간 복잡도가 달라진다. 예를 들어, quicksort에 대한 최상의 경우는 pivot이 배열을 항상 정확히 절반으로 나눌 때이다. 이는 figure 4에 나타나 있다. 각 단계에서 배열이 2등분되면, 각 단계에서 partition의 비용이 O(n)이고, 분할 깊이는 log₂n이므로 최종 시간 복잡도는 O(n log(n))이다.

Figure 5. Worst Case for Quicksort

반면, quicksort에서 최악의 경우는 pivot이 배열을 극단적으로 한쪽으로만 쏠리게 분할할 때이다. 예를 들면, pivot이 항상 최댓값/최솟값으로 선택되는 경우이다. 분할 깊이는 n이므로 최종 시간 복잡도는 O(n²)이다. 이는 figure 5에 나타나있다.

하지만, 평균적으로는 quicksort라는 이름처럼 매우 빠르다. pivot이 항상 극단적이지 않고 “적당히” 중간 근처에서 분할한다면, 기대 시간 복잡도는 O(n log(n))이다.

시간 복잡도만 분석할 때에는, quicksort가 heapsort와 같은 다른 O(n log(n))의 시간 복잡도를 가지는 정렬 알고리즘보다 더욱 빠르다고 보기에는 어렵다. 하지만 실전에서는 quicksort가 보통 2~3배 더 빠르다. 이는 아래와 같은 이유를 가진다:

1. quicksort의 내부 루프 연산이 훨씬 단순하다.
2. 메모리 접근 패턴이 연속적이라 캐시 친화적이다.

따라서 실제 구현에서 상수 계수가 작아서 더욱 빠른 속도를 자랑한다.

Improving Quicksort

위에서 살펴보았듯이, 기본적인 quicksort는 데이터가 이미 정렬되거나 특정 패턴을 만족하면 O(n²)의 시간복잡도를 가진다. 이 경우 적대적인 상황(“worst enemy”)에서 실행해야 한다면, 적은 항상 최악 입력을 줄 수 있다. 하지만 pivot을 무작위로 선택하면 이야기가 달라진다. 이렇게 무작위로 pivot 값을 정하는 quicksort를 randomized quicksort라고 한다. Randomized quicksort의 장점은 어떤 입력이 들어오든 항상 같은 확률로 좋은 pivot을 뽑을 수 있다는 것이다. 이는 일반적인 quicksort와는 아래와 같이 다르다:

• 일반 quicksort: "무작위 입력일 때 기대 성능은 O(n log(n))"
• Randomized quicksort: "임의의 입력일 때 기대 성능은 O(n log(n))"

즉, 입력 데이터 분포에 기대지 않고, 알고리즘 자체가 랜덤성을 내장하기 때문에 더욱 강한 성능을 보장한다.

이와 같이 pivot을 선택하는, 적어도 기본적인 quicksort보다는 더욱 좋은 방식이 존재한다. 이는 아래와 같다:

1. 중간 원소 사용: 항상 가운데 원소를 pivot으로 선택한다. 이미 정렬된 경우에 대해 유효하다.
2. 무작위 원소 사용: 배열에서 무작위 원소를 pivot으로 선택한다.
3. Median-of-Three: 첫 번째, 마지막, 중간 원소 중 중간값을 pivot으로 선택한다.

다만, 어떤 방법을 써도 최악의 경우는 여전히 O(n²)이지만, 발생 확률이 매우 낮아진다.

Linear Sorting Approach

위에서 다룬 알고리즘들은 비교 기반 정렬(comparison-based sorting)으로, 시간 복잡도는 아무리 효율이 좋은 알고리즘이더라도 O(n log(n))에 그친다. 이는 우연이 아니라 비교 기반 정렬의 근본적인 한계에서 기인한 문제이다.

Figure 6. Decision Tree

Figure 6는 3개의 원소 a1, a2, a3를 정렬하는 과정을 결정 트리로 표현한 것이다. 결정 트리(Decision Tree)는 특정 기준(질문)에 따라 데이터를 구분하는 자료 구조로, 보통 이진 트리로 표현된다. 해당 figure에서는 루트 노드에서 "$a1<a2$?"를 물어보고, 그에 따라 왼쪽/오른쪽으로 분기한다. 그 이후로도 "$a2<a3$?", "$a1<a3$?" 같은 비교를 통해 리프에 도달하며, 리프 노드에는 $(1,2,3),(1,3,2),(2,1,3)$과 같은 최종 정렬된 순열이 기록된다. 이때 중요한 것은 이 결정 트리의 높이(height)가 바로 최악의 경우 비교 횟수, 즉 정렬의 최악 시간 복잡도라는 것이다. 이를 통해 비교 기반 정렬의 최선의 시간 복잡도가 O(n log(n))이라는 것을 증명할 수 있다:

1. n개의 정렬할 원소가 존재한다면, 서로 다른 n!개의 순열이 만들어질 수 있다.
2. 결정 트리의 리프 수도 최소한 n!개가 필요하다.
3. 높이가 h인 이진 트리의 리프 수는 최대 2^h이므로, $n!\le 2^h\to h\ge log(n!)$
4. 따라서 정렬의 최악 시간 복잡도는 $\mathrm{\Omega }(log(n!))$
5. 근사식을 사용하면, $log(n!)\approx \theta (nlog(n))$
6. 따라서, 시간 복잡도는 $\mathrm{\Omega }(log(n!))\approx \mathrm{\Omega }(nlog(n))$이다.

Bucketsort

위는 어떤 비교 기반 정렬도 $\mathrm{\Omega }(nlog(n))$보다 빠를 수 없다는 것을 보여준다. 따라서 정렬 알고리즘의 효율성을 더욱 높이고자 한다면, 비교 기반 정렬이라는 기존의 틀을 벗어날 필요가 있다. 예를 들어 52장의 트럼프카드를 정렬한다고 할때, 효율적인 정렬 방식은 아래와 같다:

1. 카드 숫자(1~13)에 따라 13개의 더미(pile)를 만들고 같은 숫자끼리 모은다.
2. 같은 숫자 카드끼리는 많아야 4장밖에 없으니 같은 숫자끼리는 간단히 삽입 정렬로 정렬할 수 있다.

이렇게 하면 각 카드는 바로 자신의 더미로 가므로 O(n) 시간에 정렬이 가능하다. 위 방법의 핵심은 카드의 숫자들이나 모양을 비교하지 않고 직접 자리에 배치(mapping)하는 방식이다. Bucketsort는 이와 같은 방식을 활용하여, 아래와 같이 구현된다:

1. n개의 숫자가 1부터 m 사이에서 균등 분포되어 있다고 하자.
2. 총 n개의 버킷을 만들고, 각 버킷은 구간 m/n을 담당한다. 예를 들어 첫 번째 버킷은 [1, m/n], 두 번째는 [m/n+1, 2m/n] 범위이다.
3. 각 입력 x는 버킷 번호가 $\lceil$xn/m$\rceil$에 속하는 버킷에 속하게 되며, 해당 연산의 시간 복잡도는 O(1)이다.

위 구현에서 입력이 균등하게 되어 있다면, 각 버킷에 평균적으로 원소가 하나 존재하며, 각 버킷 안에서의 정렬은 O(1)의 시간복잡도를 요구한다. 따라서 원소를 버킷에 분배하고, 버킷 내부를 정렬하고, 각 버킷을 연결하는 작업은 모두 O(n)의 시간 복잡도 내에 이루어진다.

하지만 데이터가 균등 분포가 아니라, 모든 원소가 하나의 버킷에 몰린 경우에는 얘기가 달라진다. 이 경우에는 각 원소를 버킷에 O(n)의 시간을 써서 분배했으나, 여전히 하나의 큰 버킷을 정렬해야 해서 결과적으로 O(n log(n))의 시간 복잡도가 추가로 소요된다. 즉, 최악의 경우 성능이 보장되지 않는다. 이렇게 편향된 입력은 현실에서 종종 이루어 지므로, 데이터를 잘 이해하고 있는 경우에 bucketsort를 사용하는 것이 권장된다.

Non-Comparison Sorts Don’t Beat the Bound

Radix sort도 bucketsort와 같이 비교를 하지 않는 정렬이지만, 무조건 O(n)의 시간 복잡도를 보장하지는 않는다. Radix sort는 수나 문자열을 자릿수(또는 문자 위치) 단위로 나눠서 정렬하는 알고리즘이다. 예를 들어, 숫자 [329, 457, 657, 839, 436, 720, 355]를 정렬할 때:

1. 일의 자리 기준으로 정렬 → [720, 355, 436, 457, 657, 329, 839]
2. 십의 자리 기준으로 정렬 → [720, 329, 436, 839, 355, 457, 657]
3. 백의 자리 기준으로 정렬 → [329, 355, 436, 457, 657, 720, 839]

위는 가장 낮은 자릿수부터 정렬하는 LSD(Least Significant Digit first) 방식의 radix sort의 예시이다. 이는 n개의 문자열 길이가 m일 때, O(nm) 시간 복잡도를 가지며, m에 따라 선형적인 시간 복잡도를 가진다고 할 수 있다. 하지만 모든 입력이 임의의 키 값을 가진다면 d 값은 필연적으로 커진다. 이는 n개의 서로 다른 키를 가지려면, 적어도 n개를 구분할 수 있는 키의 길이 d를 가져야 하기 때문이다. 예를 들어:

• m = 1비트 → 표현 가능한 경우는 2개 (0,1)밖에 없음.
• m = 2비트 → 4개 구분 가능.
• m = 3비트 → 8개 구분 가능.

즉, m비트로 표현 가능한 서로 다른 키의 개수는 최대 2개이다. 따라서 우리가 n개의 키를 구분하려면 반드시 $2^m\ge n\to m\ge logn$이어야 한다. 즉, m값이 고정되어 있는 경우에는 O(n) 정렬이 가능하다. 하지만 임의의 길이를 가지는 키 값을 사용하는 경우에는 $m\ge logn$이상이다. 따라서 이 경우 시간 복잡도는 $O(m\cdot n)\ge O(nlog(n))$이다. 따라서 일반적인 임의 키들의 정렬은 여전히 $\theta (nlog(n))$을 벗어나지 못한다.