파이썬으로 정리하는 Quick-Sort
quick sort는 말 그대로 빠른 정렬을 의미한다. 큰 문제를 쪼개 작은 문제로 만들어서 정복하는 divide-and-conquer 패러다임에 바탕을 두고 있어 퍼포먼스가 좋다.
https://idea-instructions.com/quick-sort/
기본적인 매커니즘은 그리 어렵지 않다.
- 리스트에서 값 하나를 골라 pivot으로 정한다.
- pivot보다 작은 것은 pivot의 왼쪽으로 보낸다.
- pivot보다 큰 것은 pivot의 오른쪽으로 보낸다.
- pivot의 왼쪽에 있는 값들로 새로운 리스트를 만들어 또 pivot을 정하고, pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 보낸다. 그리고 다시 왼쪽, 오른쪽 값들로 새로운 리스트를 만들어 이동하는 과정을 반복한다.
- pivot의 오른쪽에 있는 값들로 새로운 리스트를 만들어 또 pivot을 정하고 pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 보낸다. 그리고 다시 왼쪽, 오른쪽 값들로 새로운 리스트를 만들어 이동하는 과정을 반복한다.
위 과정을 재귀적으로 반복하면 리스트의 값들이 정렬된다. 단계적으로 살펴보면 이렇다.
# input
[85, 24, 63, 45, 17, 31, 96, 50]
# 50을 pivot으로 정한다.
[85, 24, 63, 45, 17, 31, 96, "50"]
# pivot(50)보다 작은 것은 pivot의 왼쪽으로, 큰 것은 오른쪽으로 보낸다.
[24, 45, 17, 31, "50", 85, 63, 96]
# pivot(50)의 왼쪽에 있는 값들로 새로운 리스트를 만들고, 31을 pivot으로 정한다.
[_, _, _, _, "50", 85, 63, 96]
[24, 45, 17, "31"]
# pivot(31)보다 작은 것은 pivot(31)의 왼쪽으로, 큰 것은 오른쪽으로 보낸다.
[_, _, _, _, "50", 85, 63, 96]
[24, 17, "31", 45]
# pivot(31)의 왼쪽에 있는 값들로 새로운 리스트를 만들고, 17을 pivot으로 정한다.
[_, _, _, _, "50", 85, 63, 96]
[_, _, "31", 45]
[24, "17"]
# pivot(17)보다 작은 것은 pivot(17)의 왼쪽으로, 큰 것은 오른쪽으로 보낸다.
[_, _, _, _, "50", 85, 63, 96]
[_, _, "31", 45]
["17", 24]
# pivot(17)의 왼쪽에 있는 값들로 새로운 리스트를 만든다. (왼쪽에 값이 없으므로 패스)
[_, _, _, _, "50", 85, 63, 96]
[_, _, "31", 45]
["17", 24]
[]
# pivot(17)의 오른쪽에 있는 값들로 새로운 리스트를 만든다. (값이 하나이므로 패스)
[_, _, _, _, "50", 85, 63, 96]
[_, _, "31", 45]
["17", _]
[] [24]
# 리스트를 pivot(17) 오른쪽에 넣는다. (호출한 값이 return되는 과정)
[_, _, _, _, "50", 85, 63, 96]
[_, _, "31", 45]
["17", 24]
[] [_]
# 리스트를 pivot(31) 왼쪽에 넣는다. (호출한 값이 return되는 과정)
[_, _, _, _, "50", 85, 63, 96]
[17, 24, "31", 45]
[_, _]
[] [_]
# pivot(31)의 오른쪽에 있는 값들로 새로운 리스트를 만든다. (값이 하나이므로 패스)
[_, _, _, _, "50", 85, 63, 96]
[17, 24, "31", 45]
[_, _] [45]
[] [_]
# 리스트를 pivot(31) 오른쪽에 넣는다. (호출한 값이 return되는 과정)
[_, _, _, _, "50", 85, 63, 96]
[17, 24, "31", 45]
[_, _] [_]
[] [_]
# 리스트를 pivot(50) 왼쪽에 넣는다. (호출한 값이 return되는 과정)
[17, 24, 31, 45, "50", 85, 63, 96]
[_, _, _, _]
[_, _] [_]
[] [_]
# 위 과정을 pivot(50)의 오른쪽 리스트에 대해 반복한다.
[17, 24, 31, 45, "50", 63, 85, 96]
[_, _, _, _] [_, _, _]
[_, _] [_] [_, _] []
[] [_] [_] []
# output
[17, 24, 31, 45, 50, 63, 85, 96]여기서는 리스트의 마지막 값을 항상 pivot으로 정했지만, random하게 pivot을 정할 수도 있고, 중앙값을 pivot으로 정할 수도 있다. 중앙값을 pivot으로 정하는 정렬 과정을 시각화하면 이 영상처럼 보인다. (quick sort를 이해하는 데 별로 도움은 안 되지만 재밌다.)
그리고 좀 더 최적화된 방법으로 inplace quick sort를 쓸 수 있다. inplace 방식은 pivot을 정하고 왼쪽, 오른쪽으로 값들을 이동시키는 과정을 개선한 것이다.
- 먼저 왼쪽에서 출발하는 인덱스
l과 오른쪽에서 출발하는 인덱스r을 만든다. l은 pivot보다 큰 값을 만나면 정지하고,r은 pivot보다 작은 값을 만나면 정지한다.- 두 인덱스가 모두 정지하면 값을 교체한다.
- 이 과정을
l과r이 같아질 때까지 반복한다.
이런 식으로 구현하면 더 적은 메모리를 사용할 수 있다.
# pivot = 50
# l = 85, r = 96, (l > pivot)
["85", 24, 63, 45, 17, 31, "96", "50"]
# l = 85, r = 31, (l > pivot) (r < pivot)
["85", 24, 63, 45, 17, "31", 96, "50"]
# l과 r을 교체
["31", 24, 63, 45, 17, "85", 96, "50"]
# l = 24, r = 17, (r < pivot)
[31, "24", 63, 45, "17", 85, 96, "50"]
# l = 63, r = 17 (l > pivot) (r < pivot)
[31, 24, "63", 45, "17", 85, 96, "50"]
# l과 r을 교체
[31, 24, "17", 45, "63", 85, 96, "50"]
# l = 45, r = 45 (l == r)
[31, 24, 17, "45", 63, 85, 96, "50"]
# l(45)과 r(45)이 pivot보다 작거나 같으므로 l += 1
# l = 63, r = 45
[31, 24, 17, "45", "63", 85, 96, "50"]
# l과 pivot을 교체
[31, 24, 17, 45, "50", 85, 96, 63]파이썬으로 구현하면 다음과 같다.
def quick_sort(S, a, b):
if a >= b:
return
pivot = S[b]
left = a
right = b - 1
while left <= right:
while left <= right and S[left] < pivot:
left += 1
while left <= right and pivot < S[right]:
right -= 1
if left <= right:
S[left], S[right] = S[right], S[left]
left, right = left + 1, right - 1
S[left], S[b] = S[b], S[left]
quick_sort(S, a, left - 1)
quick_sort(S, left + 1, b)이미 정렬되어 있는 리스트를 quick sort로 정렬하는 경우