정렬 알고리즘(Sort Algorithm)의 퀵 정렬(Quick Sort) 개념 정리

들어가며

파이썬을 사용하는 경우 정렬해야 하는 상황에서 sort()를 사용하여 내부적인 정렬을 해주거나, sorted()를 사용하여 정렬된 새로운 값을 받도록 하는 경우가 많다.

def use_sort(arr: List) -> List:
    arr.sort()
    return arr

def use_sorted(arr: List) -> List:
    return sorted(arr)

이러한 정렬 함수가 내부적으로 어떻게 동작하는지 알기 위해서는 적어도 퀵 정렬 또는 병합 정렬 정도는 알고 있어야 한다고 한다. 따라서, 이번에는 퀵 정렬에 대해서 공부한 내용을 정리해보겠다.

퀵 정렬

퀵 정렬(Quick Sort)에서는 중심점(pivot)과 파티션(partition)이라는 개념이 존재하며, 이는 퀵 정렬의 동작 원리이기도 하다.

파티션은 중심점을 기준으로 나뉜 또 다른 그룹이라고 할 수 있는데, 자세한 개념은 예제를 통해 살펴보도록 하자.

예를 들어, 퀵 정렬을 통해 아래의 배열의 내부 요소들이 어떻게 정렬되는지 살펴보도록 하겠다.

[ 9, 5, 2, 3, 7, 8, 4 ]

중심점을 정한 후에는 배열의 모든 원소를 순회하는데, 이때 현재 위치의 요소와 중심점에 위치한 값의 크기를 비교한다.

중심점을 정하는 방법으로는 여러가지가 있을 수 있으나, 본 예제에서는 arr[1]을 중심점으로 정했다고 가정한다.

arr[1](5)를 기준으로 배열의 요소를 비교하기 위해 배열의 맨 끝에 위치한 값과 스왑(swap)해주고, 배열의 양 끝에 서로 다른 포인터를 지정하여 파티셔닝을 진행할 수 있도록 한다.

     ↔              ↔
[ 9, 4, 2, 3, 7, 8, 5 ]
  ↑              *

포인터(↑)가 가리킨 값은 중심점의 값보다 작은 경우에만 그대로 유지하고, 포인터(*)가 가리킨 값은 중심점의 값보다 큰 경우에만 그대로 유지한다고 생각하자. 즉, 위의 두 가지 조건이 모두 지켜지지 않은 상황에서만 서로의 값을 스왑할 수 있다. 이 조건이 언제 활용되는지는 뒤에서 자세히 살펴보도록 하자.

포인터(*)의 값(8)은 중심점의 값(5)보다 크므로 포인터를 한 칸 좌측으로 이동시킨다. 반면, 포인터(↑)의 값(9)는 중심점의 값(5)보다 크기 때문에 포인터(*)의 스왑이 가능한 상태가 된다. 그러나, 포인터(*)의 값은 중심점의 값(5)보다 크므로 스왑하지 않고, 현재 위치를 고수한다.

[ 9, 4, 2, 3, 7, 8, 5 ]
  ↑           *   

포인터(↑)는 우측으로만 이동 가능하고, 포인터(*)는 좌측으로만 이동 가능하다.

포인터(*)의 값(7)은 중심점의 값(5)보다 크므로 포인터를 한 칸 이동시키고, 포인터(↑)의 값(9)은 스왑이 가능한 상태이므로 현재 위치를 고수한다.

[ 9, 4, 2, 3, 7, 8, 5 ]
  ↑        *      

포인터(*)의 값(3)은 중심점의 값(5)보다 작으므로 스왑이 가능한 상태가 되었고, 포인터(↑)의 값(9)은 이전부터 스왑이 가능한 상태이므로 이 두 개의 값을 서로 스왑한다. 그리고, 모든 포인터를 한 칸씩 이동시킨다.

  ↔        ↔         
[ 3, 4, 2, 9, 7, 8, 5 ]
     ↑  *         

포인터(*)의 값(2)은 중심점의 값(5)보다 작으므로 스왑이 가능한 상태가 되었다. 반면, 포인터(↑)의 값(4)는 중심점(5)보다 작으므로 우측으로 한 칸 이동시킨다. 이때, 두 개의 포인터가 중첩되는데, 이 경우 포인터(↑)를 한 칸 더 이동시킨다.

[ 3, 4, 2, 9, 7, 8, 5 ]
        *  ↑       

두 개의 포인터가 역전되었으니, 포인터(↑)의 값(9)을 중심점의 값(5)과 스왑한다.

           ↔        ↔ 
[ 3, 4, 2, 5, 7, 8, 9 ]

지금까지의 상황을 이해했다면, 포인터(↑)의 좌측 값들은 중심점보다 작은 값을 의미하고, 포인터(*)의 우측에 위치한 값들은 중심점보다 큰 값을 의미한다는 것을 알 수 있다. 이 둘이 서로 역전하는 경우에는 더 이상 중심점보다 큰 값 또는 작은 값을 찾을 수 없다는 의미이므로 가장 최근에 이동시킨 포인터의 값과 중심점의 값을 스왑해주는 것이다.

그리고 현재 배열은 이전 중심점의 값(5)을 기점으로 하여 두 개의 파티션으로 분할되며, 각각의 파티션에서 정렬을 수행해주면 된다.

[ 3, 4, 2 ] + [ 5 ] + [ 7, 8, 9 ]

퀵 정렬은 중심점 위치, 포인터의 위치에 따라 속도가 달라질 수 있다.

중심점의 위치 : arr[-1]

중심점을 배열의 가장 마지막 원소로 정하는 경우가 있다. 이 경우 오히려 더 느린 동작으로 수행될 수 있다. 그 이유는 뒤에서 퀵 정렬의 시간 복잡도에 관련된 내용을 참고하면 되겠다.

포인터의 위치 : arr[0], arr[0]

두 개의 포인터를 왼쪽과 오른쪽 끝이 아닌 배열의 첫 번째 요소에 위치하도록 정하는 경우가 있다. 예를 들어, 아래와 같은 배열을 퀵 정렬로 정렬해보도록 하겠다.

[ 9, 5, 2, 3, 7, 8, 4 ]

이 방법에서도 두 개의 포인터를 사용하는데, 첫 번째 포인터(↑)는 스왑되었을 때에만 우측으로 한 칸 이동하고, 두 번째 포인터(*)는 값이 중심점보다 작은 경우 우측으로 계속 이동시킨다.

[ 9, 5, 2, 3, 7, 8, 4 ]
  ↑      
  *         

본 예제에서는 arr[-1](4)를 중심점으로 정했다고 가정한다.

포인터(*)의 값(9)이 중심점의 값(4)보다 크므로 해당 포인터를 우측으로 한 칸 이동시킨다.

[ 9, 5, 2, 3, 7, 8, 4 ]
  ↑  *    

포인터(*)의 값(5)이 중심점의 값(4)보다 크므로 해당 포인터를 우측으로 한 칸 이동시킨다.

[ 9, 5, 2, 3, 7, 8, 4 ]
  ↑     * 

포인터(*)의 값(2)이 중심점의 값(4)보다 작으므로 포인터(↑)의 값(9)과 스왑한 후 모든 포인터를 우측으로 한 칸 이동시킨다.

  ↔     ↔
[ 2, 5, 9, 3, 7, 8, 4 ]
     ↑     * 

여기서 눈치챘을 수도 있지만, 포인터(↑) 위치에서 스왑된 값(2)은 중심점보다 작은 값으로만 구성된다는 것을 알 수 있다.

포인터(*)의 값(3)이 중심점의 값(4)보다 작으므로 포인터(↑)의 값(5)과 스왑한 후 모든 포인터를 우측으로 한 칸 이동시킨다.

     ↔     ↔
[ 2, 3, 9, 5, 7, 8, 4 ]
        ↑     *

포인터(*)의 값(7)이 중심점의 값(4)보다 크므로 해당 포인터를 우측으로 한 칸 이동시킨다.

     ↔     ↔
[ 2, 3, 9, 5, 7, 8, 4 ]
        ↑        *

포인터(*)의 값(8)이 중심점의 값(4)보다 크므로 해당 포인터를 우측으로 한 칸 이동시킨다.

     ↔     ↔
[ 2, 3, 9, 5, 7, 8, 4 ]
        ↑           *

포인터(*)의 값(4)이 중심점에 위치하고 있으므로 포인터(↑)의 값(9)와 스왑한다.

        ↔           ↔
[ 2, 3, 4, 5, 7, 8, 9 ]

그리고 현재 배열은 이전 중심점의 값(4)을 기점으로 하여 두 개의 파티션으로 분할되며, 각각의 파티션에서 정렬을 수행해주면 된다.

[ 2, 3 ] + [ 4 ] + [ 5, 7, 8, 9 ]

퀵 정렬의 시간 복잡도와 공간 복잡도

퀵 정렬은 위에서 살펴본 바와 같이 새로운 메모리에 값을 할당하기 않으므로 공간 복잡도는 항상 O(1)이다. 반면, 시간 복잡도는 상황에 따라 크게 두 가지로 나뉜다. 앞서 살펴본 바와 같이 퀵 정렬은 중심점을 기준으로 두 개의 파티션으로 나누어지고, 각 파티션에서 퀵 정렬을 다시 수행하면 n × 2 개의 파이션으로 나누어진다. 즉, 퀵 정렬은 재귀적인(Recursive) 구조라는 것을 알 수 있다.

최적의 상황

퀵 정렬이 가장 빠르게 수행될 수 있는 상황은 배열의 평균값에 가까운 값이 중심점으로 지정될 때이다.

여기서 말하는 가운데 값이란, 배열에 존재하는 모든 원소의 평균 값과 가장 가까운 값을 말한다.

예를 들어, 다음과 같은 배열이 있고, 배열의 평균값(5.42)에 가장 가까운 5가 중심점으로 지정되었다고 가정해보자.

[ 9, 5, 2, 3, 7, 8, 4 ]

그리고 두 개의 파티션으로 나뉠 때까지 정렬했다고 가정했을 때, 나눠진 파티션은 다음과 같을 것으며, 이때 시간 복잡도는 O(N)이다.

[ 2, 3, 4 ] [ 5 ] [ 9, 8, 7 ]

편의상 나눠진 두 개의 파티션을 각각 A([2, 3, 4])와 B([9, 8, 7])이라고 하자. 첫 번째 중심점을 지정하였을 때와 마찬가지로 A에서는 평균값(3)에 가장 가까운 3을, B에서는 평균값(8)에 가장 가까운 8을 중심점으로 지정하고, 퀵 정렬을 수행하면 다음과 같이 정렬된다.

[ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 7 ] [ 8 ] [ 9 ] 

모든 파티션의 길이가 1이 되어 더 이상 퀵 정렬을 수행할 필요가 없기 때문에 정렬을 종료한다.

정렬이 완료되기까지 배열의 파티션이 총 두 번 나눠진 것을 확인할 수 있으며, 나눠진 파티션의 모든 요소를 반복하는 과정의 시간 복잡도는 O(log₂N)이라고 할 수 있다. 정리하자면, 중심점을 배열 요소의 평균값에 가까운 값으로 지정하는 경우, 시간 복잡도는 O(Nlog₂N)(O(N * log₂N))이다.

최악의 상황

이번에는 중심점을 배열의 최대값에 해당하는 값으로 지정하는 경우를 살펴보자. 마찬가지로 아래 배열에서 최대값(9)을 중심점으로 지정한 후 파티션이 나눠지는 과정을 살펴보겠다.

[ 9, 5, 2, 3, 7, 8, 4 ]

최초의 퀵 정렬이 수행되고 나면 다음과 같이 한 개의 파티션으로 나뉘게 된다.

[ 5, 2, 3, 7, 8, 4 ] [ 9 ]

이어서 위의 파티션에서 퀵 정렬을 계속해서 수행하면 다음과 같이 총 N번의 파티션 분할 과정을 거치게 된다.

[ 5, 2, 3, 7, 4 ] [ 8 ] [ 9 ]
[ 5, 2, 3, 4 ] [ 7 ] [ 8 ] [ 9 ]
[ 2, 3, 4 ] [ 5 ] [ 7 ] [ 8 ] [ 9 ]
[ 2, 3 ] [ 4 ] [ 5 ] [ 7 ] [ 8 ] [ 9 ]
[ 2 ] [ 3] [ 4 ] [ 5 ] [ 7 ] [ 8 ] [ 9 ]

즉, 배열에 N개의 요소가 존재할 때 N개의 요소를 N개의 파티션으로 나누어야 하므로 시간 복잡도는 O(N²)이다.

마치며

여기까지 오늘 공부한 내용을 정리해보았다. 퀵 정렬을 수행할 때 배열의 평균값에 가까운 값을 효율적으로 찾아낼 수 있다면 훨씬 빠른 정렬이 가능할 것으로 생각된다.

참고자료

• 코드없는 프로그래밍 - 코딩테스트, 기초, 퀵 정렬. quick sort. 퀵 소트