[C/C++] 퀵 정렬(Quick Sort) 재귀 구현 코드

 퀵 정렬은 이름 그대로 빠른 정렬이다. 평균적인 시간복잡도가 O(NlogN)이며 일반적인 상황에서 빠른 속도를 보여주는 정렬 알고리즘이다. 퀵 정렬은 버블, 선택, 삽입 정렬과 비교했을 때 상대적으로 구현이 복잡하다.

 

 퀵 정렬은 대표적인 분할-정복(Divide-and-Conquer) 알고리즘으로 영역을 분할해서 정렬하는 방식을 채용한다. 퀵 정렬은 영역 분할의 기준을 피벗(Pivot)으로 두고 있으며 처음 피벗은 보통 정렬할 배열의 0번지로 지정한다.

 

아래 코드는 퀵 정렬을 재귀 함수로 구현한 코드이다.

void Swap(int& left, int& right)
{
    int temp = left;
    left = right;
    right = temp;
}
 
void Quick(int* items, int begin, int end)
{
    // 1. begin이 end보다 큰 경우 정렬이 끝났음을 암시
    if (begin >= end)
        return;
 
    // 2. 피벗을 정해준다. 보통 0번을 설정한다.
    int pivot = begin;
 
    // 3. 양쪽에서 값을 비교할 커서를 두 개 저장한다
    int left = begin + 1;
    int right = end;
 
    // 4. 분할 정복을 실시한다.
    // 5. left의 값이 right보다 커질 경우 엇갈렸다는 신호로 받아들여 반복문을 종료한다.
    while (left <= right)
    {
        // 6. left를 하나씩 증가시키면서 pivot값보다 큰 값을 찾는다.
        // (단, 여기서 left의 값은 끝 주소보다 커지면 안된다. 분할된 영역 내에서만 동작하도록 한다.)
        while (items[left] <= items[pivot] && left <= end)
            left++;
        // 7. right을 하나씩 감소시키면서 pivot값보다 작은 값을 찾는다.
        // (단, 여기서 right의 값은 시작 주소보다 작아지면 안됨. 분할된 영역 내에서만 동작하도록 한다.)
        while (items[right] >= items[pivot] && right > begin)
            right--;
 
        // 8. 만약 서로 엇갈렸다면 pivot과 right를 서로 스왑한다.
        // 8-1. 엇갈리지 않고 서로 값을 찾았다면 서로 스왑해준다.
        if (left > right)
            Swap(items[pivot], items[right]);
        else
            Swap(items[left], items[right]);
    }
 
    // 9. right을 기준으로 왼쪽 영역과 오른쪽 영역으로 나누어 재귀 함수를 실행한다.
    Quick(items, begin, right - 1);
    Quick(items, right + 1, end);
}