퀵 소트 (Quick sort)

이번에 정리할 알고리즘은 정렬 알고리즘 중에서 퀵 소트(Quick sort)이다.

 

정렬 알고리즘은 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort) 등 여럿 있지만

 

그래도 쓸만한(?) 정렬 알고리즘은 퀵 소트인 것 같다.

 

그래서 퀵 소트 너로 정했다!

 

 

일단 구현 원리는 이렇다.

 

1. 배열에 정렬되지 않은 숫자들이 있다.

 

2. 숫자들을 정렬할 범위를 지정하는 배열의 시작 인덱스와 끝 인덱스도 있다.

 

3. 그 범위 안에서 적당한 피벗(pivot)을 정한다.

 

4. 피벗 기준으로 작은 숫자들을 왼쪽에, 큰 숫자들을 오른쪽에 이동한다.

 

5. 피벗 기준으로 왼쪽과 오른쪽에 있는 숫자들을 부분 배열로 취급하여 다시 1번 과정부터 시작한다.

 

6. 부분 배열의 요소 개수가 1개가 될 때까지 반복한다.

 

 

위의 구현 원리에서 가장 핵심은 피벗 기준으로 숫자들을 이동하고 배열을 계속 쪼개는 것이다.

 

 

피벗 기준으로 숫자들을 이동하는 것부터 봐보자.

 

일단 피벗을 정해야 한다.

 

필자는 간단하게 중간에 있는 요소로 지정하였다.

 

그리고 시작 인덱스와 끝 인덱스가 있다고 앞서 언급하였다.

 

그들의 사이를 좁혀가면서 만날 때까지 어떤 일(?)을 수행하고

 

만나면 피벗과 그것(만나서 가리키는 요소)을 교환(swap)하면 된다.

 

그렇다면 그 어떤 일이란 무엇인가?

 

시작 인덱스는 끝 인덱스에 다가가면서 피벗보다 큰 요소를 찾는다.

 

반대로 끝 인덱스도 시작 인덱스에 다가가면서 피벗보다 작은 요소를 찾는다.

 

서로가 만나기 전에 위의 조건에 드는 요소를 찾았다면 교환을 한다.

 

그리고 만날 때까지 계속 반복한다.

 

지금까지의 내용을 코드로 구현하면 아래와 같다.

 

void QuickSort(std::size_t* arr, std::size_t left, std::size_t right)
{
    std::size_t pivot = (left + right) / 2;
    if (right > left)
    {
        std::size_t i = left, j = right;
        while (i < j)
        {
            for (; arr[i] <= arr[pivot] && i < j; ++i);
            for (; arr[j] >= arr[pivot] && i < j; --j);
            if (i < j)
            {
                Swap(arr[i], arr[j]);
            }
            else // i == j
            {
                ...
            }
        }
        ...
    }
}

 

바깥 while 문은 시작 인덱스(변수 i)와 끝 인덱스(변수 j)가 서로 만날 때까지 반복하도록 한다.

 

첫 번째 for 문은 시작 인덱스가 끝 인덱스를 만날 때까지 이동한다.

 

다만 끝 인덱스와 만나기 전에 피벗보다 큰 요소가 있으면 빠져나온다.

 

두 번째 for 문은 그 반대로 끝 인덱스가 시작 인덱스를 만날 때까지 이동한다.

 

마찬가지로 시작 인덱스와 만나기 전에 피벗보다 작은 요소가 있으면 빠져나온다.

 

그다음 if 문에서 아직 시작 인덱스와 끝 인덱스가 만나지 않았다면 서로의 요소를 교환한다.

 

그리고 else 문을 지나 다시 while 문의 초기로 가서 위의 과정을 반복한다.

 

이제 else 문을 봐보자.

 

else 문은 시작 인덱스와 끝 인덱스가 서로 만났을 때이다.

 

여기서 질문!

 

위의 코드에서 시작 인덱스와 끝 인덱스가 가리키는 요소는 과연 피벗일 수 있을까?

 

개인적인 의견이지만 구현 방식이나 원리만 익히는 일방적인 학습은 실력 향상에 별로 도움되지 않는다고 생각한다.

 

꼭 본인이 생각해 보는 것이 중요하다.

 

일단 답은 그럴 수 없다.

 

이 질문이 왜 나왔냐면 마지막으로 else 문에서 시작 인덱스와 끝 인덱스가 가리키는 요소랑 피벗과 교환만 하면 되는 것이 아니기 때문이다.

 

만약 시작 인덱스가 피벗보다 큰 요소를 발견한 후 끝 인덱스가 쭉 내려와 시작 인덱스와 만났다고 해보자.

 

그냥 교환해도 되는가?

 

아니다.

 

피벗이 속해 있는 부분이 피벗보다 작은 숫자들이 모여있는 곳일 수도 큰 숫자들이 모여 있는 곳일 수도 있다.

 

그 반대의 경우(시작 인덱스가 쭉 올라가는 경우)도 마찬가지이다.

 

그래서 약간의 조정이 필요하다.

 

코드는 아래와 같다.

 

void QuickSort(std::size_t* arr, std::size_t left, std::size_t right)
{
    std::size_t pivot = (left + right) / 2;
    if (right > left)
    {
        std::size_t i = left, j = right;
        while (i < j)
        {
            for (; arr[i] <= arr[pivot] && i < j; ++i);
            for (; arr[j] >= arr[pivot] && i < j; --j);
            if (i < j)
            {
                Swap(arr[i], arr[j]);
            }
            else // i == j
            {
                if (pivot < i && arr[pivot] < arr[i])
                    --i;
                else if (pivot > i && arr[pivot] > arr[i])
                    ++i;
                Swap(arr[pivot], arr[i]);
                break;
            }
        }
        ...
    }
}

 

else 문에선 시작 인덱스와 끝 인덱스가 같으니 시작 인덱스만 취급한다.

 

시작 인덱스가 피벗 인덱스보다 크고 시작 인덱스의 요소가 피벗보다 크다면

 

피벗과 교환할 요소를 시작 인덱스가 가리키는 이전 요소로 지정해야 한다.

 

시작 인덱스가 피벗보다 큰 요소를 찾은 후 끝 인덱스가 내려온 경우이거나

 

서로 교환 후 시작 인덱스가 끝 인덱스까지 도착한 경우이다.

 

그 반대의 경우도 마찬가지이므로 시작 인덱스가 피벗 인덱스보다 작고 피벗이 시작 인덱스의 요소보다 클 때

 

피벗과 교환할 요소를 시작 인덱스가 가리키는 다음 요소로 지정해야 한다.

 

여기까지가 피벗 기준으로 숫자들을 이동하는 방법이다.

 

 

이제 배열을 쪼개는 작업이 남아있다.

 

이것은 간단하게 시작 인덱스와 끝 인덱스를 다시 지정하여 재귀 호출을 하면 된다.

 

총 정리하면 주요 코드는 다음과 같다.

 

void Swap(std::size_t& a, std::size_t& b)
{
    std::size_t temp = a;
    a = b;
    b = temp;
}

void QuickSort(std::size_t* arr, std::size_t left, std::size_t right)
{
    std::size_t pivot = (left + right) / 2;
    if (right > left)
    {
        std::size_t i = left, j = right;
        while (i < j)
        {
            for (; arr[i] <= arr[pivot] && i < j; ++i);
            for (; arr[j] >= arr[pivot] && i < j; --j);
            if (i < j)
            {
                Swap(arr[i], arr[j]);
            }
            else // i == j
            {
                if (pivot < i && arr[pivot] < arr[i])
                    --i;
                else if (pivot > i && arr[pivot] > arr[i])
                    ++i;
                Swap(arr[pivot], arr[i]);
                break;
            }
        }
        
        if(0 < i)
            QuickSort(arr, left, i - 1);
        QuickSort(arr, i + 1, right);
    }
}

 

피벗의 왼쪽 부분에 대해 QuickSort 함수를 호출할 때 if 문이 붙은 이유는 언더플로우(underflow) 때문이다.

 

 

정렬 알고리즘을 직접 해보면서 정말 가볍게 보았다가 뒤통수를 크게 맞았다.

 

꼭 직접 구현해 보는 것이 정말 중요한 것 같다.