5. 퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복법을 이용한 정렬 알고리즘이다.

기준 원소 $p$(pivot)를 정하여 정렬하고자 하는 리스트를 $LT$ ($p$보다 작은 원소들), $EQ$ ($p$와 같은 원소들), $GT$ ($p$보다 큰 원소들)의 세 부분으로 분할하고, $LT$와 $GT$를 재귀를 통해 각각 정렬 후, 세 부분을 합쳐 정렬을 완료한다.

def quickSort(L):
    if len(L)> 1:
        i = -1 # pivot, 보통은 마지막 원소를 사용
        LT, EQ, GT = partition(L, i)
        quickSort(LT)
        quickSort(GT)
        L = merge(LT, EQ, GT)
    return L

리스트 분할

리스트의 각 원소를 차례대로 꺼내어 기준 원소 p와 비교하여 분할하기 때문에, 분할 단계는 $O(n)$ 시간이 소요된다.

def partition(L, i):
    p = L.get(i)
    LT, EQ, GT = [], [], []
    while !L.isEmpty():
        e = L.removeFirst()
        if e < p:
            LT.addLast(e)
        elif e == p:
            EQ.addLast(e)
        else:
            GT.addLast(e)
    return LT, EQ, GT

기준 원소 선택

• 결정적이며 쉬운 방법
  • 맨 앞 원소
  • 맨 뒤 원소
  • 중간 원소
• 결정적이며 조금 복잡한 방법
  • 맨 앞, 중간, 맨 뒤 위치의 세 원소의 중앙값 (median)
  • 0/4, 1/4, 2/4, 3/4, 4/4 위치의 다섯 원소의 중앙값
  • 전체 원소의 중앙값
• 기준 원소에

따라 분할 결과와 퀵 정렬의 수행 성능이 달라지게 된다.

퀵 정렬의 실행시간

퀵 정렬의 최악의 경우는, 기준 원소가 항상 유일한 최소 원소이거나 최대 원소일 경우이다.

이 경우, $LT$와 $GT$ 중 하나는 크기가 $n-1$이며, 다른 하나는 크기가 $0$이 된다. 이 경우, 실행시간은 $n+(n-1)+\cdots+2+1$이 되고, 이는 $O(n^2)$이다.

반면, 퀵 정렬에서 좋은 호출은 $LT$와 $GT$의 크기가 모두 $\frac {3}{4}$보다 작은 경우이다. 랜덤으로 $p$를 선택했을 때, 좋은 호출이 일어날 확률은 $\frac{1}{2}$이다.

무작위로 피벗을 선택한 퀵 정렬에서, $i/2$는 좋은 호출을 기대할 수 있으므로, 분할은 $O(log n)$회 일어날 것으로 기대할 수 있고, 기대실행시간은 $O(n\log n)$이다.

제자리 퀵 정렬

퀵 정렬을 제자리에서 수행하도록 구현할 수 있다.

def inPlaceQuickSort(L, l, r): # L은 리스트, l부터 r까지의 위치에 대해 정렬 수행
    if l>=r:
        return
    k = between(l, r) # l과 r 사이의 위치
    a, b = inPlacePartition(L, l, r, k)
    inPlaceQuickSort(L, l, a-1)
    inPlaceQuickSort(L, b+1, r)

def inPlacePartition(L, l, r, k):
    p = A[k] # pivot
    swap(A[k], A[r]) # pivot을 맨 뒤로
    i = l
    j = r-1
    while i<=j:
        while i<=j and A[i]<=p: # 앞부분은 pivot보다 작은거
            i += 1
        while j>=i and A[j]>=p: # 뒷부분은 pivot보다 큰걸로 나눠주고
            j -= 1
        if i<j: 
            swap(A[i], A[j])
    swap(A[i], A[r]) # 그 사이에 pivot 넣어주기
    return i, j # p보다 작은거, 큰거 인덱스 리턴

합병 정렬과 퀵 정렬의 비교

	합병 정렬	퀵 정렬
기법	분할 정복법
실행시간	$O(n \log n)$ 최악실행시간	$O(n^2)$ 최악실행시간 $O(n\log n)$ 기대실행시간
분할과 결합	분할이 쉽고, 합병이 어렵다.	분할이 어렵고, 합병이 쉽다.
제자리 구현	제자리 합병 어렵다.	제자리 분할 쉽다.
실제 작업 순서	작은 것에서 점점 큰 부문제로 진행	큰 것에서 점점 작은 부문제로 진행

퀵 정렬 변형

배열을 크게 나누어 정렬하는 퀵 정렬의 특성에 착안해, 일단 어느 정도 정렬을 퀵 정렬로 진행하고, 정렬이 어느 정도 완료되면 삽입 정렬로 마무리하는 방법이 있다.

어느 정도 정렬된 배열에서 삽입 정렬의 속도가 아주 빠르기 때문에, 이 방법을 응용하면 빠른 시간 안에 정렬을 완료할 수 있다.