퀵 정렬(Quick Sort)

퀵정렬 과정 
a. 피봇 값을 하나 선택한다 
b. 피봇 값을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 오도록 Swap 한다 
   (low(left), high(Right) 가 서로 만날때까지 반복함) 
c. 피봇 값을 기준으로 분할된 두영역을 다시 분할 정복으로 a. ~ c. 과정을 반복한다 

 

시간복잡도

평균: O(n log2 n)

최악: O(n^2) 이미 정렬되어있는 경우

int partition(int arr[], int left, int right)
{
    // low는 왼쪽에서 오른쪽으로 pivot보다 큰값이면 스탑
    // high는 오른쪽에서 왼쪽으로 pivot보다 작은값이면 스탑
    int pivot = arr[left];    // 기준 값
    int low = left + 1;        // 좌측 > 우측 탐색
    int high = right;        // 우측 > 좌측 탐색
    int temp;                // 임시 값
    while (low <= high)
    {
        while (arr[low] <= pivot)
            low++;
        while (high > left && arr[high] >= pivot)
            high--;
 
        if (low > high)
        {
            temp = arr[left];
            arr[left] = arr[high];
            arr[high] = temp;
        }
        else
        {
            temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
        }
    }
    cout << "========== quickSort sort partition ==========" << endl;
    return high;
}
 
void quickSort(int arr[], int left, int right)
{
    if (left >= right)
        return;
 
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
 
    cout << "========== quickSort sort ==========" << endl;
}