[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬은 병합 정렬과 마찬가지로 분할과 정복 패러다임에 기반하고 있지만 모든 힘든 작업이 재귀 호출 앞에 행해지기 때문에 다소 정반대의 방법이다.

분할과 정복

분할과 정복 패러다임은 다음의 세 단계로 이루어진 일반적인 용어로 설명될 수 있다.

분할(Divide): 배열이 적어도 2개의 원소를 갖고 있다면 배열로부터 피봇(pivot)이라고 불리는 특정한 원소 x를 선택한다. 일반적으로 배열의 마지막 원소를 피봇 x로 선택한다. 배열로 부터 모든 원소를 삭제하여 이들을 세 개의 배열에 넣는다. 세 배열은 각각 x보다 작은 원소(L), x와 같은 원소(E), x보다 큰 원소(G)가 저장된다.
재귀(Recur): 재귀적으로 시퀀스 L과 G를 정렬한다.
정복(Conquer): 먼저 L의 원소, 다음 E의 원소, 마지막으로 G의 원소를 차례로 다시 넣는다.

C++ 구현

template <class RandomIt>
void quick_sort(RandomIt first, RandomIt last)
{
    if (first + 1 >= last) return;
    RandomIt l = first, r = last-2;
    while (l < r)
        if (*l < *(last-1)) ++l;
        else if (*r >= *(last-1)) --r;
        else
        {
            auto temp = *l;
            *l = *r;
            *r = temp;
        }
    if (*l <= *(last-1)) ++r;
    auto temp = *r;
    *r = *(last-1);
    *(last-1) = temp;
    quick_sort(first,r);
    quick_sort(r+1,last);
}

[first, last) 범위의 원소를 오름차순으로 퀵 정렬하는 코드이다.