[Algorithm] 퀵 정렬 (Quick Sort)

Quick Sort

• 분할 정복을 이용한 정렬 알고리즘이다. (값에 따른 비균등 분할)
• 피벗을 정한 뒤 피벗의 위치를 확정해가며 정렬을 수행하는 것이 특징
• 일반적으로 각 부분 배열의 맨 앞 or 뒤를 피벗으로 정하는데, 이는 정렬 과정 동안 유지되어야 한다.
• 피벗이 확정되면 피벗의 앞에는 피벗보다 작은 값, 뒤에는 큰 값이 오게 한다. (오름차순 기준)

순서대로 pivot을 확정하면 pivot의 양 옆에 값의 크기에 따라 값들을 옮김

코드

#include <iostream>

void Print(int* arr)
{
    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

int Partition(int* arr, int p, int r)
{
    int pivot = arr[r]; // 부분 배열의 맨 마지막을 pivot으로 설정
    int i = p-1;
    
    // j => p부터 pivot 한 칸 앞까지 전진
    for (int j = p; j < r; j++)
    {
        if (arr[j] < pivot) // pivot보다 작은 수를 발견하면
            std::swap(arr[++i], arr[j]); // i를 전진 & j와 바꿈
    }

    std::swap(arr[++i], arr[r]); // pivot과 i의 다음 칸과 바꿈 => 왼쪽/오른쪽에 pivot보다 작은/큰 수로 나뉨

    return i;
}

void QuickSort(int* arr, int p, int r)
{
    if (p < r)
    {
        int q = Partition(arr, p, r); // q 자리는 확정
        QuickSort(arr, p, q-1); // q 자리는 확정됐으므로 q를 제외한 범위만 와야 함
        QuickSort(arr, q+1, r);
    }
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};

    Print(arr);
    // 최악(이미 정렬된 경우): O(n^2)
    // 평균: O(nlogn)
    QuickSort(arr, 0, 9);
    Print(arr);
}

QuickSort에서 배열을 분할한다. p와 r은 부분 배열의 양 끝 인덱스다.

부분 배열의 크기가 2 이상인 경우 (p < r), q의 자리를 Partition 함수를 통해 확정한 후, q를 제외한 나머지 p ~ q-1, q+1 ~ r 범위에 대해 다시 부분 배열을 나눈다.

 

Partition 함수에서는 부분 배열의 맨 마지막을 pivot으로 설정한다. 이때, 두 개의 포인터 i와 j가 사용되는데, j는 첫 번째 원소, i는 j보다 한 칸 왼쪽을 가리키게 한다.

j를 pivot의 앞까지 계속 이동시키면서, 만약 j 위치에 있는 값이 pivot보다 작은 경우 i를 한 칸 전진시킨 후 j에 있는 값과 스왑한다.

j가 pivot의 앞까지 도달하면 i를 한 칸 앞으로 보낸 후 pivot과 스왑한 후, pivot의 위치인 i를 리턴한다.

시각적 표시

시간 복잡도

평균적으로 O(nlogn)이나, 이미 정렬된 데이터가 들어오는 최악의 경우 O(n^2)으로 동작한다.

참고사항

• pivot 선정 방식에 따라 성능이 달라질 수도 있다. pivot을 랜덤으로 지정하면 최악의 경우 O(n^2)가 나오는 것을 피할 가능성이 높아지는데, 이를 Randomized Quick Sort라 한다.

pivot을 p ~ r 사이의 랜덤 값으로 지정한 후, 배열의 마지막과 pivot을 바꾸고 기존의 Partition 함수를 호출한다.