티스토리 뷰

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

idea

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

  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. 이 과정을 lr이 같아질 때까지 반복한다.

이런 식으로 구현하면 더 적은 메모리를 사용할 수 있다.

# 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)이지만 실제로는 더 빠르게 정렬된다.

댓글
댓글쓰기 폼