[Algorithm#04] | 퀵 정렬(Quick Sort)

🎓 동빈나님의 강의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 듣고 정리한 내용입니다.

 

💻 알고리즘

퀵 정렬(Quick Sort)

• “특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까?”
• 퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬합니다. 더 쉽게 말하자면 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다.
• 퀵 정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN)입니다.

 

바로 한 번 예시를 통해서 살펴보도록 합시다. 일반적으로 퀵 정렬에서는 기준 값이 있습니다. 이를 피벗(Pivot)이라고도 하는데, 보통 첫 번째 원소를 피벗 값으로 설정하고 사용합니다. 다음과 같이 1이라는 값이 먼저 피벗 값으로 설정이 되었다고 생각해봅시다.

(1) 10 5 8 7 6 4 3 2 9

 

이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾습니다. 이 때 1보다 큰 숫자로는 바로 10을 찾을 수 있고, 1보다 작은 숫자는 찾지 못해서 결국 1까지 도달합니다. 이 때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 피벗 값과 작은 값의 위치를 바꿉니다. 즉, 1과 1을 교환하므로 제자리 걸음입니다.

1 10 5 8 7 6 4 3 2 9

 

따라서 위와 같이 구성되고, 이 때 피벗 값이었던 1의 왼쪽에는 1보다 작은 값이 존재하며 오른쪽에는 1보다 큰 값이 존재합니다. 이제 이어서 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 수행하는 겁니다.

1 (10) 5 8 7 6 4 3 2 9

 

이 때 왼쪽은 없으므로 무시하고, 오른쪽에서는 피벗 값으로 10이 채택됩니다. 10보다 큰 값을 왼쪽부터 찾고, 10보다 작은 값을 오른쪽부터 찾습니다. 큰 값은 찾지 못하게 되며 작은 값으로는 바로 9를 찾을 수 있습니다. 이 때 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 9와 10을 교환합니다.

1 5 8 7 6 4 3 2 10

 

따라서 위와 같이 구성되고, 이 때 피벗 값이었던 10의 왼쪽에는 10보다 작은 값이 존재하며 오른쪽에는 10보다 큰 값이 존재합니다. 이제 이어서 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 수행합니다.

1 (5) 8 7 6 4 3 2 10

 

이 때 오른쪽은 없으므로 무시하고, 왼쪽에서는 피벗 값으로 5가 채택됩니다. 5보다 큰 값을 왼쪽부터 찾고, 5보다 작은 값을 오른쪽부터 찾습니다. 큰 값으로는 8이 선택되고, 작은 값으로는 2가 선택됩니다. 이 때 작은 값의 인덱스가 큰 값의 인덱스보다 크므로 8과 2를 교환합니다.

1 (5) 2 7 6 4 3 8 10

 

이어서 큰 값과 작은 값을 바꾸어 다음과 같이 바뀝니다.

1 (5) 2 3 6 4 7 8 10

 

이어서 큰 값과 작은 값을 바꾸어 다음과 같이 바뀝니다.

1 (5) 2 3 4 6 7 8 10

 

이제 큰 값과 작은 값을 선택하면 각각 6과 4인데 작은 값의 인덱스가 큰 값의 인덱스보다 작으므로 피벗 값과 작은 값을 교환합니다. 따라서 다음과 같습니다.

1 4 2 3 5 6 7 8 10

 

이제 5를 기준으로 하여 5보다 작은 값은 왼쪽에 있고, 5보다 큰 값은 오른쪽에 있습니다. 이제 5의 왼쪽과 오른쪽에서 추가적으로 퀵 정렬을 수행합니다. 바로 다음과 같이 피벗값이 설정됩니다.

1 (4) 2 3 5 (6) 7 8 10

 

위와 같이 퀵 정렬을 순환적으로 수행하면 반으로 쪼개 들어가면서 분할 정복식으로 정렬이 완료됩니다. 이게 왜 빠른지 이해가 안 가시는 분은 직관적으로 다음과 같이 생각해보세요. 10 * 10은 100이지만 이를 전부 1개씩 나누게 되면 1 * 1을 10번 더한 값인 10에 불과합니다.

1 2 3 4 5 6 7 8 9 10

 

📝 문제

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

✏️ 소스 코드

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void QuickSort(int * data, int start, int end)
{
    if (start >= end)
    { // 원소가 1개인 이유 
        return;
    }

    // 키는 첫 번째 원소
    int key = start;
    int i = start + 1;
    int j = end;
    int temp;

    while (i <= j)
    { // 엇갈릴 때 까지 반복 
        while (data[i] <= data[key])
        { // 키 값보다 큰 값을 만날 때 까지 반복 
            i++;
        }

        while (data[j] >= data[key] && j > start)
        { // 키 값보다 작은 값을 만날 때 까지 반복
          // && 엇갈렸을 때 교체하게 되는데 왼쪽에 있는 값과 키 값을 교체해주기 때문에 start 이상으로 넘어오지 않게 한다. 
            j--;
        }

        if (i > j)
        { // 현재 엇갈린 상태면 왼쪽 값과 키 값 변경 
            // Swaping
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        }
        else // 현재 엇갈린 상태가 아니라면 큰 값과 작은 값을 서로 변경 
        {
            temp = data[j];
            data[j] = data[i];
            data[i] = temp;
        }

        // 똑같은 함수 안에 똑같은 함수를 호출함(재귀적 함수 구현) 
        // 왼쪽 
        QuickSort(data, start, j - 1);
        // 오른쪽 
        QuickSort(data, j + 1, end);
    }
}

int main(void)
{
    QuickSort(data, 0, number - 1);

    for (int i = 0; i < number; i++)
    {
        printf("%d ", data[i]);
    }
}

 

⏳ 시간 복잡도

퀵 정렬의 시간 복잡도는 O(N * logN)입니다.

위 소스코드를 보시면 '키 값보다 작은 값을 만날 때까지' 반복하는 부분에서 j가 start보다 클 때에 한해서만 반복문이 수행되도록 처리되어 있습니다. 이는 항상 왼쪽에 있는 값과 피벗 값을 교환하기 때문입니다. 오른쪽에 있는 값은 피벗 값과 교환되지 않으므로 처리해 줄 필요가 없습니다. 퀵 정렬 알고리즘은 기본적으로 N번씩 탐색하되 반으로 쪼개 들어간다는 점에서 log N을 곱한 복잡도를 가집니다.

하지만 퀵 정렬의 최악 시간 복잡도는 어떻게 될까요? 바로 O(N^2)입니다.

흔히 알고리즘 대회에서 복잡도 O(N * logN)을 요구하는 경우 퀵 정렬을 이용하면 틀리기도 합니다. 도대체 왜 최악의 경우 시간 복잡도가 O(N^2)일까요? 이는 다음의 경우를 생각해보세요.

 

📝 문제

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 2 3 4 5 6 7 8 9 10

위와 같이 이미 정렬이 되어 있는 경우 퀵 정렬의 시간 복잡도는 O(N^2)에 가깝습니다. 반면에 이전 시간에 다루었던 삽입 정렬의 경우 위 문제를 매우 빠르게 풀어낼 수 있습니다. 즉 정렬할 데이터의 특성에 따라서 적절한 정렬 알고리즘을 사용하는 것이 중요하다는 것입니다.

 

📚 참고 사이트

• 동빈나 블로그
• 동빈나 - 실전 알고리즘 강좌 (Algorithm Programming Tutorial)