Quick sort

퀵정렬은 최악의 경우 O(n^2)의 수행시간으로, 평균 O(n log n)의 수행시간으로 배열을 정렬하는 알고리즘이다. 

O(n log n) 내에 숨겨진 상수인자가 매우 작아 속도 면에서 매우 효율적이며, 내부 정렬로 작동하기 때문에 실제 문제에서 가장 유용한 정렬 방법 중 하나이다. 

(내부정렬이란, 정렬하고자 하는 배열 이외의 추가적인 배열공간을 필요로 하지 않는 것을 의미한다.)

 

퀵정렬은 사전에 배열이 보다 많이 정렬되어 있을수록, 배열 내의 겹치는 원소 수가 많아질 수록 수행시간이 O(n^2)에 가까워진다. 

이에 대한 자세한 내용은 후술한다. 

 

퀵정렬은 divide&conquer방식으로 작동한다. 

A[first~last]의 본래 배열을 A[first~mid-1] A[mid+1~ last]로 분할한다. 

분할 과정에서 A[first~mid-1]의 배열에는 A[mid]보다 작은 원소들이, A[mid+1,~ast]의 배열에는 A[mid]보다 큰 원소들이 배열된다. 

 

quick_sort(A,first,last)
    if first<last
        mid=partition(A,first,last)
        quick_sort(first,mid-1)
        quick_sort(mid+1,last)

partition(A,first,last)
    i=first-1
    x=A[last]
    for j=first to last-1
        if A[j]<x
            i++
            SWAP(A[i],A[j])
    i++
    SWAP(A[i],A[last])
    return i

 

퀵정렬의 성능

분할을 가장 나쁘게 하는 경우

퀵정렬에서 최악의 경우는 분할 과정에서 원래 문제를 n-1개의 원소와 0개의 원소를 갖는 부분문제로 분할하는 것이다. 

이 경우 O(n^2)의 수행시간이 걸린다. 

이 경우는 입력배열이 거의 다 정렬되어있을 경우 발생하게 되는데, 이런 경우는 insertion sort를 이용할 경우 오히려 O(n)시간에 정렬이 가능하다.

 

분할을 가장 잘 하는 경우

가장 고른 분할은 본래 문제를 거의 같은 크기의 두 개의 부분문제로 나누는 경우이다. 

이 경우 O(n log n)의 수행시간에 정렬이 가능하다.

 

평균적인 수행시간에 대하여

퀵 정렬의 평균 수행시간은 최적의 경우와 더 가깝다.

이를 이해하기 위해서는 분할의 균형 정도가 수행속도에 어느정도의 영향을 미치는지를 알아봐야 한다. 

 

가령, 분할 알고리즘이 문제를 항상 9:1로 분할하는 경우를 생각해보자. 

언뜻 보기에 매우 불균등하게 보이지만, 이 경우 퀵 정렬의 수행시간에 대한 재귀 관계식은 다음과 같다. 

T(n)<=T(9n/10)+T(n/10)+cn

이 경우, 퀵정렬의 수행시간은 O(n log n)이 된다. 

 

직관적으로 매우 불균등해 보이지만, 매 재귀 단계에서 9:1 비율로 분할된다면, 퀵 정렬은 점근적으로는 정확하게 반반씩 분할할 때 처럼 O(n logn)의 수행시간에 정렬을 완료할 수 있다.

심지어 99:1로 분할하더라도 O(n log n)의 수행시간이 나온다. 

즉, 분할이 100:0으로 분할되지만 않는다면 수행시간은 O(n log n)이 된다. 

가장 불균등하게 분할하는 단계를 몇 개 끼워넣는다 해도 총 수행시간은 여전히 O(n log n)이다. 

랜덤화된 퀵 정렬

상술한대로 거의 정렬된 배열의 경우 O(n^2)의 수행시간이 필요하다.

그러나 알고리즘에 랜덤화기법을 적용함으로써 모든 입력에 대해 성능의 기대값을 높일 수 있다.

 

부분배열 A[first~last]중 하나의 원소를 선택해서 이 원소를 A[last]와 교환하는 것이다.

이렇게 할 경우, 거의 정렬되어있는 배열일지라도 100:0이 아닌 보다 균형잡힌 크기의 부분배열들로 배열을 분할할 수 있고, 점근적으로 수행시간이 O(n logn)에 근접하게 된다. 

 

randomize_partition(A,first,last)
    i=random(first,last)
    SWAP(A[i],A[last])
    return partition(A,first,last)

randomize_quick_sort(A,first,last)
    if(first<last)
        mid=randomize_partition(A,first,last)
        randomize_quick_sort(A,first,mid-1)
        randomize_quick_sort(A,mid+1,last)

 

셋 중 중앙값 분할

랜덤화된 퀵정렬을 개선하기 위한 방법으로, 기준이 되는 원소를 임의로 하나를 선정하는 것이 아니라 보다 신중하게 선택하는 방법이 있다. 

바로 배열 내의 무작위의 3개의 원소를 뽑아 그 중앙값을 기준 원소로 삼는 방법이 있다. 

 

동일한 원소들에 대한 퀵 정렬

퀵정렬의 성능분석에서 보았듯, 100:0으로 분할되는 경우가 많아질수록 퀵정렬의 성능은 안좋아진다.

그렇다면 모든 원소들이 같다면 모든 분할이 100:0으로 분할될 것이고, 총 수행시간은 O(n^2)이 될 것이다.

 

이 문제를 해결하기 위해 partition단계에서 기준 원소와 중복되는 원소들의 위치를 파악한 후, A[first~ mid_first-1]까지는 기준원소보다 작은 원소들을, A[mid_last+1 ~ last]까지는 기준 원소보다 큰 원소들을 정렬시키는 방식으로 보다 수행시간을 단축시킬 수 있다. 

 

quick_sort_for_same_element(A,first,last)
    if first<last
        mid_first,mid_last = partition_for_same_element(A,first,last)
        quick_sort_for_same_element(A,first,mid_first-1)
        quick_sort_for_same_element(A,mid_last+1,last);

partition_for_same_element(A,first,last)
    i=first-1
    k=first;
    x=ary[last];
    
    for j=first to last-1
        if ary[j] == x
            if ary[j]==x
                i++
                SWAP(ary[i],ary[j])
            else
                i++
                SWAP(ary[i],ary[j])
                SWAP(ary[i],ary[k])
                k++
    i++
    SWAP(ary[i],ary[last]);
	mid_first=k
    mid_last=i
    
    return mid_first,mid_last

위와같은 방법을 통해 같은 원소들이 있을 경우, 해당 원소의 뭉텅이들을 완료한 이후, 그것들을 제외한 나머지 부분을 수행하는 형태로 보다 정렬을 효율적으로 수행할 수 있다.