퀵 정렬

시간복잡도 : 최악의 경우 O(N^2) 평균적으로 O(NlogN) 이다. 데이터 복사가 없기 때문에 병합보다 일반적인 경우 더 빠름 시간복잡도 같아도

1. pivot >= v[low] 이면 low 를 오른쪽 이동 반복
2. pivot <= v[high] 이면 high 를 왼쪽 이동 반복
3. 1,2 의 반복문을 빠져나왔을때 low < high 이면 v[low] v[high] 교체
4. 1,2,3 반복
5. low > high 가 되면 반복문 빠져나와서 v[pivot] 과 v[high] 스왑
6. 그 후 pivot 기준으로 나뉘어진 왼,오 를 다시 퀵 소트로 각각 pivot 다시 설정해서 정렬 반복

void QuickSort(vector<int>& v, int left, int right)
{
    if (left > right)
        return;
    int pivot = v[left];
    int low = left + 1;
    int high = right;

    while (low <= high)
    {
        while (low <= right && pivot >= v[low])
        {
            low++;
        }
        // pivot + 1 이어야 하니깐 범위가
        while (high >= left + 1 && pivot <= v[high] )
        {
            high--;
        }

        if (low < high)
            swap(v[low], v[high]);        
    }

    swap(v[left], v[high]);
    pivot = high;

    QuickSort(v, left, pivot - 1);
    QuickSort(v, pivot + 1, right);

}