[Python3] QuickSort (퀵 정렬)

공부하다가 Python으로 퀵 정렬을 구현해 보았다. 단점은 이미 정렬된 상태에서 이렇게 양 극값을 Pivot으로 선택하는 경우 시간이 O(n^2) 소요된다는거...

#!/usr/bin/env python3

def quick_sort(arr, start, end):
    if start >= end:
        return arr
    pivot = start
    left = start + 1
    right = end
    while True:
        while left <= right and arr[left] <= arr[pivot]:
            left += 1
        while left <= right and arr[pivot] <= arr[right]:
            right -= 1
        if left > right:
            arr[pivot], arr[right] = arr[right], arr[pivot]
            pivot = right
            break
        arr[left], arr[right] = arr[right], arr[left]
    quick_sort(arr, start, pivot-1)
    quick_sort(arr, pivot+1, end)
    return arr


# 테스트 출력 코드
from random import shuffle

test_case = list(range(1, 101))
shuffle(test_case)
print('Before Sort :\n', test_case)
quick_sort(test_case, 0, 99)
print('After Sort :\n', test_case)