퀵소트

피봇을 중심으로 하여 피봇값보다 작은 수는 비봇 앞으로, 큰 수는 피봇 뒤로 보내며 이를 재귀적으로 반복하여(divide and conquer) 정렬하는 방식

시간 복잡도는 O(nlogn) 최악일땐 O(n^2)

python으로 구현하면 다음과 같다.
코드출처

def quick_sort(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 quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

• 피봇을 정하고
• 피봇보다 작은 값은 작은 리스트로, 같은 값은 같은 리스트, 큰값은 큰리스트
• 이를 작은 어레이도 재귀적으로 퀵소트, 큰리스트도 재귀적으로 퀵소트