[알고리즘] Quick Sort

Quick Sort

Divide and Conquer(분할정복) 방법을 사용

기준 데이터인 Pivot을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘

---

Process

1. 기준 데이터(Pivot)를 고른다

2. 피벗 앞에는 피벗보다 값이 작은 데이터, 피벗 뒤에는 피벗보다 값이 큰 데이터들이 오도록 배열을 둘로 나눈다

    이 때 피벗값은 위치가 정해진다.

3. 분할된 두개의 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다

---

Code

numbers = []
length = 100

for i in range(length, 0, -1):
    numbers.append(i)


def quickSort(start, end):
    global numbers

    if start >= end:
        return

    pivot = start
    left = start + 1
    right = end

    while left <= right:
        # left 는 pivot 보다 큰 값 탐색
        while left <= end and numbers[left] <= numbers[pivot]:
            left += 1
        # right 는 pivot 보다 작은 값 탐색
        while right > start and numbers[right] >= numbers[pivot]:
            right -= 1

        # 엇갈린 경우 작은 데이터와 Pivot 교체
        if left > right:
            numbers[right], numbers[pivot] = numbers[pivot], numbers[right]
        else:   # 엇갈리지 않았다면 left 와 right 교체
            numbers[left], numbers[right] = numbers[right], numbers[left]

    quickSort(start, right - 1)
    quickSort(right + 1, end)

quickSort(0, length - 1)


print(numbers)

---

Time Complexity

최선의 경우 분할이 절반씩 일어난다면 

비교 시간복잡도는 O(log₂N), 각 순환 호출 단계의 비교 연산은 O(N)으로 O(Nlog₂N) 이다

 

이미 오름차순 혹은 내림차순 정렬된 경우가 최악의 경우이며

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2 이므로 O(N²) 이다

 

---

Space Complexity

정렬하고자하는 배열안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다 (in-place sorting)

따라서 O(N) 이다

---

C, JAVA, PYTHON 의 표준 정렬 라이브러리는 Quick Sort, Merge Sort 의 아이디어를 채택한 하이브리드 방식의 정렬 알고리즘을 사용한다

pivot 값을 기준으로 swap 되는 연산을 통해 같은 값을 가지는 데이터의 인덱스가 변경될 수 있으므로 unstable sorting 이다