[알고리즘] 퀵 정렬(quick sort)

합병 정렬과 비슷하게 분할 정복을 이용한 방법 (단, 합병 정렬과 달리 공간복잡도를 N만 사용)

1. Pivot을 설정한다.
2. 0 ~ N-1까지 원소들을 pivot을 기준으로 좌, 우로 나뉘게 한다. (partition)
3. Pivot을 기준으로 나뉜 왼쪽, 오른쪽 부분배열을 각각 정렬한다. (재귀)

#define N 6

quickSort(0, N - 1);

void quickSort(int left, int right)
{
    if (left <= right)
    {
        int pivot = partition(left, right);
        quickSort(left, pivot - 1);
        quickSort(pivot + 1, right);
    }
}

int partition(int left, int right)
{
    int pivot = data[left];
    int low = left + 1;
    int high = right;

    while (low <= high)
    {
        while (pivot >= data[low] && low <= right)
            low++;
        while (pivot <= data[high] && high >= (left + 1))
            high--;
        if (low <= high)
            swap(low, high);
    }
    swap(left, high);
    return high;
}

• 시간복잡도 : O(Nlog(N))
• 공간복잡도 : O(N)