Python으로 알고리즘 공부 02. 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort) 파이썬으로 구현

• 퀵 정렬은 분할 정복 알고리즘의 좋은 예이다.

• 리스트 중 하나를 pivot으로 정하고, pivot보다 작은 아이템은 왼쪽, pivot보다 큰 아이템은 오른쪽으로 보내면서 pivot의 자리를 확정한다.

• 그리고 왼쪽 리스트와 오른쪽 리스트에 대해서 재귀형식으로 진행.

• 평균 시간복잡도는 O(n*log n), 최악의 시간복잡도는 O(n^2)

def quick_sorted(arr):
    if len(arr) > 1:
        pivot = arr[len(arr)-1]
        left, mid, right = [], [], []
        for i in range(len(arr)-1):
            if arr[i] < pivot:
                left.append(arr[i])
            elif arr[i] > pivot:
                right.append(arr[i])
            else:
                mid.append(arr[i])
        mid.append(pivot)
        return quick_sorted(left) + mid + quick_sorted(right)
    else:
        return arr
        
arr = [3, 5, 1, 2, 9, 6, 4, 7, 5]
print(quick_sorted(arr))

• 퀵 정렬에서 pivot의 위치를 처음으로 하거나 마지막으로 하거나 상관은 없다. 그러나 최악의 경우가 될 가능성을 줄이기 위해서는 pivot의 위치를 무작위로 추출하는 것이 좋다.