Quick 정렬

Quick 정렬의 논리

• left : 정렬 범위의 처음 지점
• right : 정렬 범위의 마지막 지점
• pivot : 정렬을 수행하는데 필요한 기준값

퀵 정렬 대상 현재상태 [오름차순 정렬]

• low : pivot을 제외한 가장 왼쪽 지점
• high : pivot을 제외한 가장 오른쪽 지점

1. low 를 오른쪽으로 이동. [pivot 보다 우선순위가 낮은 값을 만날때 까지]

2. high 를 왼쪽으로 이동. [pivot 보다 우선순위가 높은 값을 만날때 까지]

3. 현재 low의 값과 high의 값을 교환.

4. (1)~(3)번 과정 반복

5. low와 hight가 교차 되었을때, pivot의 값과 high의 값을 교환한다.

이렇게 pivot의 값이 정렬 완료 되었다.

여기까지가 pivot의 값을 정렬하기까지의 과정이다. ( pivot값 5의 왼편은 전부 작고, 오른편은 전부 크다)

이제 정렬이 안된 나머지 부분도 같은 방법으로 pivot을 정렬해야한다.

 

6. 정렬 완료된 값(5, 현재 high가 가르키는) 기준으로 양쪽에 left, right를 새로 할당하고 전 과정 반복한다.
    left > right 가 될 때 까지.

왼쪽 범위( left = left / right = high-1)

오른쪽 범위( left = high+1 / right = right)

반복

 

 

*시간 복잡도

pivot이 딱 중간 값이 선택되어 나뉘는 범위가 반반씩 줄어든 다고 했을 때

나뉘는 횟수는 logn, 범위 마다 연산 횟수가 n 이므로 O(n logn) 이 된다.

 

만약 pivot이 극단적으로 값이 치우져져 있으면 나뉘는 횟수가 n이 될 수 있기 때문에

최악은 O(n^2)  이 된다.

 

다만 pivot을 고를 때 보통 중간 값을 고르려고 따로 연산을 한다.

그래서 퀼정렬은 평균 시간 복잡도의 의미로 O(nlogn)를 쓴다.

 

 

구현 해보기

구현 하다보니 고려해야 될 것이 있었다.

low를 구할때 옮기다 보면 right보다 커질때가 있다.   ( 예) 오름차순 정렬할때 data가  5,4,3,2,1 이면  low가 끝까지 감. )

void QuickSort(vector<int>& seq, int start, int end) //오름차순
{
    if (start >= end)
        return;

    int base = seq[start];
    int low = start + 1, high = end;
    while (low <= high)     //교차된다고 바로 멈추는게 아니고 끝까지 찾는다.
    {
        while (low<=end)   
        {
            if (base < seq[low])
                break;
            ++low;
        }
        while (high > start)
        {
            if (base > seq[high])
                break;
            --high;
        }
        if(low<=high)//이걸 빼먹었네
            swap(seq[low], seq[high]);
    }
    swap(seq[start], seq[high]);

    QuickSort(seq, start, high - 1);
    QuickSort(seq, high + 1, end);
}


void QuickSort_Prog()
{
    vector<int> seq = { 5,7,9,6,4,1,8,2,3,15,19,13,17,10 };
    QuickSort(seq, 0, seq.size() - 1);
    for (int i = 0; i < seq.size(); ++i)
        cout << seq[i] << ", ";
    cout << endl;
}