[핵심 알고리즘 정리] 퀵소트

보통 내부 라이브러리는 퀵소트와 삽입 정렬을 믹스해서 만든 TIM SORT 라는 녀석으로 구현되어 있는 것으로 안다.

퀵 소트를 직접 구현할 일은 거의 없지만

문제의 구현 아이디어가 비슷하게 출제되는 경우도 있으므로

여러번 봐두면 도움이 된다.

 

쉬운 버전의 구현과 어려운 버전의 구현을 동시에 공부해보자.

 

# https://www.daleseo.com/sort-quick/ 참고 URL
# 시간복잡도 O(NolgN)
# 거의 모든 정렬 중 제일 좋음. 기본으로 사용
# 최악이 N이라 안되는 경우 병합 정렬을 사용
# 쉽게 구현하기
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left, equal, right = [], [], []  # 오름차순 정렬
    for num in arr:
        if num < pivot:  # 내림차순 시 이부분 바꿔줌
            left.append(num)
        elif num > pivot:  # 내림차순 시 이부분 바꿔줌
            right.append(num)
        else:
            equal.append(num)
    return quick_sort(left) + equal + quick_sort(right)


# 해당 구현은 쉽지만, 매번 새로운 리스트를 리턴하여 메모리 효율성이 떨어짐.
# 구현이 약간 더 어려운 in-place 정렬

def quick_sort2(arr):
    def real_quick_sort(l, h):
        if h <= l:
            return
        # 가운데의 위치를 찾아 해당 위치에 고정하고
        # 좌 우에서 고정할 위치를 하나씩 찾음
        m = partition(l, h)
        real_quick_sort(l, m - 1)
        real_quick_sort(m, h)

    def partition(l, h):
        pivot = arr[(l + h) // 2]
        while l <= h:
            # 피벗과 같거나 큰 녀석을 찾음
            while arr[l] < pivot:
                l += 1
            # 피벗보다 작거나 같은 녀석을 찾음
            while arr[h] > pivot:
                h -= 1
            # l<=h 이면 정렬이 안된 상태이므로, 둘을 스왑함
            if l <=h:
                arr[l], arr[h] = arr[h], arr[l]
                l += 1
                h -= 1
        return l
    return real_quick_sort(0, len(arr) - 1)