면접 준비를 하면서 퀵 소트를 직접 구현해보고 있는데 구글링을 하면서 다양한 방법이 있지만 그 중에서도 pivot을 정하는 데 있어서 어떤 방법이 가장 효과적인지 생각해보았다.

여러 블로그나 질문글(?)에서 볼 때 mid(가운데)값을 pivot으로 설정할 경우, 효과적인 결과를 얻을 수 있다고 포스팅이 되어있는 경우가 많았다. 하지만 최악의 경우 어차피 시간 복잡도는 $O(N^2)$ 이므로 일반적으로 모든 경우의 수에서 사용될 수 있는 것이 뭘까 찾아보았다.

• randomly choosing an element
• picking from the middle
• picking a median of the first
• middle and last element
• even more complicated recursive fomulars

등 다양하게 있었지만, random하게 찾는 방법은 비용도 클 뿐더러 항상 최적의 답을 찾아 주지는 않는다.

출처 - Olivera Popović

🎯  가장 직관적인 방법은 배열의 맨 앞의 원소를 pivot으로 설정하는 것이다.

구현

가장 중요한 것은 배열 내 하나의 원소를 pivot으로 설정한 후, 배열을 왼쪽은 pivot보다 작거나 같은 원소들로 나열하고, 그 반대로 배열의 오른쪽은 pivot보다 크거나 같은 원소들로 나열하는 것이다.

array : [ left side ] +[ pivot ] + [ right side ]

• left side: 모든 원소 $\leq$ pivot
• right side: 모든 원소 $\geq$ pivot

지금부터 가장 직관적인 방법인 배열의 맨 앞 원소를 pivot으로 Quick Sort를 진행할 것이다.

예를 들어서 어느 배열이 아래와 같이 있다고 가정하자.

test_list = [5, 3, 8, 4, 9, 1, 6, 2, 7]

• 5를 pivot으로 설정
• 배열의 처음과 끝을 left와 right로 설정
• 원소들을 left side와 right side로 나눠주면서 배열 내에서 탐색할 요소
  왼쪽 부터 low, 오른쪽 부터 high

이런 모습을 하고 있을 것이다.

[5]	3	8	4	9	1	6	2	7
left								right
pivot	low							high

low는 왼쪽에서부터 오른쪽으로 가면서 pivot보다 큰 값을 만나면 멈추게 된다.

마찬가지로 high는 오른쪽에서부터 왼쪽으로 가면서 pivot보다 작은 값을 만나면 멈추게된다.

그럼 이때 low와 high의 위치를 바꿔주게 되면 왼쪽에는 pivot보다 작거나 같은 값이, 오른쪽에는 pivot보다 크거나 같은 값이 오게 된다.

• low: 현재 가리키고 있는 원소 $\leq$ pivot, low + 1
• high: 현재 가리키고 있는 원소 $\geq$ pivot, high - 1

이런식으로 low와 high에 위치한 값을 바꿔주다보면 low와 high가 만나게 된다. 만나게 되는 순간 이제 더이상 pivot의 의미는 사라지게 된다. 왜냐하면 이미 배열 내 왼편과 오른편이 pivot을 기준으로 새롭게 나열됐기 때문이다.

작업을 모두 마친 후에는 처음에 설정했던 pivot을 high의 위치에 넣어주게되면 pivot을 기준으로 왼편과 오른편이 나열된 모습을 볼 수 있다.

이를 코드로 나타내면 아래와 같다.

# Divide
def partition(arr, left, right):
    low, high = left + 1, right
    pivot = arr[left]

    while True:
        while low <= high and pivot <= arr[high]:
            high -= 1
        while low <= high and arr[low] <= pivot:
            low += 1
        if low <= high:
            arr[low], arr[high] = arr[high], arr[low]
        else:
            break
    arr[left], arr[high] = arr[high], arr[left]
    return high

이렇게 되면 return 되는 high에 해당하는 index는 이미 정렬된 사실을 알 수 있고 나머지 부분을 똑같은 작업을 해주면 된다.

def quick_sort(numbers, left, right):
    if left >= right: return
    pivot_index = partition(numbers, left, right)
    quick_sort(numbers, left, pivot_index - 1)
    quick_sort(numbers, pivot_index + 1, right)

left와 right가 같다면 해당 원소는 1개일 것이므로 정렬을 마친 상태이다.

이렇게 분할-정복 방법을 사용해서 퀵 소트를 구현할 수 있다. 위와 같이 구현된 퀵 소트는 아래와 같은 특성을 가진다.

• 분할-정복 방법
• 같은 메모리 내 교환 방법
  추가적인 배열을 생성해내거나 복사하지 않는다
• 불안정 정렬
  중복된 값이 있을 경우, 순서가 바뀔 수 있다
  

---

Pythonic

def pythonic_quick_sort(arr):
    if len(arr) <= 1: return arr
    
    pivot = arr[0]
    remain = arr[1:]
    
    left_side = [x for x in remain if x <= pivot]
    right_side = [x for x in remain if x > pivot]
    
    return pythonic_quick_sort(left_side) + [pivot] + pythonic_quick_sort(right_side)

python 답게 사용하는 방법 또한 있는데 직관적으로 이해하기에도 좋다.