퀵소트에 대해 알아보자

퀵소트는 정렬과 관련된 내용을 다룰 때 빠지지 않고 등장하는 알고리듬이다. 제자리 정렬로 구현할 수 있는 알고리듬 중에서는 가장 빠른 것으로 알려져 있다. (그래서 이름도 퀵 정렬) 평균적인 성능은 O(nlogn)이 나온다. 퀵소트의 원리는 간단히 말해서 데이터 중에서 기준이 되는 임의의 값 하나를 정하고 이를 보통 pivot이라 한다. 이제 다른 데이터들을 피봇과 비교하여 그보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮겨준다.

이 작업을 한 번 수행하면 피봇을 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값이 온다. 다시 피봇으로 나누어진 왼쪽과 오른쪽 구간에 대해서 재귀적으로 같은 동작을 수행해주면 전체 데이터가 정렬된 상태가 된다.

퀵소트는 비슷한 복잡도를 갖는 다른 정렬들도 있지만, 추가적인 메모리를 사용하지 않고 제자리에서 정렬이 가능하며 많은 경우에 성능이 좋다고 알려져 있어서 많이 사용된다. 게다가 의외로 구현이 많이 어렵지 않고 재귀적으로 구현하는 특징 덕분에 많은 알고리듬 관련 수업에서 단골 과제로 등장한다.

원리만 적용한 구현

퀵정렬의 원리만 두고 볼 때, 제자리 정렬이라는 조건만 제외한다면 아주 간단하게 구현할 수 있다.

  1. 데이터의 개수가 1개 이하이면 정렬된 것으로 본다.
  2. 기준값은 첫 원소로 쓴다
  3. ‘큰 것’의 부분집합과 ‘작은 것’의 부분집합을 골라낸 후
  4. 각각을 퀵정렬하여 ‘작은것’ + 기준값 + ‘큰 것’으로 다시 이어 붙인다.

이를 파이썬으로 구현하면 다음과 같다.

def quick_sort_f(arr):
  if len(arr) < 2:
    return arr
  p = arr[0]
  less = [x for x in arr if x < p]
  greater = [x for x in arr if x >= p]
  return quick_sort_f(less) + quick_sort_f(greater)

제자리 정렬로 구현하기

추가적인 메모리를 사용하지 않고 제자리에서 정렬되는 퀵소트를 구현해보자. 퀵소트 방식 자체는 똑같이 재귀적으로 동작해야 한다. 따라서 배열로 받은 인자는 계속 재귀호출 시 전달되어야 하므로, 실제 정렬을 수행할 범위를 인자로 알려주는 방식을 취한다. 따라서 quick_sort() 함수는 배열, 정렬할 구간의 왼쪽위치, 오른쪽위치를 인자로 받는다.

예제를 통한 알고리듬 이해

주어진 구간을 정렬하는 방식을 예를 들어 살펴보자. 리스트 [30,45,25,60,80,90,30,15,75,55]를 정렬하려고 한다. 먼저 피봇위치는 맨 처음이며, 그 다음 칸과 끝 칸을 구역의 양 끝으로 잡는다. 피봇을 P, 왼쪽 마크와 오른쪽 마크를 L, R로 표현하면 각각의 위치는 아래와 같이 표시할 수 있다.

1. 초기 자리 설정
30,45,25,60,80,90,35,15,75,55
^P ^L                      ^R

L은 결국 피봇보다 큰 값들의 왼쪽 경계 위치가 되어야 하고, R은 피봇보다 작거나 같은 값들의 경계가 될 것이다. 따라서 L은 오른쪽으로 R은 왼쪽으로 움직여야 하는데, 이 때 기준은 다음과 같다.

  1. L은 해당 위치의 값이 피봇보다 작다면 오른쪽으로 이동한다. 정렬구간의 끝보다 오른쪽으로 갈 수는 없다.
  2. R은 해당 위치의 값이 피봇보다 작지 않다면(이상이라면) 왼쪽으로 이동한다. 역시 정렬구간의 왼쪽을 벗어날 수 없다.

이 기준에 따라서 L을 움직이면 첫 값 45가 이미 30보다 크기 때문에 더 이상 움직일 수 없다. R은 55, 75를 지나서 15의 위치까지 오게된다.

2. L은 피봇값보다 작으면 오른쪽으로,
   R은 피봇값 이상이면 왼쪽으로 진행한다.
30,45,25,60,80,90,35,15,75,55
   ^L                ^R 

아직 R이 L의 오른쪽에 있는 상태이다. 여기서 L자리 값과 R자리값을 교체한다.

3. R이 아직 오른쪽에 있으므로 L/R자리의 값 교환
30,15,25,60,80,90,35,45,75,55
   ^L                ^R 

교체 후에 다시 L, R을 이동시켜 본다. L은 60의 자리까지, R은 25의 자리까지 이동할 수 있다.

4. 다시 L, R을 이동
30,15,25,60,80,90,35,45,75,55
      ^R ^L        

이제 더 이상 R이 L의 오른쪽에 있지 않다. (오른쪽에 있지 않다는 것은 둘이 같은 위치라는 것도 포함한다.) 이렇게되면 L/R의 값을 교환하는 대신, P와 R의 값을 교환한다. 교환을 마치면 R의 위치 왼쪽으로는 피봇보다 작거나 같은 값이, 오른쪽으로는 피봇보다 큰 값이 오게 된다. 전체 구간을 R의 위치 좌/우로 나눈다.

! 실제 코드는 양쪽 파티션을 동시에 처리하지 않지만 분량상 각 파티션을 동시에 정렬한다.

5. 왼쪽 파티션에서는 L/R이 같은 자리에 있으며, 움직일 조건이 안된다. 오른쪽도 각각 초기위치에서 움직일 수 없는 조건이다. 
25,15|30|60,80,90,35,45,75,55
   ^R|  |   ^L             ^R  

왼쪽 파티션에서는 L과 R이 같은 위치에서 움직일 수 없다. 그렇다면 피봇과 R의 값을 교환하고 다시 파티션한다. 오른쪽 파티션에서는 초기 위치에서 더 이상 움직일 수 없는데, R이 더 오른쪽에 있으므로 L/R 교환을 시행한다.

6. R값과 피봇값을 바꾸고, L/R값을 바꾼다.
15,25|30|60,55,90,35,45,75,80
   ^R|  |   ^L             ^R  

왼쪽 파티션은 모두 길이가 1으므로 정리됐고, 오른쪽에서 L과 R을 마저 이동하면서 L/R 교환을 반복해보자.

7. 이동
25|15|30|60,55,90,35,45,75,80
  |  |  |      ^L    ^R

8. 교체
25|15|30|60,55,45,35,90,75,80
  |  |  |      ^L    ^R

9. 이동
25|15|30|60,55,45,35,90,75,80
  |  |  |         ^R ^L

이제 다시 파티션을 할 시간이다. 나머지 구간에 대해서도 동일하게 처리해보자.

10. 파티션
25|15|30|35,55,45|60|90,75,80
  |  |  |   ^L ^R|  |   ^L ^R  

11. 다시 이동. 오른쪽 파티션에서는 L이 R과 같은 위치에 왔다.
25|15|30|35,55,45|60|90,75,80
  |  |  |^R ^L   |  |      ^L   

12. P/R 값 교체하고 파티션
25|15|30|35|55,45|60|80,75|90
  |  |  |  |   ^L|  |   ^L|   

13. 또 파티션해서 정렬완료
25|15|30|35|45|50|60|75|80|90
  |  |  |  |  |  |  |  |  |  

퀵소트는 이런식으로 피봇을 중심으로 값을 좌우로 가르고, 갈라진 파티션에 대해서 같은 동작을 반복해서 잘게 나누면서 정렬된 상태로 만든다.

구현하기

로직에 대해서 실제 예를 통해 이해를 구했으니, 이제 실제로 구현해야 할 시간이다. 퀵소트 자체는 배열내 특정 파티션을 정렬하는 함수를 구현하고, 배열 전체에 대해서 이 파티션함수를 호출하는 식으로 만들면 된다. 파티션 함수의 코드가 더 이상 마법처럼 보이지는 않을 것이다.

참고로 범위의 양 끝값으로 받은 인자를 함수 내에서 변형하지는 않는다. 파티션을 나눌 때 각각의 바깥쪽 끝 범위를 알고 있어야 하기 때문에 L/R 마커에 해당하는 변수를 따로 정의한다. 또 재귀호출을 하기 때문에 반드시 탈출 조건을 명시해야 한다. 여기서는 길이가 1 이하인 범위는 정렬된 것으로 간주하여 바로 리턴하면 된다.

def partition(arr, pivot, right):
  # 구간의 길이가 1이하이면 종료
  if right - pivot < 2:
    return

  # l, r은 움직여가면서 비교할 마커인덱스
  v = arr[pivot]
  l, r = pivot + 1, right
  
  while l < r:
    # L, R 이동
    while arr[l] < v and l < right:
      l += 1
    while arr[r] >= v and r > pivot:
      r -= 1
    # R이 오른쪽에 있다면 L/R 교환
    if l < r:
      arr[l], arr[r] = arr[r], arr[l]

   # P/R 교환하고 파티션
   arr[pivot], arr[r] = arr[r], arr[pivot]
   partition(arr, pivot, r-1)
   partition(arr, l, right)

파티션 함수를 작성했으므로 quick_sort() 함수는 배열과 양끝 위치를 포워딩해주는 것으로 구현하면 된다.

def quick_sort(arr):
  partition(arr, 0, len(arr)-1)

그외에 몇 가지 퀵소드에 대해서 알아두면 좋은 점

  1. 퀵소트는 소모하는 자원대비 좋은 성능으로 주목받고 있지만, 최악의 경우에는 성능이 무척 저하된다. 특히 이미 정렬된 배열을 정렬할 때가 그렇다. 상대적으로 데이터가 정렬된 상태에 가까우면 퀵소트의 효율을 떨어진다.
  2. 그런데 ‘평균적으로 가장 좋은 효율을 보인다’고 하는 것이 반드시 실제 사용에서 가장 좋은 성능을 내는 것은 아니다. 현실의 자료에서 많은 경우, 데이터는 부분적으로 정렬된 상태인 경우가 많으며 완전히 뒤섞인 상태로 존재하는 경우가 더 찾기 힘들다
  3. 제자리 정렬이 항상 좋은 것은 아니다. 데이터가 아주 큰 경우 메모리에 모두 올리지 못하는 경우도 있다. 이 경우에는 병합정렬과 퀵소트를 혼합하는 방식을 사용할 수 있다. 데이터를 로드 가능한 크기로 잘게 나눈다음, 각 조각을 퀵소트로 정렬하여 저장하고 다시 이들을 병합정렬을 사용해서 하나의 파일로 모으는 식으로 처리할 수 있다.