정렬 알고리즘 - 퀵 정렬(Quick Sort)

분할 정복(Devide and Conquer) 기법과 재귀(Recursive) 알고리즘을 이용한 정렬 알고리즘입니다.

1. 피봇(pivot)이라고 불리는 임의의 기준값을 정합니다.
2. 피봇 값보다 작은 값들은 모두 왼편으로, 큰 값들은 모두 오른편으로 이동시킵니다(분할).
3. 왼편과 오른편 모두 앞과 동일한 방식으로 피봇을 정하고 값들을 이동시킵니다(재귀).
4. 더 이상 분할이 불가능할 때까지 반복합니다.

시간복잡도는 피봇을 어떻게 선택하느냐에 따라 달라집니다. 피봇을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되는 경우

**O(nlogn)**의 시간복잡도를 갖습니다. 하지만 피봇을 기준으로 분할 했을 때, 값들이 한 편으로 몰리는 경우 **O(n^2)**이 걸립니다.

 

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라,시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠릅니다.
• 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에,
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다.

단점

• 불안정 정렬(Unstable Sort) 입니다.
• 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸립니다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    less_arr, equal_arr, more_arr = [], [], []

    for num in arr:
        if num < pivot:
            less_arr.append(num)
        elif num > pivot:
            more_arr.append(num)
        else:
            equal_arr.append(num)

    return quick_sort(less_arr) + equal_arr + quick_sort(more_arr)

def quick_sort(arr, start, end):
    if start >= end:
        return
    pivot = start
    left, right = start + 1, end

    while left <= right:
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            arr[right], arr[left] = arr[left], arr[right]

    quick_sort(arr, start, right - 1)
    quick_sort(arr, right + 1, end)