[정렬 알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)란, 피벗(pivot, 기준값)을 기준으로 큰 데이터와 작은 데이터를 찾아서 위치를 변경하는 정렬 방식이다. 

 

 

퀵 정렬(Quick sort) 동작 순서

오름차순으로 정렬하는 방법에 대해 알아보자.

1. 기준점이 될 index를 pivot으로 설정한다.(random value)
2. 새로운 리스트 2개를 만들고, pivot 값보다 작은 값들과 큰 값들을 모아서 각각 리스트에 담는다.
3. pivot값을 기준으로 작은 값이 모든 리스트는 왼쪽, 큰 값들의 리스트는 오른쪽으로 붙인다.
4. 1-3을 재귀로 반복한다.

 

퀵 정렬(Quick sort) 구현

퀵 정렬의 구현 방법은 아래와 같다.

def quick_sort(collection):
    """
    Examples:
    >>> quick_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]
    >>> quick_sort([])
    []
    >>> quick_sort([-2, 5, 0, -45])
    [-45, -2, 0, 5]
    """
    if len(collection) < 2:
        return collection
    pivot_index = 0  # Use random element as pivot
    pivot = collection[pivot_index]
    greater = []  # All elements greater than pivot
    lesser = []  # All elements less than or equal to pivot

    for element in collection[:pivot_index]:
        (greater if element > pivot else lesser).append(element)

    for element in collection[pivot_index + 1:]:
        (greater if element > pivot else lesser).append(element)

    return [*quick_sort(lesser), pivot, *quick_sort(greater)]


alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(quick_sort(alist))

 

 

퀵 정렬(Quick sort)의 시간 복잡도(Time Complexity)

우리가 알아보았던 선택정렬과 삽입정렬의 시간 복잡도는 O(N^2)로 느리다. 퀵 정렬의 시간 복잡도는 O(N log N)으로 정렬속도가 빠르다. 하지만, 모든 정렬 알고리즘이 장점만 있는 것은 아니다. 퀵 정렬의 단점은 리스트가 어느 정도 정렬 되어 상태라면 삽입 정렬이 더 빠르다. 정렬 정도에 따른 적절한 정렬 알고리즘을 고르자.

 

 

퀵 정렬과 병합 정렬

추가로 퀵 정렬과 병합 정렬의 차이에 대해 알아보자. 위의 코드를 확인해 보면, 퀵 정렬이 주어진 리스트를 분할하고 병합하는 것이 병합정렬과 비슷해 보인다. 그렇다면 차이점은 무엇일까? 병합정렬은 두 부분으로 나눈 후에 각 정렬이 끝난 후 병합하는 후처리 작업이 추가로 필요하다. 하지만 퀵 정렬은 기준값(pivot item)을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 위치시킨다. 따라서 분할하는 과정에서 pivot들이 자기 자리를 찾아가기 때문에, 분할 이후에 병합하는 과정에서 후처리 작업이 불필요하다.