이번에 살펴볼 정렬 알고리즘은, 실제 정렬 알고리즘 중 가장 인기있고 많이 사용되는 Quick Sort입니다. 이름 그대로 빨라서 quick sort겠지만, 이론적으로는 평균 $O(n\log n)$으로 앞서 배웠던 merge sort와 비슷한 수준입니다. 하지만 메모리 효율성 등의 측면에서 실제로 돌아가는 속도가 조금 더 빠르고 가볍기 때문에 많이들 사용한다고 합니다.

딱히 정렬을 해야한다 해서 살펴보는 것이 아니라, 알고리즘적인 생각을 돕기 위하여 살펴보는 것이니 가볍게 한 번 봅시다.

퀵소트

Quick sort의 원리는 이러합니다.

1. List에서 숫자 하나를 골라 pivot이라고 부릅니다.(Median 값을 고르는 것이 최선입니다.)
2. pivot을 맨 끝의 원소와 swap한 후, 1~$n-1$번째 원소까지 검사하면서 pivot보다 크면 후반부로, 작으면 전반부로 몰아줍니다.
3. 맨 끝에 있던 Pivot을 자기보다 큰 것들 중 첫번째 원소와 swap한 후 자신을 제외한 전반부와 후반부를 recursive call을 합니다.


결국 이 또한 $T(n)\approx n+2T(\frac{n}{2})$ (BEST CASE: pivot을 median으로 선택했을 때)이므로 Merge sort와 동일하게 $O(n\log n)$으로 동작합니다. 물론 Merge sort와 다르게 이러한 성능을 보장할 수는 없습니다. 왜일까요?

최악의 상황을 가정해 봅시다. 매번 pivot을 골랐는데 고를때마다 pivot이 최대값이 되는 경우를 상상해 봅시다. 그럴 경우 $T(n)=n+T(n-1)$로 쪼개게 되는데, 그렇게 되면 결국 1에서 $n$까지의 합을 구하는 것이기 때문에, $O(n)\approx n^2$가 되게 됩니다. 비효율적인 Bubble sort밖에 안되겠죠.

이렇게 매번 worst case를 취하는 것을 막기 위해 다양한 방법들이 있습니다만, 가장 직관적인 Randomized quick sort 방식으로 구현해 보려고 합니다. 즉, pivot을 뽑기로 뽑으면, 매번 worst case가 나올 확률이 매우 낮아진다는 점에서 착안한 것이죠.

#먼저 자주 쓰이는 list내 swap을 해주는 함수를 선언합니다.
def swap(A, i, j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp

#아까 말씀드렸다시피, pivot을 선택한 후에(parition 함수의 결과값으로 pivot의 최종 index가 나옵니다.) recursive call로 쪼갭니다.
def quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        quicksort(A, lo, p-1)
        quicksort(A, p+1, hi)

#이제 pivot을 뽑는 과정을 알아봅시다.
def partition(A, lo, hi):
    import random
    pivotIndex = random.randint(lo, hi) ##pivot을 뽑기로 뽑습니다.
    pivotValue = A[pivotIndex]
    
    # 일단 pivot을 마지막 원소와 바꾸고,
    swap(A, pivotIndex, hi)
    
    storeIndex = lo
    # 나머지 원소들은 A[hi]와 비교하면서 재정렬합니다.
    for i in range(lo, hi):
        if A[i] < pivotValue:
            swap(A, i, storeIndex)
            storeIndex += 1
    swap(A, storeIndex, hi) #마지막으로 pivot을 자신보다 큰 원소들의 첫번째 원소와 바꿔줍니다. (전반부, 후반부를 나누기 위해서)
    return storeIndex

이제 잘 구현 되었는지 확인해 볼까요?

>>> import random
>>> A = [random.randint(0, 100) for _ in range(15)] #임의로 0~100까지 15개 수를 뽑습니다.
>>> print A
[58, 13, 52, 42, 94, 25, 73, 59, 12, 85, 52, 52, 13, 98, 85]
>>> quicksort(A, 0, len(A)-1)
>>> print A
[12, 13, 13, 25, 42, 52, 52, 52, 58, 59, 73, 85, 85, 94, 98]

깔끔하게 정렬되어 있음을 확인할 수 있죠? :-) 정렬에 대한 개념들이 생각보다 응용이 많이 되기 때문에 꼭 스스로 구현해 보시길 바랍니다 :)