면접 준비를 하면서 퀵 소트를 직접 구현해보고 있는데 구글링을 하면서 다양한 방법이 있지만 그 중에서도 pivot을 정하는 데 있어서 어떤 방법이 가장 효과적인지 생각해보았다.
여러 블로그나 질문글(?)에서 볼 때 mid(가운데)값을 pivot으로 설정할 경우, 효과적인 결과를 얻을 수 있다고 포스팅이 되어있는 경우가 많았다. 하지만 최악의 경우 어차피 시간 복잡도는 이므로 일반적으로 모든 경우의 수에서 사용될 수 있는 것이 뭘까 찾아보았다.
등 다양하게 있었지만, random하게 찾는 방법은 비용도 클 뿐더러 항상 최적의 답을 찾아 주지는 않는다.
🎯 가장 직관적인 방법은 배열의 맨 앞의 원소를 pivot으로 설정하는 것이다.
가장 중요한 것은 배열 내 하나의 원소를 pivot으로 설정한 후, 배열을 왼쪽은 pivot보다 작거나 같은 원소들로 나열하고, 그 반대로 배열의 오른쪽은 pivot보다 크거나 같은 원소들로 나열하는 것이다.
array : [ left side ]
+[ pivot ]
+ [ right side ]
left side
: 모든 원소 pivot
right side
: 모든 원소 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
: 현재 가리키고 있는 원소 pivot, low + 1
high
: 현재 가리키고 있는 원소 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개일 것이므로 정렬을 마친 상태이다.
이렇게 분할-정복 방법을 사용해서 퀵 소트를 구현할 수 있다. 위와 같이 구현된 퀵 소트는 아래와 같은 특성을 가진다.
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 답게 사용하는 방법 또한 있는데 직관적으로 이해하기에도 좋다.