[Algo] 3 way-quicksort

퀵소트의 최선 시간복잡도가 O(N log N)라는 건 알고리즘을 공부한 사람이라면 알고 있을 것이다.
비교 횟수: O(N), 분할 횟수: O(log N)

퀵소트를 좀 더 효율적으로 만드는 방법
1) 피벗을 어떻게 설정하는가? (난수 분할, Median of Three)
2) 비재귀로 구현
3) 삽입정렬과 함께 사용

하지만 위의 방법대로 하더라도 최선의 시간복잡도는 여전히 O(N log N)이다
일반 퀵소트와는 다른 방법으로 이 최선의 시간복잡도를 개선시킬 수 있다.

3 Way-Quicksort

바로 pivot을 기준으로 dutch national flag를 알고리즘을 적용하는 것이다.
위의 알고리즘을 적용하여 퀵소트를 구현하면, 영역은 아래와 같이 나누어지게 된다.

1) 피벗보다 작은 값을 가지는 영역
2) 피벗과 같은 값을 가지는 영역
3) 피벗보다 큰 값을 가지는 영역

이렇게 3영역으로 나누어지게 되는데, 피벗과 같은 값을 가지는 영역을 추가함으로써 분할되는 좌/우의 영역을 최소화 시키는 것이다.
즉, 시간복잡도를 개선시키기 위한 아이디어로 분할 횟수를 최소화하자는 것이다.

예를 들어 아래와 같은 배열이 있다고 했을 때,
array = [1, 2, 2, 2, 2, 2, 2, 3]
기존 퀵소트는 중앙 피벗(pivot = 2)을 제외한 [1, 2, 2]와 [2, 2, 2, 3]를 좌/우 영역으로 분리하게 되는데,
여기서 문제점은 중앙 피벗을 제외한 '피벗과 같은 값'은 또 다시 좌/우 영역에서 퀵소트 과정을 겪어야 한다는 것이다.

3 way-quicksort는 이 피벗값과 중복되는 값을 좌/우 영역에서 제외시킴으로서 시간복잡도를 개선시켰다.
(위의 array로 예를 든다면 [1], [3]으로 분리된다)

최선의 경우는 모든 값이 동일하다고 했을 때, O(N)을 가지게 된다.

def patition(A, left, right):
    if left >= right:
        return
    mid = left
    pivot = A[(left + right) // 2]
    while mid <= right:
        if A[mid] < pivot:
            A[left], A[mid] = A[mid], A[left]
            left += 1
            mid += 1
        elif A[mid] > pivot:
            A[right], A[mid] = A[mid], A[right]
            right -= 1
        else:
            mid += 1
    return left, mid


def quick_sort(A, left, right):
    if left >= right:
        return
    left_section, right_section = patition(A, left, right)
    quick_sort(A, left, left_section - 1)
    quick_sort(A, right_section, right)


if __name__ == '__main__':
    import random
    array = [random.randint(0, 10) for _ in range(10)]
    print(array)
    quick_sort(array, 0, len(array) - 1)
    print(array)