피벗설정에 따른 퀵정렬의 속도

이전 포스트를 이어서 퀵정렬의 pivot을 설정하는 방법에 대해 이야기 하도록 하겠다.

먼저 퀵정렬이 빠른 이유에 대해 알아야 한다.

전제 조건은 랜덤하게 정렬된 배열을 퀵정렬 알고리즘으로 정렬하는 것으로 한다.

퀵정렬의 구동 원리를 자세히 생각해보면 퀵정렬이 빠른 이유를 알 수 있다.

구동원리는 다음과 같다.

1. 피벗을 설정한다.

2. 피벗보다 큰 수는 오른쪽 작은 수는 왼쪽에 배치한다. 

3. 피벗을 기준으로 두개의 배열로 나눈다.

4. 각각의 배열을 1번부터 재귀적으로 반복한다.

만약 위의 방법만으로 정렬이 되는 것을 믿지 못하겠다면 [ 10. QuickSort ] 포스트를 참조하여 직접 따라가면서 컴파일 해보는 것을 추천한다.

힌트를 주자면 위의 단계처럼 두개의 배열로 나누다 보면 언젠가 하나의 배열이 3개 혹은 2개 혹은 1개가 되는데  

상식적으로 생각해보면 3개중 하나의 요소를 기준으로 좌우로 정렬한다면 오름차순으로 정렬될 수 밖에 없다는 것을 생각해보기 바란다.

다시 돌아와서 내가 생각한 퀵정렬이 빠른 가장 큰 이유는 바로 먼 거리 처리 능력 이다.

다음과 같은 두개의 배열을 두 가지 방법으로 정렬한다고 가정하자.

[2,  3,  4,  5,  6,  7,  8,  …  N,  1] => 1과 N, 1과 (N - 1), 1과 (N - 2), 1과 (N - 3), ... 1과 (N - (N - 1)) 비교 후 제자리를 찾음 (총 N - 1번 비교) 

[2,  3,  4,  5,  6,  7,  8,  …  N,  1] => 1과 2를 비교 후 작다면 1앞에 배치 (1번 비교) 

( 극단적인 상황이지만 먼거리 처리 능력을 보여주는 좋은 예 인것 같다. )

정렬 알고리즘의 수행시간을 결정짓는 모든 근원은 비교연산의 횟수와 교환연산의 횟수이다. 

그리고 똑같은 코드를 얼마나 반복하는지이다.

(상식적으로 for문을 아무런 처리 없이 n^2 번 반복시킨다고 해도 그렇게 오랜시간이 걸리지 않는다.)

결국 빠른 알고리즘은 코드를 얼마나 적게 수행하는 지에 따라 결정된다. 

코드를 적게 수행하는 방법은 비교연산을 통해 코드를 스킵하는 것이다.

이 모든 것이 비교를 하는 방법에 따라 결정되며 곧 먼거리를 한번에 이동할 수 있는 알고리즘이냐 아니냐의 문제라고 생각한다.

기존 알고리즘의 문제점

그렇다면 퀵정렬의 먼거리 처리능력이 소용없어지게 된다면 퀵정렬이 느려질까? 

퀵정렬의 먼거리 처리 능력을 없애는 방법은 이미 정렬된 배열을 정렬 시키거나 역순으로 정렬된 배열을 정렬시키는 것이다.

위 두가지의 경우 퀵정렬 역시 순차적으로 모두 비교를 하게 되기 때문이다.

그 이유는 앞서 구현하였던 퀵정렬이 피봇을 선택하는 방법에서 찾을 수 있다. 

무조건 left의 값을 피봇으로 설정 하기 때문에 피봇이 항상 가장 크거나 가장 작은 값이된다.

때문에 모든 요소와 비교를 하며 먼거리 처리능력도 소용이 없게 된다.

실제로 앞선 [ 10. QuickSort ]의 알고리즘으로 역순 배열이나 정렬된 배열을 정렬하면 n^2의 시간이 걸린다.

해결방안

어떻게 하면 퀵정렬이 랜덤인 상황이 아니더라도 빠른속도를 유지 할 수 있을까?

사실 이부분에서 나는 굉장히 많은 시간을 보냈다. 알고리즘을 새로운 방법으로 짜보기도 하는 등 여러가지 시도를 해보았다. 

여러가지 시도를 하면서 중점을 맞춘 내용은 어떤 상황이더라도 Pivot을 기준으로 최대한 동등하게 배열을 나누는 것 이었다.

생각하기까지 매우 오랜시간이 걸렸지만 결과적으로는 매우 간단하게 해결할 수 있었다.

바로 배열의 가운데값을 피봇으로 설정하는 것이다.

물론 실제 가운데 값을 피봇으로 설정한 후 알고리즘을 실행시키면 제대로 정렬되지않을 뿐더러 데이터가 엉망이된다.

그래서 조금만 비껴생각해낸 것이 배열의 가운데 값을 left값과 교환하는 것이다. 그 이후의 방법은 기존알고리즘과 동일하다.

바뀐 코드는 아래와 같다.

// QUICKSORT_ver2
 
// Swap 함수 - 두 요소를 교환한다.
void swap(int& num1, int& num2)
{
    int temp = num1;
    num1 = num2;
    num2 = temp;
}
void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold, median;
    l_hold = left;
    r_hold = right;
 
    // pivot설정 방법 변경 (성능UP)
    median = (left + right) / 2;
    swap(numbers[left], numbers[median]);
 

이 아래로는 이전의 코드와 동일하다.

핵심적인 부분은 바로 median을 설정하는 부분과 그것을 left(원래의 피벗)과 교환하는 부분이다.

median을 배열의 가운데 요소로 선택하고 이것을 다시 피벗과 교환함으로써 피벗이 가장 큰값이나 작은 값이 아닌 중간값으로 설정된다.

때문에 오름차순이나 내림차순으로 미리 정렬된 배열의 경우에도 동등한 2개의 배열을 만들어 낼수 있으며 

이는 곧 퀵정렬의 강점을 살릴 수 있게 된다는 것이다.

위의 코드를 이용하여 실제로 테스트를 해본 결과는 아래와 같다.

기존의 알고리즘 

요소 수 :           100,000                  100,000,000   

랜덤 배열 :         0.017                        23
역순 배열 :         12.89            너무 오래걸려서 측정 불가
순열 배열 :         13.21             너무 오래걸려서 측정 불가

Median피벗 알고리즘

요소 수 :           100,000                  100,000,000   

랜덤 배열 :         0.017                           23
역순 배열 :         0.0076                      8.98
순열 배열 :         0.0072                      8.46

이전 알고리즘에 비해서 매우 빠른 속도를 보여준다.