#04 퀵 정렬(Quick Sort)

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

퀵 정렬은 분할 정복을 통해 정렬을 수행하는 대표적인 정렬 알고리즘이다.

 

최선과 평균에서 시간 복잡도가 O(nlogn)으로 다른 정렬 알고리즘과 비교했을 때 가장 빠르다.

공간 복잡도도 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다.

- 하단에 pythonic 한 코드에서는 추가로 n의 공간을 사용하므로, O(2n)이다.

이미 오름차순, 내림차순으로 정렬되었을 때 O(n^2)이고, 또한 불안정 정렬이라는 단점이 존재한다.

 

def quick_sort(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 : # 서로 교차되었을 때(right의 값이 left의 값 보다 작음)
            # 작은 값과 피벗의 위치를 변경
            # 피벗 왼쪽은 피벗보다 작고 피벗 오른쪽은 피벗보다 큼
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            # 작은 데이터와 큰 데이터 위치 변경 - 불안정 정렬 이유
            arr[left], arr[right] = arr[right], arr[left]
    quick_sort(arr, start, right - 1) # 이상태 right index가 pivot의 위치 start ~ 피벗 -1
    quick_sort(arr, right + 1, end) # 피벗+1 ~ end
    
def pythonic_quick_sort(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 pythonic_quick_sort(left) + [pivot] + pythonic_quick_sort(right)

 

수행 시간 비교

테스트 케이스 N = 10000 -> (0 ~ 10000)까지의 숫자 random.shuffle 적용

 

quick sort

다른 정렬

오히려 pythonic 한 코드가 더 빨라서 의외였지만,

아마 비교연산을 더 많이 하는 것보다 객체 할당을 변경하고 해제하는 데에 시간이 더 소요돼서 그런다고 생각한다.

     - selection sort가 의외로 O(n^2) 중 빠른 이유가 가장 교환이 적게 발생해서 그러는 것이라는 비슷한 맥락의 추론

그리고 역시 정렬된 상태에서 quick sort는 다른 O(n^2) 연산들의 시간과 비슷하다.

 

객체 할당과 해제하는 것에 대해 헷갈리면 아래 포스팅을 참고하자.

2021.12.29 - [Comuter Science] - #2 python의 메모리 할당과 관리 (Everything is object in Python)

#2 python의 메모리 할당과 관리 (Everything is object in Python)