3.1 Sorting - 3.1.5 Quick Sort

CS - 3. Common Algorithms - 3.1. Sorting - 3.1.5 Quick Sort

 

💡Quick Sort is a divide and conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

퀵 정렬은 분할 및 정복 알고리즘입니다. 이 알고리즘은 요소를 피벗으로 선택하고 선택된 피벗을 중심으로 주어진 배열을 분할합니다. 다양한 방식으로 피벗을 선택하는 여러 가지 버전의 퀵 정렬이 있습니다.

 

퀵정렬(Quick Sort)는 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘입니다.

이 방법은 주어진 배열을 두개의 부분 배열로 분할하고, 각각을 별도로 정렬하는 방식으로 작동합니다.

 

퀵 정렬의 동작 과정은 다음과 같습니다.

 

1. 배열에서 하나의 원소를 고릅니다. 이를 피봇(pivot)이라 합니다.

2. 피봇보다 작은 원소들을 피봇의 왼쪽으로, 큰 원소들은 오른쪽으로 이동시킵니다.

이를 분할(partition)이라고 합니다.

3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복합니다.

 

 

In Python

 

파이썬에서 퀵정렬을 구현해 보겠습니다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + middle + quick_sort(greater)

 

퀵 정렬은 평균적으로 O(log n) 의 시간 복잡도를 가집니다. 

그러나 최악의 경우 (이미 정렬된 배열 등) 에는 O(n^2)의 시간 복잡도를 가질 수 있습니다.

 

 

 

정리 & 활용

퀵 정렬은 대부분의 경우에 매우 효율적이며, 작은 배열에 대해서도 빠르게 동작하므로 다른 알고리즘과 결합하여 사용하기도 합니다.

주의할 점은, 피봇 선택에 따라 성능이 크게 달라질 수 있습니다.

일반적으로 중간값을 피봇으로 선택하면 효율적입니다.

 

또, 퀵 정렬은 추가 메모리를 거의 사용하지 않는다는 장점이 있습니다.

이는 정렬하려는 데이터가 매우 큰 경우에 유리합니다.

 

따라서 퀵정렬은 일반적인 목적의 정렬 알고리즘으로 자주 사용 되며,

특히 메모리가 제한적인 상황에서 유용하게 사용될 수 있습니다.

 

Appendix, 퀵 정렬은 왜 추가 메모리를 거의 사용하지 않을까? (+ in Python)

 

퀵 정렬이 추가 메모리를 거의 사용하지 않는 이유는 이 알고리즘이 '제자리 정렬(in-place sort)' 알고리즘 이기 떄문입니다.

제자리 정렬 알고리즘은 입력 배열 자체를 정렬하여 정렬된 결과를 반환하며, 이 과정에서 추과적인 저장 공간을 피룡로 하지 않습니다.

 

퀵 정렬에서는 피벗(pivot)을 선택하고, 피 벗을 기준으로 배열을 두 개의 부분 배열로 분할하는 과정이 진행됩니다.

이 분할 과정은 원래의 배열 내에서 진행되며, 새로운 배열을 생성하지 않습니다.

분할이 진행된 후에는 각 부분 배열에 대해 동일한 과정을 재귀적으로 반복하여 정렬을 완성합니다.

 

이렇게 원래의 배열 내에서 직접 원소들의 위치를 정렬하기 때문에,

퀵 정렬은 추가적인 메모리를 거의 필요로 하지 않습니다.

 

다만, 파이썬 같은 언어에서는 재귀호출에 대한 오버헤드나, 리스트 슬라이싱과 같은 작업으로 인해 실제로는 추가 메모리가 사용될 수 있습니다. 

 

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + middle + quick_sort(greater)

아까 위에서 파이썬에서 퀵정렬을 구현하였는데, 위 코드에서는

less, middel, greater 라는 피벗에 따라 분류한 새로운 리스트를 생성한다.

따라서 리스트 컴프리헨션을 사용해 새로운 리스트를 만들기에 추가적인 메모리를 사용하고 위 코드는 퀵 정렬의 제자리(in-place)특성을 벗어난다.

 

def partition(nums, low, high):
    # 피벗을 선택하고, 작은 원소와 큰 원소를 양쪽으로 분할합니다.
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1
        j -= 1
        while nums[j] > pivot:
            j -= 1
        if i >= j:
            return j
        # 피벗을 기준으로 작은 원소와 큰 원소를 교환합니다.
        nums[i], nums[j] = nums[j], nums[i]

def quick_sort(nums):
    # 퀵 정렬의 도우미 함수를 정의합니다.
    def _quick_sort(items, low, high):
        if low < high:
            # 피벗을 기준으로 분할된 지점을 구합니다.
            split_index = partition(items, low, high)
            # 분할된 두 부분을 재귀적으로 정렬합니다.
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)
    _quick_sort(nums, 0, len(nums) - 1)

# 테스트
nums = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
quick_sort(nums)
print(nums)  # [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

이 코드는 피벗을 선택하고, 배열 내에서 직접 위치를 변경하여 정렬을 수행하는 코드입니다.

 

 

메모리 사용량을 확인해보면

120 바이트를 원본메모리에 사용하고 새로운 리스트들을 활용하기에 메모리를 추가적으로 사용합니다.

 

아래의 코드는 리스트 내부에서 정렬을 하기에 (In-place sort) 추가적인 메모리 사용량이 없다고 생각됩니다.

(아직 메모리에 대한 이해가 부족하여, 연산에 필요한 메모리나 추가적인 공부후 추가 작성)