[Algorithm] 1. Quick Sort(퀵 정렬)

Quick Sort의 정의

1. 분할 정복 알고리즘의 하나로, 평균적으로 빠른 시간 복잡도를 지닌다.

2. Pivot의 개념을 활용한다.

 

Quick Sort 과정

1. 리스트 안에 있는 한 요소를 선택한다.(임의로)

2. 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 옮긴다.

3. 피벗을 제외한 왼쪽, 오른쪽 리스트를 위와 같은 방법(1~2)으로 재정렬한다.

4. 분류된 리스트가 더 이상 분할되지 않을 때까지 반복한다.

   - 리스트의 크기가 0 or 1일 경우

 

Quick Sort 코드 1(기본)

def quicksort2(arr, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = 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[left], arr[right] = arr[right], arr[left]
    quicksort2(arr, start, right - 1)
    quicksort2(arr, right + 1, end)

Quick Sort 코드 2(파이썬 활용 1)

def quicksort1(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quicksort1(lesser_arr) + equal_arr + quicksort1(greater_arr)

Quick Sort 코드 3(파이썬 활용 2)

def quicksort3(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    tail = arr[1:]
    
    left = [x for x in tail if x <= pivot]
    right = [x for x in tail if x >= pivot]
    
    return quicksort3(left) + [pivot] + quicksort3(right)

시간 복잡도

1. 평균적으로 O(nlog₂n)의 시간복잡도를 가진다.

2. 하지만 pivot을 설정함에 있어 최악의 경우 O(n^2)의 시간복잡도를 가질 수도 있다.

  - pivot이 최대값 or 최소값으로 지정되어 분할이 되지 않을 때

 

장점

1. 다른 O(nlog₂n)의 시간복잡도를 가진 정렬 알고리즘과 비교해도 빠르다.

2. 정렬하고자 하는 배열 안에서 옮기는 것이기 때문에 다른 메모리 공간을 필요로 하지는 않는다.

 

단점

1. 불안정 정렬

2. 이미 정렬된 배열에 대해서는 오히려 시간이 더 오래 걸린다.

 

결론

1. 단점에 비해 활용성이 높기 때문에 파이썬의 list.sort()나 자바의 Arrays.sort() 내부적으로 Quick Sort를 사용하고 있다.