Quick Sort

MergeSort 알고리즘의 시간 복잡도는 O(NlogN) 이다.

 

MergeSort는 매우 준수한 정렬 알고리즘이지만 추가적인 배열 하나가 더 필요하기 때문에 memory allocation이 일어난다.

그리고 새로운 메모리를 할당하는 과정은 꽤 비싸다.

이번 포스팅에서는 퀵정렬에 대해 알아보고, 시간복잡도에 대한 증명도 하고자 한다.

 

Quick Sort

대표적인 divide & conquer 알고리즘.

평균 시간복잡도: O(NlogN) 인 아주 훌륭한 알고리즘이다.

 

퀵 정렬은 조금 특이한 특징을 가지고 있는데, 바로 피벗(Pivot)을 사용한다는 점이다.

 

대략적인 소스코드는 다음과 같다.

int qsort(int a[], int n){
	// pivot
    int p = a[0];
    int i = 1; int j = n-1;
    while(i <= j){
    	while (a[i] < p) i++;
        while (a[j] > p) j--;
        if(i < j) // swap a[i], a[j];
    }
    // swap a[0], a[j];
    sort(a, j); sort(a+j+1, n-j-1);
    return 0;
}

여기서 눈여겨봐야 할 것은 피벗이다. 피벗으로 배열의 맨 앞의 값을 선택한다. (0번째 인덱스)

그 다음 i 를 배열의 인덱스 1부터, j를 배열의 마지막 인덱스: n-1 로 설정.

while문 안의 로직을 실행한다.

 

첫 번째 while 문이 끝나고 다음과 같은 상태가 된다.

a[j] 와 a[0] swap.

 

pivot보다 작은 값은 앞쪽으로, 피벗보다 큰 값은 뒤로 보낸다. 

다음과 같이 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값으로 정렬된다.

이후 피벗을 중심으로 좌우로 나누어, 재귀를 통해 divide & conquer 로 해를 구한다.

 

QuickSort의 시간복잡도 : O(NlogN) 이다.

 

QuickSort는 MergeSort와 달리 배열을 추가로 할당하지는 않는다.

따라서 메모리 사용 측면에서 mergeSort보다 훨씬 효율적이고, 많이 사용하는 알고리즘이다.

 

---

시간복잡도의 평균?

여기서 퀵소트의 시간복잡도는 평균적으로 O(nlogn) 이지만,  최악의 경우에는 O(n^2) 까지 증가하는 것으로 알려져 있다.

 

소스코드 끝에서 마지막으로 divide할 때 pivot의 위치가 가운데가 아닌 한쪽끝으로 쏠려있다면, 시간복잡도는 어떻게 될까?

T(n) = n + T(n-1) = n + (n-1) + T(n-2) = n + (n-1) + (n-2) + T(n-3) = ....... = O(n^2)

피벗의 위치가 계속 한쪽끝으로 쏠려있는 경우 O(n^2)의 시간 복잡도를 갖게 된다.

 

즉 피벗을 선택을 했는데 사이값들이 이미 정렬되어있을 때가 최악의 경우이다.

그렇다면 이럴 때는 O(n^2)으로 성능이 나쁜데, 왜 퀵소트를 성능이 좋은 알고리즘이라고 할까?

 

---

Quick Sort Performance 증명

우리는 "평균" 에 중점을 둬야 한다.

O(n^2)인 경우가 분명 있지만 이는 드문 케이스로, 평균적으로 O(nlogn) 임을 보이자.

 

우선 평균 시간복잡도를 구하기 전에 가정이 필요하다.

• 균등 : 해당 경우의 수가 일어날 확률은 1/n로 동일하다.
• n개를 정렬한다고 했을 때, 가능한 경우의 수는 n!개 이다.

n! 경우의 수가 모두 균등하게 같은 확률로 나온다고 가정.

 

  피벗 P |   확률

        1등 | 1/n

       2등 | 1/n

       3등 | 1/n

        ...     ...

       n등 | 1/n

 

E(n) : n개의 원소를 퀵정렬 할 때, 평균적인 비교 횟수라고 하자.

 

피벗 P의 위치가 1~n등까지 (인덱스로는 0 ~ n-1)

모두 동일하게 1/n의 확률로 나온다고 가정하자.

P: 피벗, k : 피벗의 등수

 

한 경우에서 피벗의  등수 = p 라면, 나머지 원소에 대해서도 퀵정렬을 해줘야 하므로 (p-1) , (n-p) 두 경우 모두를 고려해야 한다.

따라서 E(n)을 다음과 같이 정의할 수 있다.

 

앞의 n-1 은 피벗이 모든 원소와 비교하는 부분이고, 뒷부분은 균등한 확률에 의해 각 상황이 1/n의 확률로 출현하는 것이다.

E(n) 은 점화식 형태가 되고, 위 점화식을 소거하려면 n을 한 단계 낮춰 소거를 진행해주면 된다.

 

 

점화식 풀이

여기서부터가 중요하다. 우리는 현재 원소가 n 개일때의 QuickSort 의 평균적인 비교횟수, E(n)을 구하려고 한다.

따라서 정확한 연산을 하는 것이 아닌, 시간복잡도 빅-오를 구하기 위해 대략적으로 살펴보자.

 

E(n) 과 E(n-1) 관계를 나타내는 식이 도출되었으므로, 여기서 끌어내보자.

 

알고리즘을 풀면서 적분까지 하게 될 줄은 몰랐는데, 풀이는 이렇다.

n이 무한히 커지면 커질수록, O(logN)의 시간복잡도로 수렴하게 될 것! 

E(n)/(n+1) = O(logn)

따라서 E(n) = O(n logn) 이다.

 

N 값이 크면 클수록 위의 E 기댓값은 더 효과가 좋을 것이다. 따라서 평균적으로, QuickSort는 O(NlogN)의 시간복잡도를 갖는 것!

 

 

 

Selection Problem

피벗을 어떻게 선택해야 할까?

현재는 pivot으로 첫번째 원소를 골라 사용하고 있는데, 이 경우 위처럼 최악의 경우를 피한다는 보장이 없다.

따라서 배열의 원소중에서 대략적인 중간값을 피벗으로 선택해 알고리즘을 수행한다면 평균시간으로 수행될 것이다.

 

정확히 배열에서 중간값을 찾는 것이 아니라, 대략적인 중간값을 빠르게 찾아 피벗으로 삼는다면 O(NlogN)에 수행되지 않을까?

pivot을 선택할 때 대략적인 중간값(approximate medium)을 찾기 위한 Selection 알고리즘은 다음 포스팅에서 알아보자.