[파이썬 자료구조] 퀵정렬

정렬 중에서  퀵정렬에 대해서 알아보겠습니다. 2가지의 방식이 있습니다.

방법1.

L은 피벗보다 작은 집단, G는 피벗보다 큰 집단

1단계. 입력된 임의의 원소를 피벗으로 선택합니다. 피벗은 기준이 되는 원소입니다.

2단계. 피벗을 기준으로 작은 원소들, 피벗과 같은 원소들, 피벗보다 큰 원소들로 나눕니다.

3단계. 재귀적으로 정렬하고 크기순으로 놓으면 끝

파이썬으로 간단히 구현해보면

def quick_sort(S):
    if len(S) < 2:
        return S
    pivot = random.choice(S)
    L = [x for x in S if x < pivot]
    E = [x for x in S if x == pivot]
    G = [x for x in S if x > pivot]
    return quick_sort(L) + E + quick_sort(G)

def quick_sort(S, a, b):
    if a >= b:
        return
    pivot_idx = random.randint(a, b)
    S[pivot_idx], S[a] = S[a], S[pivot_idx]
    pivot = S[a]
    left = a+1
    right = b
    while left <= right:
        while left <= right and S[left] < pivot:
            left += 1
        while left <= right and pivot < S[right]:
            right -= 1
        if left <= right:
            S[left], S[right] = S[right], S[left]
            left, right = left + 1, right - 1
    S[right], S[a] = S[a], S[right]
    quick_sort(S, a, right - 1)
    quick_sort(S, right + 1, b)

S는 리스트이고 a와b는 각각 리스트의 양쪽 index입니다.

랜덤인트로 피벗을 정하고 피벗을  맨왼쪽으로 보내줍니다.

그리고 위에서 설명한 방식으로 진행됩니다.

퀵정렬의 수행시간

최선의 경우는 랜덤으로 뽑은 피벗이 항상 중간값을 갖는 경우입니다.

수행시간 T(n) = 2*T(n/2) + cn 

위에서 설명한 것처럼 리스트를 두개로 나누기 때문에 2*T(2/n)이 나온거고 cn은 피벗과 비교하는 시간입니다.

계속 2개씩 나눠지기 때문에 최대 log(n)번 나눌 수 있습니다. (이진트리)

따라서 k= log(n) 이므로 O(nlogn)의 수행시간을 가집니다.

최악의 경우는 피벗을 뽑을때마다 최솟값이나 최대값인 경우입니다.

한 쪽으로 기울어진 트리가 만들어지게 됩니다. 따라서 n(n+1)/2 -> O(n^2)의 수행시간이 걸립니다.

따라서 Big-O 표기법으로 시간복잡도는 O(n^2)입니다.