[탐색과 정렬] 퀵 정렬

퀵 정렬(Quick sort)

기준값과 비교하여 그룹을 나눈 후, 각각 재귀 호출하여 결과를 합치는 정렬 방식으로 분할 정복 알고리즘(Divide and conquer algorithm)의 하나이다. 아래 그림과 같은 방식으로 동작한다.

퀵 정렬은 얼마나 적절한 기준을 정하느냐에 따라 성능이 크게 좌우된다.

평균적인 계산 복잡도는 $$ \mbox{O}(n\log{n}) $$

 

 

코드 (캐시 사용)

def quick_sort(a):
    n = len(a)

    # 종료 조건
    if n <= 1:
        return a

    # 기준 값을 정하고 기준에 맞춰 그룹을 나누는 과정
    pivot = a[-1]  # 편의상 리스트의 마지막 값을 기준 값으로 정함
    g1 = []        # 그룹 1: 기준 값보다 작은 값을 담을 리스트
    g2 = []        # 그룹 2: 기준 값보다 큰 값을 담을 리스트

    for i in range(0, n - 1):  # 마지막 값은 기준 값이므로 제외
        if a[i] < pivot:       
            g1.append(a[i])    
        else:
            g2.append(a[i])   

    return quick_sort(g1) + [pivot] + quick_sort(g2) # 리스트 합치기​

 

 

코드 (캐쉬 미사용)

def partition(list, start, end):
    if end - start <= 0:
        return
        
    pivot = list[end]
    i = start
    
    for j in range(start, end):
        if list[j] < pivot:
            list[i], list[j] = list[j], list[i]
            i += 1
    list[i], list[end] = list[end], list[i]
    
    partition(list, start, i - 1)
    partition(list, i + 1, end)


def quick_sort(list):
    return partition(list, 0, len(list) - 1)​

partition 함수 동작 모습은 아래와 같다.

 

 

참고 문서

https://itstory.tk/entry/%ED%80%B5%EC%A0%95%EB%A0%ACQuick-Sort