Quick Sort

CJB_ny·2022년 12월 8일

DataStructure & Algorithm

목록 보기

20/35

Quick sort는 Stable하지 않다.

1단계

먼저 "기준점"을 잡는다. 여기서는 5를 기준으로 잡아줌.

(pivot설정은 지 마음대로임. 8을 해도되고 상관없음..)

low ->, <- high 화살표 방향대로 이동을 할 것이다.

먼저 low부터 보면은 pivot보다 작을 경우 ++low를 진행시켜준다.

그러다가 pivot보다 큰 데이터를 만나면 low 증가를 멈추고 정지한다.

이후 high와 pivot의 데이터 비교를 시작한다.

high가 pivot보다 클 경우 --high를 계속 진행한다.

계속 당기다가 여기서 멈춘다. high가 가르키는 데이터가 pivot보다 작으니까.

2단계

low index가 high index보다 작다면은 데이터를 교체를 해준다.

이렇게 교체를 함 ㅇㅇ.

이후 1단계를 다시 반복을 하면은

이렇게 된다.

다시 low, high index를 비교후

데이터를 교체를 해준다.

그다음 다시 1단계 -> 2단계 진행을 하면은

low, high가 역전을 하는 상황이 발생을 하는데 이게 알고리즘 끝이다. => 3단계 진행을 한다.

3단계

1~2단계를 반복을 하다가 low, high의 index가 역전이 발생했을 때

pivot의 데이터와 high의 데이터를 swap해준다.

이게 끝임.

pivot보다 작은 애들은 swap하고 나서의 pivot위치의 왼쪽에, 5보다 큰 애들은 싹다 오른쪽으로 밀림.

이것을 재귀적으로 호출하면 된다.

구현

중간에 && 뒤에서 pivot >= v[low] 접근을 하고있는데 이러면 안됨.

int Partition(std::vector<int>& v, int left, int right)
{
    int pivotData = v[left];
    int pLeft = left + 1;
    int pRight = right;

    while (pLeft <= pRight)
    {
        while (pLeft <= right && pivotData >= v[pLeft])
            ++pLeft;
        
        while (pRight >= left + 1 && pivotData <= v[pRight])
            --pRight;

        if (pLeft < pRight)
            std::swap(v[pLeft], v[pRight]);        
    }

    std::swap(v[left], v[pRight]);
    return pRight;
}

void QuickSort(std::vector<int>& v, int left, int right)
{
    if (left > right)
        return;

    int pivotIdx = Partition(v, left, right);
    QuickSort(v, left, pivotIdx - 1);
    QuickSort(v, pivotIdx + 1, right);
}