[정렬 알고리즘] - Quick Sort

merge sort와 비슷하게 분할 정복 방법으로 정렬하는 방식이다. merge sort와는 다르게 퀵 정렬에서는 부분 리스트를 분할할때 비균등하게 분할한다. 분할시 리스트 안에 있는 한 요소를 pivot으로 선택한뒤 pivot보다 작은 원소들은 왼쪽으로 큰 원소들은 오른쪽으로 분할한다. 이 상태에서 pivot을 제외한 왼쪽 리스트와 오른쪽 리스트들을 계속해서 분할 정복 방법으로 정렬해나간다.

 

 

QuickSort Animation

 

구현

(업로드 예정)

def partition(arr, low, high):
    i = (low-1) #작은 원소들의 끝
    pivot = arr[high]

    for j in range(low,high):
        if arr[j] <= pivot:
            i+=1
            arr[i], arr[j] = arr[j], arr[i] #swap
    arr[i+1], arr[high] = arr[high], arr[i+1] #중간에 피봇을 넣는다
    return i+1

def quickSort(arr, low, high):
    if len(arr) == 1 :
        return arr
    if low < high:
        pIdx = partition(arr, low, high)
        quickSort(arr, low, pIdx-1)
        quickSort(arr, pIdx+1, high)

arr = [1,2,5,4,-1,-2,3]
quickSort(arr, 0, len(arr)-1)
print(arr)

시간 복잡도 분석

리스트의 분할이 항상 리스트의 가운데에 이루어진다고 할때 n개의 요소를 가진 리스트는 $n/2, n/4 , n/8$, ... , $n/2^k$ 의 크기로 나눠진다. $n/2^k = 1$ 일 때까지 나누어지므로, $k=log_2n$ 번의 연산이 수행된다. 각각의 depth에서 평균 n번 정도의 비교 연산이 수행되므로 $O(Nlog_2N)$의 복잡도를 가지는 알고리즘이다.

참고

퀵 정렬에서 최악의 경우 리스트가 계속해서 불균형하게 나눠지는 경우이다. 예를들어, 이미 정렬된 리스트에서 퀵 정렬을 실행할때 불균형 분할이 계속 이뤄진다. 이때 n번의 depth가 생기게 되고 각 depth 에서 n번의 비교 연산이 수행되므로 최악의 경우 $O(N^2)$의 시간 복잡도를 가지게 된다.

그러나 평균 $O(Nlog_2N)$의 복잡도를 가지는데 이는 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환하기 때문이다. 또한 한번 결정된 pivot들이 나머지 연산에서 제외되는 특징에 기인한다고 보인다.

• 불균등 분할을 방지하기 위해 pivot을 선택할때 중간값을 pivot으로 선택하는 방법이 많이 사용한다.
• Java의 Arrays.sort()나 Python의 list.sort() 함수는 퀵 정렬을 기본으로 한다.