Algorithm - Quick Sort

Quick Sort

분할 정복 알고리즘 중 하나로 Merge Sort와 유사하지만 Quick Sort는 리스트의 크기를 비 균등하게 분할하는 알고리즘

 

구현

• 리스트 안에서 한 요소를 선택(Pivot)
• Pivot 기준으로 Pivot보다 작은 요소들은 Pivot의 왼쪽으로 옮겨지고, Pivot보다 큰 요소들은 오른쪽으로 옮겨짐
• Pivot을 제외하고 왼쪽, 오른쪽 요소를 다시 Pivot을 정하고 Pivot 기준으로 두개의 리스트로 나누는 과정 반복

def quickSort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left, mid, right = [], [], []
    for num in arr:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            mid.append(num)
    return quickSort(left) + mid + quickSort(right)

 

 

공간 복잡도

별도의 추가 공간을 사용하지 않고 주어진 배열 원소의 위치만 바꾸기 때문에 O(1)

 

시간 복잡도

최악의 경우에는 Pivot을 맨 왼쪽으로 위치를 고정하게 된다면 2개의 리스트로 분할되지 않고 Pivot을 제외한 모든 배열을 정렬하는 경우가 발생하여 O(n^2)의 시간복잡도를 가짐

 

최선의 경우에는 Merge Sort와 동일하게 분할을 하는 과정에서 O(logn)의 시간이 필요하고, 결합하는 과정에서 배열에 들어있는 값들을 모두 비교해야 하므로 O(n)의 시간이 소요되므로 O(nlogn)의 시간복잡도를 가짐

 

장점

• 속도가 빠름 - O(nlogn)을 가지는 알고리즘 중에서도 가장 빠른 속도(Pivot을 정렬에 포함시키지 않기 때문)
• 추가 메모리 공간을 필요로 하지 않음

 

 단점

• 이미 정렬된 리스트는 불균형 분할로 인해 더 오래 걸릴 수 있음(Pivot이 최소 최댓값일 때)

 

공간 복잡도 최적화(in-place Sorting)

def swap(arr, p, r):
    tmp = arr[p]
    arr[p] = arr[r]
    arr[r] = tmp

# pivot 왼쪽으로 값 이동,
def partition(arr, left, right):
    pivot = arr[(left + right) // 2]
    
    # right 값과 pivot 값을 교환
    swap(arr, (left + right) // 2, right)
    
    # 왼쪽에 pivot 보다 작은 값 이동시키기
    idx = left
    for i in range(left, right):
        if arr[i] < pivot:
            swap(arr, i, idx)
            idx += 1
    
    # 다시 right 값(원래 pivot값)과 idx를 교환  
    swap(arr, right, idx)
    return idx

# pivot을 기준으로 왼쪽, 오른쪽으로 나눔
def quickSort(arr, left, right):
    if left < right:
        pivot = partition(arr, left, right)
        quickSort(arr, left, pivot - 1)
        quickSort(arr, pivot + 1, right)


arr = [15, 4, 3, 7, 22, 43, 6, 2]
quickSort(arr, 0, len(arr) - 1)
print(arr)

 

Merge Sort와 차이점

• Merge Sort는 분할 후 병합 시점에서 정렬을 실행하는 과정이고, Quick Sort는 Pivot을 기준으로 분할하는 시점에서 정렬을 진행하는 과정
• Merge Sort는 Stable정렬에 속하고, Quick Sort는 Unstable 정렬에 속함