정렬 알고리즘 관련 기본 정리

O(n^2) 알고리즘

Selection Sort

성능 요구사항이 없거나, n이 작을 때 사용하는 방식. 구현을 잊어버릴 수 없을만큼 간단하다.

void selSort(T arr[], int size) {
    for(int i = 0; i < size; ++i) {
        for(int j = i + 1; j < size; ++j) {
            if (arr[i] > arr[j]) {
                T tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

Insertion Sort

데이터가 뒤쪽으로 1개씩 추가되는 경우에, O(n)으로 제일 빠르다. 또한 memory의 locality를 살릴 수 있는 방식으로 유명하다.

이 방식은, i-1번째까지 원소들이 이미 정렬되어있다고 가정하고, i번쨰 원소를 적절한 곳에 삽입하는 방식이라서, Insertion sort 라고 불린다. 이 방식의 경우 swap보다 assign 연산을 1회 줄일 수 있어서 더 빠르다. 실제로, O(n^2) 알고리즘 중에 제일 빠르다고 할 수 있다.

void insertionSort(T arr[], int size) {
    for(int i = 1; i < size; ++i) {
        T tmp = arr[i]; // 비교하고자 하는 원소를 임시로 저장한다.
        int j = i - 1;
        for(; j >= 0; --j) { // j 위치를 0까지 가면서 삽입할 곳을 찾는다.
            if (arr[j] < tmp) break;
            arr[j+1] = arr[j]; // swap 대신에, 뒤쪽으로 원소를 1개 민다.
        }
        arr[j+1] = tmp; // 최종 목적지에 임시로 저장한 원소를 넣고 마무리한다.
    }
}

O(n log n) 알고리즘

Quick Sort

stable 하지는 않지만, 작성이 쉽고 랜덤한 분포를 가지는 데이터에 대해서 성능이 빠르다. 아래 코드의 구간은 [s, e] 이다.

void qSort(T arr[], int s, int e) {
    int l = s, r = e;
    T pivot = arr[(s + e) >> 1];

    while(l < r) {
        while(arr[l] < pivot) ++l;
        while(pivot < arr[r]) --r;
        if (i > j) break;

        T tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;

        ++l; --r;
    }
    qSort(arr, s, r);
    qSort(arr, l, e);
}

Merge Sort

stable 한 정렬 중에 제일 빠름. 안정적. worst에도 O(n log n)이 보장되어 PS에서 자주 쓰인다. Quick Sort 대비 메모리 사용량이 2배이기 때문에, 개인적으로는 덜 선호하는 편이지만, stable이 필요한 경우에는 어쩔 수 없이 사용되어야 한다.

구간은 마찬가지로 [s, e] 로 나누는 것이 생각하기에 간단하다.

T tmp[MAX_SIZE];
void mergeSort(T arr[], int s, int e) {
    if (s >= e) return;
    int mid = (s + e) >> 1;
    mergeSort(arr, s, mid);
    mergeSort(arr, mid + 1, e);

    int i = s, j = mid + 1;
    int k = s;
    for(;i <= mid && j <= e;) {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    for(;i <= mid; ++i, ++k)
        tmp[k] = arr[i];
    for(;j <= e; ++j, ++k)
        tmp[k] = arr[j];
    for(i = s; i <= e; ++i)
        arr[i] = tmp[i]; // realloc
}

딱히 더 빠르진 않지만 두뇌회전을 위해 아래와 같은 코드 축약 버전도 한번 기억해보자. 두 조건을 만족할 때 i++를 쓰고, 나머지의 경우 j++를 쓰는 것. i++의 사용조건만 정해지면 나머지는 j++가 되는 것에 착안한다.

1. 현재 j가 e 범위를 이미 초과했거나 (무조건 i를 써야함)
2. 또는 i가 범위 안이면서, arr[i] <= arr[j] 일 때. (등호 조건이 있어야 stable이다)

이렇게 축약하면, Quick Sort보다 오히려 코드 작성량이 적다.

T tmp[MAX_SIZE];
void mergeSort(T arr[], int s, int e) {
    if (s >= e) return;
    int mid = (s + e) >> 1;
    mergeSort(arr, s, mid);
    mergeSort(arr, mid + 1, e);

    int i = s, j = mid + 1;
    int k = s;
    for(;k <= e;++k)
        // 아래에서 arr[i] <= arr[j] 의 괄호가 빠지지 않아야 stable 임에 유의!
        tmp[k] = ((j > e) || (i <= mid) && (arr[i] <= arr[j])) ? arr[i++] : arr[j++];
    for(i = s; i <= e; ++i)
        arr[i] = tmp[i]; // realloc
}

특수 알고리즘

Bucket Sort

Radix Sort, Bucket Sort 모두 같은 개념이다. 흔히들 10진법을 Radix Sort에 사용하곤 하는데, 사실 그럴 필요가 없다. 메모리 공간은 훨씬 더 많이 사용할 수 있으므로, 65536진법 = 1<<16 진법을 사용하여, short 만큼의 1 << 16 배열에 Counting 해서 넣는 방식으로 반복하면, int 범위의 수도 쉽게 정렬할 수 있다. Counting 한 배열을 이용하면, 총 시간복잡도 O(n) 에 정렬이 완성된다. (정확히는 물론 O(n)의 상수배 되겠다) 사실 위 알고리즘들과 비교하면 말도 안될 정도로 빠른 알고리즘이라고 볼 수 있다.

이 경우 T type generic을 쓸 수 없고, 구체적인 범위의 수 범위가 필요하다. 가장 간단한 unsigned int의 예시가 아래와 같다.

unsigned int cnt[1<<16 | 1];
unsigned int acc[1<<16 | 1];
unsigned int tmp[ARR_SIZE];
unsigned int cnt2[1<<16 | 1];
unsigned int acc2[1<<16 | 1];
void bucketSort(unsigned int arr[]) {
    // 하위 부분 정렬
    for(int i = 0; i < ARR_SIZE; ++i)
        cnt[arr[i] & 0xFFFF]++;
    for(int i = 1; i <= (1<<16); ++i)
        acc[i] = acc[i - 1] + cnt[i - 1];
    for(int i = 0; i < ARR_SIZE; ++i)
        tmp[acc[arr[i] & 0xFFFF]++] = arr[i];
    // 상위 부분 정렬
    for(int i = 0; i < ARR_SIZE; ++i)
        cnt2[arr[i] >> 16]++;
    for(int i = 1; i <= (1<<16); ++i)
        acc2[i] = acc2[i - 1] + cnt2[i - 1];
    for(int i = 0; i < ARR_SIZE; ++i)
        arr[acc[tmp[i] >> 16]++] = tmp[i];
}

하위 bit -> 상위 bit 순으로 정렬을 하는 이유는 상위 bit의 영향력이 더 크기 때문이라고 이해하면 쉽다.