📊 파이썬으로 정리하는 Quick-Sort

quick sort는 말 그대로 빠른 정렬을 의미한다. 큰 문제를 쪼개 작은 문제로 만들어서 정복하는 divide-and-conquer 패러다임에 바탕을 두고 있어 퍼포먼스가 좋다.

https://idea-instructions.com/quick-sort/

기본적인 매커니즘은 그리 어렵지 않다.

1. 리스트에서 값 하나를 골라 pivot으로 정한다.
2. pivot보다 작은 것은 pivot의 왼쪽으로 보낸다.
3. pivot보다 큰 것은 pivot의 오른쪽으로 보낸다.
4. pivot의 왼쪽에 있는 값들로 새로운 리스트를 만들어 또 pivot을 정하고, pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 보낸다. 그리고 다시 왼쪽, 오른쪽 값들로 새로운 리스트를 만들어 이동하는 과정을 반복한다.
5. 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을 정하고 왼쪽, 오른쪽으로 값들을 이동시키는 과정을 개선한 것이다.

1. 먼저 왼쪽에서 출발하는 인덱스 l과 오른쪽에서 출발하는 인덱스 r을 만든다.
2. l은 pivot보다 큰 값을 만나면 정지하고, r은 pivot보다 작은 값을 만나면 정지한다.
3. 두 인덱스가 모두 정지하면 값을 교체한다.
4. 이 과정을 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로 정렬하는 경우$O(n^2)$시간이 걸린다. 즉, worst case에서$O(n^2)$시간이 걸린다는 말이다. 재밌는 것은 average case에서도$O(n \log n)$시간이 걸리는데, 이는 quick sort라는 이름이 붙을 정도로 빠른 것은 아니다. 그럼에도 quick sort인 이유는 알고리즘의 캐시 hit ratio가 높기 때문이다. (컴퓨터 아키텍처에 관한 부분이다.) 그래서 이론적으로는 평균$O(n \log n)$이지만 실제로는 더 빠르게 정렬된다.