퀵 정렬 알고리즘은 정렬 대상을 분할하여 해결하는 알고리즘입니다. 하나의 기준값(pivot)을 정해서 정해진 기준값을 기준으로 분류하는데 아래 처럼 여러가지 방법이 있습니다.

  1. 항상 첫번째 요소를 기준값으로 선택한다.
  2. 항상 마지막 요소를 기준값으로 선택한다.
  3. 무작위 요소를 기준값으로 선택한다.
  4. 가운데 요소를 기준값으로 선택한다.

그리고 퀵 정렬의 핵심은 분류(partition)입니다. 분류는 배열과 기준 값이 주어지면 기준값 보다 작은값의 요소는 앞쪽에 큰 값의 요소들은 기준값보다 뒤쪽에 위치하도록 해야하며 이러한 작업은 선형시간(linear time)안에 이루어져야 합니다.

분류(partition) 알고리즘

분류 알고리즘은 다양한 방법이 있을 수 있지만 그 중 하나인 왼쪽끝의 요소부터 모든 요소를 기준값과 비교해 작거나 같은 값만 왼쪽으로 위치를 변경하는 방법으로 구현해보겠습니다.

def partition(arr, low, high):

    # 인덱스: 처음에는 low 보다 작은 값으로 초기화
    # 정렬값보다 작은 값의 위치를 좌측으로 변경시키기 위한 위치 값 인덱스임.
    i = low - 1

    # 기준값이자 올바른 위치로 정렬할 값
    pivot = arr[high]

    for j in range(low, high):

        # 만약 현재 요소가 기준 값보다 작다면
        if arr[j] < pivot:

            # 값을 정렬하기 위해 인덱스를 1 증가
            i = i + 1

            # 인덱스의 위치값과 현재 요소의 값의 위치 교환
            arr[i], arr[j] = arr[j], arr[i]

    # 모든 분류가 완료되면 마지막 인덱스 바로 뒤의 값과 기준값의 위치 교환
    arr[i + 1], arr[high] = arr[high], arr[i + 1]

    # 기준값의 최종 변경된 위치 값을 리턴
    return i + 1

분류가 완료되면 기준값보다 왼쪽에는 모두 작은 값이 위치해있으므로 가장 마지막 인덱스(기준값보다 작은 값들의 마지막 인덱스)의 다음 인덱스(+1)이 기준값이 올바르게 정렬된 위치가 됩니다. ( 주의할 점은 기준값보다 작은 요소들까지 올바르게 정렬된 게 아니라 기준값만 정렬된 것입니다.)

분류가 처음 실행되는 시점의 예시를 그림과 함께 살펴보며 상세하게 이해해보겠습니다.

분류(partition) 작업 예시
분류(partition) 작업 예시

분류 함수를 실행하는 경우 아래의 순서를 따라 기준값이 올바른 위치로 이동됩니다.

  1. j = 0, i = -1
    0번 요소(20)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i 를 1 증가시키고 i번 요소와 0번 요소의 위치를 교환
    => arr[-1+1], arr[0] = arr[0], arr[-1+1]
    => arr[0], arr[0] = arr[0], arr[0]
  2. j = 1, i = 0
    1번 요소(80)이 기준값(70)보다 크므로 무시
  3. j = 2, i = 0
    2번 요소(50)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i를 1 증가시키고 i번 요소와 2번 요소의 위치를 교환
    => arr[0+1], arr[2] = arr[2], arr[0+1]
    => arr[2], arr[1] = arr[1], arr[2]
  4. j =3, i = 1
    3번 요소(40)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i를 1 증가시키고 i번 요소와 3번 요소의 위치를 교환
    => arr[1+1], arr[3] = arr[3], arr[1+1]
    => arr[2], arr[3] = arr[3], arr[2]
  5. j = 4, i = 2
    4번 요소(30)이 기준값(70)보다 작으므로 좌측 최종 인덱스 i를 1 증가시키고 i번 요소와 4번 요소의 위치를 교환
    =>arr[2+1], arr[4] = arr[4], arr[2+1]
    =>arr[3], arr[4] = arr[4], arr[3]
  6. 모든 요소를 순회하였으므로 최종적으로 기준값(70)보다 작은 값들이 arr[0] ~ arr[i] 위치에 존재하게 된다.
    이제 기준값은 arr[i+1] 위치(작은값들 바로 뒤)가 올바른 위치이므로 arr[i+1] 과 arr[high] 요소를 교환한다
    ( 여기서 i는 5번 순서를 거쳐 최종적으로 3(2+1) 이 된 상태. )
    => arr[3+1], arr[5] = arr[5], arr[3+1]
    => arr[3], arr[5] = arr[5], arr[3]
  7. 기준값(70)은 기준값보다 작은 요소들의 바로 뒤의 위치로 올바르게 이동되었으며
    함수는 기준값이 이동한 올바른 위치 인덱스 i + 1 을 리턴하며 종료한다.

결국, 퀵 정렬은 분류 작업을 모든 요소에 반복하며 정렬하는 방법이 되는 것입니다.

최종 퀵 정렬 구현 코드

def quick_sort(arr, low, high):

    if low < high:
        # pi는 arr[high]가 파티션 처리 후 올바르게 정렬된 위치 인덱스(즉 arr[pi]는 올바른 위치에 정렬된 요소)
        pi = partition(arr, low, high)

        # 배열의 기준값 이전(좌측) 요소와 이후(우측) 요소들을 분리해서 정렬한다.
        # partition 처리를 재귀적으로 호출.
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

if __name__ == '__main__':
    arr1 = [20, 80, 50, 40, 30, 70]
    quick_sort(arr1, 0, len(arr1) - 1)
    print("Sorted array is:", arr1)

# 결과: Sorted array is: [20, 30, 40, 50, 70, 80]

마치며

마지막으로 퀵 정렬의 특징에 대해 살펴보겠습니다.

  • 시간복잡도
    최상의경우: \(O(n\log_2{}n)\)
    최악의경우: \(O(n^2)\)
  • 공간복잡도
    \(O(n\log_2{}n)\)
  • 불완전 정렬 ( unstable sort )
    기존의 키 값이 유지되지 않으므로 키값을 유지해야 하는경우에는 사용하면 안된다.
  • 정렬된 리스트에서의 속도 저하
    정렬된 리스트에 대한 퀵 정렬은 수행 시간이 더 늘어날 가능성이 있다.

이상으로 퀵정렬에 대해 알아보았습니다. 감사합니다.