[알고리즘] 퀵 정렬(Quick Sort) - 코딩 밥상

퀵 정렬 이란?

이름 그대로 '빠른 정렬'이라고 할 만큼 앞서 배운 버블,삽입 정렬보다 월등히 좋은 성능을 갖습니다.

'분할 정복'에 바탕을 둔 알고리즘으로서 동작을 한마디로 정리하면 기준 요소 선정 및 분할의 반복입니다.

1. 기준이 될 요소를 임의로 선정하고 기준 보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 옮김
2. 왼쪽 그룹과 오른쪽 그룹을 분할하여 각 그룹에 대해 1번 과정을 수행
3. 그룹의 크기가 1 이하여서 더 이상 분할 할 수 없을 때까지 1번과 2번 과정을 반복

예를들어

5 1 6 4 8 3 7 9 2 을 오름차순으로 퀵 정렬 한다면,

5를 기준) 5 1 6 4 8 3 7 9 2 -> 1 4 3 2 5 6 8 7 9

1을 기준) 1 4 3 2 5 6 8 7 9 -> 1 4 3 2 5 6 8 7 9      왼쪽 그룹 분할 정복(예시에서의 기준 선정은 간단하게 첫번째 요소를 선정)

4를 기준) 1 4 3 2 5 6 8 7 9 -> 1 3 2 4 5 6 8 7 9

3을 기준) 1 3 2 4 5 6 8 7 9 -> 1 2 3 4 5 6 8 7 9

남은 그룹의 크기가 1이하이기 때문에 나머지 요소들도 확정 -> 1 2 3 4 5 6 8 7 9

6을 기준) 1 2 3 4 5 6 8 7 9 -> 1 2 3 4 5 6 8 7 9      오른쪽 그룹 분할 정복

8을 기준) 1 2 3 4 5 6 8 7 9 -> 1 2 3 4 5 6 7 8 9 

남은 그룹의 크기가 1이하이기 떄문에 나머지 요소들도 확정 -> 1 2 3 4 5 6 7 8 9

 

퀵 정렬 사용 전 해결해야 하는 2가지 문제

• 배열을 사용할 경우 퀵 정렬의 분할 과정을 어떻게 효율적으로 처리할 것인가?

=> 기준 요소의 왼쪽(처음)에서부터 오른쪽(끝)으로 이동하며 기준 요소보다 큰 요소를 색출,

      기준 요소의 오른쪽(끝)에서부터 왼쪽(처음)으로 이동하며 기준 요소보다 작은 요소를 색출,

      둘 다 색출에 성공했다면 서로의 요소값을 맞교환.

      두 색출 요소끼리 만날때까지 위 과정을 반복하고 만났을 경우 왼쪽 그룹의 마지막 요소와 기준 요소를 맞교환.

 

• 반복되는 분할 과정을 어떻게 처리할 것인가?

=> 재귀함수 활용

---

코드 구현

void swap(int* A, int* B){
    int temp = *A;
    *A = *B;
    *B = temp;
}

int Partition(int DataSet[], int left, int right){  //분할 정복하기(기준점 정하기)
    int first = left;
    int pivot = DataSet[first];
    ++left;
    
    while(left <= right){   //피벗 기준으로 1번째 문제 해결
        while(DataSet[left] <= pivot && left < right)   ++left;
        while(DataSet[right] >= pivot && left <= right) --right;
        
        if(left < right){
            swap(&DataSet[left], &DataSet[right]);
        }
        else break;
    }
    
    swap(&DataSet[first], &DataSet[right]);     //마지막에 기준과 왼쪽 그룹의 마지막 요소를 맞바꿈
    
    return right;
}

void QuickSort(int DataSet[], int left, int right){		//퀵 정렬
    if(left < right){
        int index = Partition(DataSet, left, right);
        
        QuickSort(DataSet, left, index-1);		//재귀로 2번째 문제 해결
        QuickSort(DataSet, index+1, right);
    }
}

---

퀵 정렬의 성능 측정

퀵 정렬은 앞서 설명했드시 기준 요소 선정과 분할의 반복으로 동작하는데, 분할 대상의 첫 번째 요소를 분할의 기준으로 정하기로 했으므로 비교나 계산이 필요하지 않으므로 이 부분은 성능 분석에서 제외합니다.

그렇다면 분할 수행 횟수만 계산하면 되는데, 재귀 호출을 이용하므로 성능을 분석하려면 재귀 호출의 '깊이'를 파악해야 합니다. 즉

• 재귀 호출의 깊이
• 분할을 위한 비교 횟수

이 점을 계산합니다.

 

퀵 정렬은 데이터 정렬 상태에 따라 성능이 크게 달라지는데, 데이터가 미리 정렬되어 있거나 역순으로 정렬된 경우 최악의 성능을 보입니다.

하지만 데이터가 무작위로 배치된 경우에는 최고의 성능을 나타냅니다.

 

최선의 경우

퀵 정렬이 한 번 호출될 때마다 자료구조가 1/2로 쪼개지는 경우입니다.

자료구조의 크기가 n일 때, 퀵정렬의 재귀 호출의 깊이는 log2n이라는 것입니다.

비교 횟수는 매 단계에서 쪼개져 있는 각 자료구조의 크기를 합하면 항상 n개가 되기 때문에 비교횟수 또한 항상 n번이 되겠네요.

정리하면, 이상적인 경우의 퀵 정렬 비교 횟수는

n x log2n => nlog2n입니다. 

버블 정렬과 삽입 정렬 모두 O(n*2)였지만 퀵 정렬은 O(nlogn)입니다.

n이 작은 값일때는 차이가 적지만, n이 점점 커질때마다 이 차이는 기하급수적으로 늘어나겠죠? 그래프만 그리봐도 체감 될 것입니다.

최악의 경우

최악의 경우는 매 재귀 호출마다 자료구조의 분할이 1 : n-1 로 이루어지는 것입니다. 즉 이미 정렬된 자료구조를 퀵정렬 하는 경우입니다.

이렇게 되면 재귀 호출의 깊이는 n-1이 되고 재귀 호출이 일어날 때마다 정렬 대상의 범위도 1씩 줄어듭니다. 

(n-1)+(n-2)+...+2+1 = n * (n-1)/2 = n(n-1)/2 이 되겠네요.

앞에서 봤던 버블,삽입 정렬과 비슷한 연산 수가 됩니다. 즉 최악의 경우에는 O(n^2)가 되는 것입니다.

 

 

이렇게 최선과 최악의 경우 보여주는 퍼포먼스가 차이가 나는 퀵 정렬을 왜 정렬의 스탠다드로 사용할까요?

평균의 경우를 생각해보면 됩니다.

퀵 정렬은 평균적으로 1.39nlogn 회 비교를 수행합니다. 즉 최선의 경우인 nlogn 의 경우에 비해 39% 정도만 느린 성능인 것입니다.

그렇기 때문에 표준 라이브러리에서도 퀵 정렬을 활용하여 qsort() 함수를 제공하는 것입니다.