정렬

정렬은 컴퓨터 과학에서 가장 기초적이면서 중요한 내용 중 하나이다. 당장 핸드폰 연락처나 컴퓨터 파일 시스템도 이름 순으로 정렬되어 있고, 이분 탐색이나 투 포인터는 정렬된 목록에서만 동작하는 등 정말 많은 곳에서 사용한다. 기초적이고 중요한 만큼 정렬하는 방법도 여러 가지가 있는데, 가장 유명하고 또 많이 쓰이는 방법은 버블 정렬, 힙 정렬, 퀵 정렬, 기수 정렬 이렇게 네 가지이다.

버블 정렬은 가장 간단하고 가장 느린 방법으로, 배열에서 가장 작은 원소를 찾아 첫 번째 값과 교환하고, 두 번째로 작은 원소를 찾아 두 번째 값과 교환하고, 세 번째로 작은 원소를 찾아 세 번째 값과 교환하고, 이 과정을 배열의 모든 순서에 대해 실행한다. 시간 복잡도는 n번 비교하여 한 번 교환하는 작업을 n번 진행하므로 O(n^2)가 된다.

for (int i = 0; i < len; i++)
    for (int j = i + 1; j < len; j++)
        if (arr[i] > arr[j]) swap(arr[i], arr[j]);

힙 정렬은 배열을 순차적으로 정렬하는 것이 아니라, 가장 작은 값이 항상 첫 번째로 오는 자료 구조인 힙을 만들어 값을 순차적으로 제거할 수 있게 하는 것을 말한다. 주로 값이 자주 추가되는 경우에 많이 사용되고, 배열의 길이 n에 대해 힙의 높이는 log2(n)이므로 시간 복잡도는 O(n * log2(n))이다. 직접 구현해서 사용할 수도 있지만, STL에선 queue 헤더의 priority_queue가 힙을 이용해 구현되었으므로 직접 구현할 필요 없이 사용할 수 있다.

int get_child(int parent) {
    int left = parent * 2, right = parent * 2 + 1;

    if (right > MAX || (!heap[left] && !heap[right])) return 0;

    if (!heap[left]) return right;
    if (!heap[right]) return left;
    return heap[left] < heap[right] ? left : right;
}

int pop() {
    int idx = 1, cmp, ret = heap[idx];
    
    heap[idx] = heap[heap[0]];
    heap[heap[0]] = 0;

    while ((cmp = get_child(idx)) && heap[idx] > heap[cmp]) 
        idx = swap(idx, cmp);

    heap[0] -= (heap[0] > 0);

    return ret;
}

void push(int item) {
    int idx = ++heap[0];
    heap[idx] = item;
    while (idx > 1 && heap[idx] < heap[idx / 2]) idx = swap(idx, idx / 2);
}

퀵 정렬은 가장 자주 사용되는 정렬 방법 중 하나로, 우선 배열에서 성분 하나를 골라 해당 성분보다 작은 값과 큰 값으로 나눈다. 이후 작은 값들은 고른 성분의 왼쪽에, 큰 값들은 고른 성분의 오른쪽에 둔 뒤, 작은 값과 큰 값에 대해 같은 작업을 반복한다. 이 과정을 각 작은 값과 큰 값의 개수가 1 이하일 때까지 반복하면 모든 값을 정렬할 수 있다. 퀵 정렬 역시 직접 구현해서 사용할 수도 있지만, STL에선 algorithm 헤더의 sort 함수가 퀵 정렬을 이용해 구현되었으므로 직접 구현할 필요 없이 사용할 수 있다.

void sort(int* start, int* end) {
    int pivot = *(end - 1), *l = start, *r = start;
    if (end - start <= 1)
        return;

    while ((r + 1) < end) {
        while ((l + 1) < end && *l < pivot) l++;
        for (r = l; (r + 1) < end && *r > pivot; r++);
        swap(l, r);
    }
    sort(start, l);
    sort(l + 1, end);
}

기수 정렬은 위의 세 정렬과 조금 다른데, 예를 들어 자연수를 정렬한다고 하면 우선 자연수의 1의 자리가 같은 수를 순서대로 모은 뒤, 다시 10의 자리가 같은 수를 순서대로 모으고, 100의 자리가 같은 수를 순서대로 모으고, 이 방법을 계속 반복해 모든 자리에 대해 비교한 다음 다시 순서대로 나열해 정렬하는 것을 말한다. 알고리즘 문제에서 기수정렬 자체를 사용할 일은 거의 없고, 대신 기수 정렬을 조금 변형해 각 수가 나온 횟수를 세어 작은 수부터 나온 횟수만큼 출력하는 식으로 사용하기도 한다.

void sort(int* start, int* end) {
    int arr[MAX_NUMBER - MIN_NUMBER + 1] = { 0, }, idx = 0;
    for (auto it = start; it != end; it++) arr[*it - MIN_NUMBER]++;
    for (auto it = start; it != end; it++) {
        while (!arr[idx]) idx++;
        *it = idx + MIN_NUMBER;
        arr[idx]--;
    }
}