NeetCode 12번 알고리즘: Quick Sort

니트코드 링크: https://neetcode.io/courses/dsa-for-beginners/11

 

Algorithm

Pivot을 정하는 법을 바꾸면 더 효율적인 알고리즘도 가능하다. (worst case 완화)

Code 

# Implementation of QuickSort
def quickSort(arr: list[int], s: int, e: int) -> list[int]:
    if e - s + 1 <= 1:
        return arr

    pivot = arr[e]
    left = s # pointer for left side

    # Partition: elements smaller than pivot on left side
    for i in range(s, e):
        if arr[i] < pivot:
            tmp = arr[left]
            arr[left] = arr[i]
            arr[i] = tmp
            left += 1

    # Move pivot in-between left & right sides
    arr[e] = arr[left]
    arr[left] = pivot
    
    # Quick sort left side
    quickSort(arr, s, left - 1)

    # Quick sort right side
    quickSort(arr, left + 1, e)

    return arr

 

Complexity

Time Complexity

Average : O(nlogn)

Worst Case: O(n^2)   #예시 :  [1,2,3,4,5] 또는 [5,4,3,2,1] 일 때. 즉 sorted 되어 있어도 worst case

 

Memory Complexity

새로운 배열을 생성하지 않고 기존 배열에서 모두 해결하기 때문에 O(1)이다.

Merge Sort가 O(n)이었는데 메모리 면에선 Quick Sort가 우수하다. 

Stabiltiy

Not Stable 

swap 하다보면 relative position 섞일 수 있음.