퀵정렬

void quickSort(vector<int>& data, int startIndex, int endIndex) // pivot은 인덱스순서로 잡는걸 기준으로한다. 
{
    if (startIndex >= endIndex) return; // 반씩 자르다 최종적으로 원소개수가 1개가 될 경우.
 
    int pivot = startIndex; // 피벗 설정.
    int left = pivot + 1;
    int right = endIndex;
 
    while (1)
    {
        while (left <= endIndex && data[left] <= data[pivot]) // 피벗보다 큰 값을 찾을때까지 Left++
        {
            left++;
        }
        
        while (right > startIndex && data[right] >= data[pivot]) // 피벗보다 작은값을 찾을 때까지 right--. 
                                                                 //right >= startIndex가 아니라 right > startIndex로 작성해야함. startIndex가 피벗이라 포함시키면 안된다.
        {
            right--;
        }
 
        if (left > right) // 엇갈렸다면.
        {
            int temp = data[right];
            data[right] = data[pivot];
            data[pivot] = temp;
            break;
        }
        else
        {
            int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }
    }
 
    quickSort(data, startIndex , right - 1); // pivot 왼쪽 영역 정렬
    quickSort(data, right + 1, endIndex); // pivot 오른쪽 영역 정렬.
}
 
 
int main()
{
    vector<int> data = { 1,10,5,8,7,6,4,3,2,9 };
    quickSort(data, 0, data.size()-1);
 
    for (int i = 0; i <  10; i++)
    {
        cout << data[i] << ' ';
    }
}

 

나동빈님 블로그의 이론설명을 보고 구현했다. 코드도 거의 동일하다.

퀵소트의 평균적으로 N log N의 시간복잡도를 보이며, 최악의 경우 N^2의 형태를 보인다.

피벗을 어떻게 설정하느냐, 주어지는 배열이 어떻게 주어지냐에 따라 다르긴 한데 최악의 케이스 중 하나는 아래와 같다.

 

1. 배열이 정렬된 상태

2. 첫번째값을 피벗으로 설정하는 방식.

 

이런 케이스일 경우 시간복잡도가 O(N^2)가 되버린다.

 

1,2,3,4,5 라는 배열이 있다고 가정하자.

 

첫번째값을 피벗으로 잡기로 했으니 1을 피벗으로 잡고 left를 2부터, right를 5부터 탐색시킨다.

left는 처음부터 바로 pivot보다 큰 값을 찾았으므로 탐색이 바로 종료. right는 pivot보다 작은값, 즉 1보다 작은값을 찾아야하지만, 이미 정렬된 배열이기때문에 pivot에 갈때까지 그런값은 없다. 결국 pivot으로 되돌아와서 종료. (n-1번)

 

결국 pivot값 인덱스는 그대로다. 코드대로라면 pivot값 인덱스를 기준으로 반으로 쪼개서 왼쪽영역, 오른쪽영역에 대해서 퀵소트를 진행해야하지만 왼쪽영역을 진행할일은 없고 오른쪽영역에 대해서만 쭉 진행한다.

 

위와같은과정을 n번 반복하기 때문에 N * (N-1) => O(N^2) 라는 최악의 시간복잡도가 나오게 된다.

 

물론 주어진 배열이 정렬된 배열일 가능성은 극히 적긴 하지만, 늘 최악의 경우를 대비해야하기 때문에 여러 방법을 통해 개선한다. 

1. 배열의 원소를 섞는 방법. 

2. 피벗을 랜덤한 방법으로 설정.

3. 피벗을 임의의 원소를 선택하는 대신, 후보값 3개를 설정하고 3개의 중간값을 피벗으로 설정.

 

아래의 블로그글을 참고했는데, 보면 알겠지만 적용한거와 안한거는 성능차이가 굉장히 많이 난다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ljy9378&logNo=221508655059 

퀵 정렬(Quick Sort)과 최악의 경우(O(N^2))를 방지하기 위한 방법들

위의 방법 말고도 또 여러 방법이있는 것 같은데, 결국 주어지는 상황에 따라 어떤걸 써야할지 알아서 잘 판단해야 할 것 같다. 사실 당장은 그렇게 딥하게 알필요는 없을 것 같고 퀵소트의 기본원리, 그리고 '왜' 성능이 안좋은 경우가 있는지, '왜' 최적화를 해야하는지에 대해서 좀 알아두면 될 것 같다.