[Algorithm] 퀵 정렬(Quick sort) 알고리즘

Quick sort

Idea

퀵 정렬은 기본적으로 분할 정복 (Devide and Conquer) 기법과 재귀를 이용한 정렬 알고리즘입니다. Pivot이라는 것을 사용하여 정렬의 기준을 정하게 됩니다. 그리고 그 pivot을 기준으로 “작은 group”, “큰 group”을 나누고, 분할 정복 기법을 이용하여 각각을 해결하는 방식입니다.

6 1 5 11 16 [7] 10 13

위와 같은 숫자 배열을 정렬하고자 할 때, 아무 값이나 pivot으로 선정합니다. 저는 7을 선정하였습니다. pivot을 선정하면, 해당 pivot을 기준으로 작은 값들과 큰 값들을 분류하여 각각 왼쪽, 오른쪽에 위치시킵니다.

6 1 5 [7] 11 16 10 13

그럼, [6,1,5]는 작은 group, [11,16,10,13]은 큰 group이 됩니다. 그럼, 7이라는 pivot은 이제 위치가 고정되게 됩니다. 즉, 정렬이 완료된 것이죠.

이제 각 group에서 pivot을 다시 선정하고, 똑같이 pivot을 기준으로 group을 나눕니다.

작은 group: 임의로 5을 pivot으로 선정

6 1 [5] -> 1 [5] 6

큰 group: 임의로 13을 pivot으로 선정
11 16 10 [13] -> 11 10 [13] 16

여기서 잠시 중간 점검을 하면 아래와 같습니다.

1 5 6 7 11 10 13 16

그럼, 1-5-6-7 까지는 정렬이 완료된 것을 볼 수 있습니다. 이는, 작은 group에서 더 이상 sub problem으로 분할할 수 없기 때문입니다.

과정을 정리하면 아래와 같습니다.

1. pivot을 정한다.
2. pivot보다 큰 값은 오른쪽에, pivot보다 작은 값은 왼쪽에 둔다.
3. pivot을 기준으로 작은 group, 큰 group을 다시 1번 과정부터 더 이상 분할할 수 없을 때까지반복한다.

 

Code (재귀 사용) - 비효율적

def quick_sort(arr):
    if len(arr) <= 1: # 더 이상 분할할 수 없는 경우
        return arr

    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []

    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)

		# 각 group에 대해 재귀 호출
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr) 

 

Code (partition) - 효율적

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)

 

Time complexity

• 쿽 정렬의 성능은 pivot 값을 어떻게 선택하느냐에 크게 달라질 수 있습니다.
• Best Case: pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되는 경우 → O(nlog(n))의 시간 복잡도를 가진다.
• Worst Case: pivot 값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우는 경우 → O(n^2)의 시간 복잡도를 가진다.