Randomized Quicksort

Problem Solving (PS)를 할 때 정렬은 직접 구현하지 않고 std::sort를 이용하는 것이 상식이다.

왜냐면, 직접 구현하는 것이 까다롭기 때문이다. 퀵소트를 구현할 경우, 까딱하면 O(N^2)가 되어 시간초과를 내기 십상이다.

하지만 Randomization을 구현하고 적절한 tie-breaking을 구현하면 아래와 같이 평균 시간복잡도 O(N lg N)을 낼 수 있다.

 

코드 설명

• 기본적인 Quicksort 구현에 Pivot 선택 시 Randomization을 추가한 형태다.
• 랜덤한 숫자를 하나 골라 srand()를 호출해주면 기본 시드(seed)값에 대해 시간 초과가 나도록 설계된 데이터에서 시간 초과를 피할 수 있다.
• Randomization을 하더라도 구간 내의 숫자가 모두 같은 경우 맨 끝의 원소가 Pivot으로 선택되는 문제가 있다. 따라서 이를 막기 위해 Pivot값과 일치하는 숫자는 1/2의 확률로 왼쪽, 1/2의 확률로 오른쪽으로 분류한다. (CLRS Exercise 7.1-2 참조)

이렇게 하면 Online Judge (e.g. Baekjoon) 에서도 거의 평균 시간복잡도로 돌아간다.

https://www.acmicpc.net/problem/2751 에서 확인해보자.

 

Note 엄밀하게 말하면 아래의 rand_range 함수는 구간 길이가 RAND_MAX보다 클 때 특별한 처리를 해 주어야 한다. 하지만 굳이 그렇게 하지 않아도 Randomization에 의해 그냥 적당히 돌아가는 것 같다. 어차피 몇 번만 분할하면 구간 길이는 금방 RAND_MAX보다 작아질 테니까. (* RAND_MAX는 보통 32767이다.)

 

Sample Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <functional>
#include <queue>
#include <math.h>
#include <memory.h>
 
int readInt();
 
 
int N;
int P[1000000];
 
 
void GatherInput() {
    N = readInt();
    for (int i = 0; i < N; i++) {
        P[i] = readInt();
    }
}
 
int rand_range(int L, int R) {
    double tmp = rand() / ((double)RAND_MAX + 1); // tmp belongs to [0, 1)
    return (int)(tmp * (R - L + 1) + L);
}
 
int partition(int L, int R) {
    // pick pivot randomly
    int pivot = rand_range(L, R);
    std::swap(P[pivot], P[R]);
 
    // the same for non-randomized version
    int pivot_value = P[R];
 
    // loop invariant: [L, i) contains left elements
    //             and [i, j) contains right elements
    int i, j;
    for (i = L, j = L; j < R; j++) {
        if (P[j] < pivot_value || (j % 2 == 0 && P[j] == pivot_value)) {
            // left
            // exchange it with P[i]
            std::swap(P[i], P[j]);
            i++;
        }
        else {
            // right
            // just keep it
        }
    }
 
    std::swap(P[i], P[j]);
    return i;
}
 
void quicksort(int L, int R) {
    if (L < R) {
        int pivot = partition(L, R);
        quicksort(L, pivot - 1);
        quicksort(pivot + 1, R);
    }
}
 
void Solve() {
    srand(7598034);
    quicksort(0, N - 1);
    for (int i = 0; i < N; i++) {
        printf("%d\n", P[i]);
    }
}
 
int main() {
#ifdef BOJ
    int T = 1;
#else
    setbuf(stdout, NULL);
    int T = readInt();
#endif
    for (int test_case = 1; test_case <= T; test_case++) {
        GatherInput();
#ifndef BOJ
        printf("Case #%d\n", test_case);
#endif
        Solve();
    }
    return 0;
}
 
int readInt() {
    int p;
    scanf("%d", &p);
    return p;
}