[425] 퀵 정렬(Quick Sort)

1. 퀵 정렬 개념

영국의 컴퓨터 과학자 토니 호어(Charles Antony Richard Hoare)가 1959년 고안한 정렬 알고리즘입니다.

효율적인 알고리즘으로 빠르게 널리 사용되기 시작하였으며, 다양한 프로그래밍 언어와 시스템에서 기본 정렬 알고리즘으로 채택되었습니다.

 

퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하여 배열을 정렬합니다.

배열에서 한 원소를 선택합니다. 선택된 원소는 피벗(Pivot)이라고 부릅니다.

피벗을 기준으로 피벗보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 이동시킵니다.

이 과정은 투포인터를 사용하여 해결할 수 있습니다.

먼저 피벗을 제일 오른쪽 원소와 바꿉니다.(피벗을 제일 오른쪽에 위치시킵니다.)

투포인터(i, j)를 첫 번째 자리에 위치시킵니다.

한 포인터(i)를 순차적으로 탐색하며 피벗보다 작거나 같으면 다른 포인터(j)와 자리를 바꿉니다.

그리고 다른 포인터(j)는 한 칸 오른쪽으로 옮깁니다.

피벗을 기준으로 만들어진 왼쪽과 오른쪽의 부분 배열에 재귀적으로 위 과정을 반복합니다.

부분 배열이 하나 이하의 원소를 가지면 정렬이 끝납니다.

 

최악의 경우 시간 복잡도가 \(O(n^2)\)이지만 현실적인 데이터를 정렬할 때 다양한 피벗 선택 전략과 최적화 기법을 적용하여 제곱 시간이 걸릴 확률이 거의 없도록 설계할 수 있습니다.

 

피벗을 선택하는 방법에는 좌측 끝, 중앙, 우측 끝 등 여러가지 방법이 있습니다.

아래 예제에서는 좌측 끝, 중앙, 우측 끝 세 값 중에서 중간값을 선택하는 중위법을 사용하겠습니다.

 

https://ko.wikipedia.org/wiki/퀵_정렬

퀵 정렬 - 위키백과, 우리 모두의 백과사전

2. 퀵 정렬 예제

3. 퀵 정렬 코드

nums = [9, 3, 8, 2, 5, 1, 7, 4, 6]

def find_pivot(left, right): # 피벗을 중위법으로 결정하는 코드
    mid = (left+right)//2
    if nums[left] >= nums[mid]:
        if nums[mid] >= nums[right]:
            return mid
        if nums[left] <= nums[right]:
            return left
        return right
    if nums[left] >= nums[right]:
        return left
    if nums[mid] >= nums[right]:
        return right
    return mid

def quick_sort(left, right, nums):
    if left >= right: # 부분 배열의 크기가 1 이하이면 종료
        return
    pivot = find_pivot(left, right)
    
    # 피벗을 제일 오른쪽 원소와 바꿉니다.
    nums[pivot], nums[right] = nums[right], nums[pivot]
    
    # 투포인터 기법으로 피벗을 기준으로 더 작거나 같은 값은 왼쪽, 더 큰 값은 오른쪽으로 나눕니다.
    j = left
    for i in range(left, right+1):
        if nums[i] <= nums[right]:
            nums[i], nums[j] = nums[j], nums[i]
            j += 1
    
    # 재귀적으로 부분 배열을 다시 반복합니다.
    quick_sort(left, j-2, nums) # 왼쪽 부분 배열
    quick_sort(j, right, nums) # 오른쪽 부분 배열

quick_sort(0, len(nums)-1, nums)
print(nums)
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

4. 퀵 정렬 장점

퀵 정렬은 평균 \(O(n\log{n})\)의 시간 복잡도를 가집니다. 그러나 같은 시간 복잡도를 가지는 다른 정렬 알고리즘 보다도 더 빠르게 동작합니다.

제자리 정렬(In-place Sorting)이기 때문에 추가적인 메모리 공간을 거의 사용하지 않습니다.(재귀 호출로 인해 \(O(\log{n})\)의 공간 복잡도를 가집니다.)

대부분의 실제 데이터에서 우수한 성능을 보여주어 다양한 시스템에서 폭넓게 사용됩니다.

5. 퀵 정렬 단점

피벗 선택이 잘못되는 경우(이미 정렬된 배열에서 첫 번째나 마지막 원소를 피벗으로 선택하는 경우), 최악의 경우 시간 복잡도가 \(O(n^2)\)으로 떨어질 수 있습니다.

퀵 정렬은 안정적인 정렬이 아니므로 동일한 값을 가지는 원소의 상대적 순서가 바뀔 수 있습니다.

배열의 크기가 큰 경우, 재귀 호출의 깊이가 깊어져 스택 오버플로우가 발생할 수 있습니다.

6. 정렬 알고리즘 시간 복잡도 비교

정렬 알고리즘	최악(Worst)	최선(Best)	평균(Average)
버블 정렬(Bubble Sort)	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)
선택 정렬(Selection Sort)	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)
삽입 정렬(Insertion Sort)	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)
퀵 정렬(Quick Sort)	\(\boldsymbol{O(n^2)}\)	\(\boldsymbol{O(n\log{n})}\)	\(\boldsymbol{O(n\log{n})}\)
병합 정렬(Merge Sort)	\(O(n\log{n})\)	\(O(n\log{n})\)	\(O(n\log{n})\)
힙 정렬(Heap Sort)	\(O(n\log{n})\)	\(O(n\log{n})\)	\(O(n\log{n})\)
기수 정렬(Radix Sort)	\(O(n)\)	\(O(n)\)	\(O(n)\)
계수 정렬(Counting Sort)	\(O(n)\)	\(O(n)\)	\(O(n)\)