알고리즘/자료구조 - Quick Sort(퀵 정렬)

내가 이해한 퀵 정렬 

배열을 하나의 기준점(pivot)을 두고 배열을 분할하여 분할된 배열 각각의 크기를 비교한 다음 정렬하는 것

기준점을 두고 그 기준점을 기준으로 크고 작음을 비교하는 알고리즘 아닌가 싶음

def quick_sort(arr):

    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]

    less_arr, same_arr, more_arr = [], [], []

    for num in arr:
        if num < pivot:
            less_arr.append(num)

        elif num > pivot:
            more_arr.append(num)

        else:
            same_arr.append(num)

    return quick_sort(less_arr) + same_arr + quick_sort(more_arr)

arr = [4,6,9,8,7,5,3,2,1]
print(quick_sort(arr))

#[1,2,3,4,5,6,7,8,9]

 

자세한 내용은 이 블로그 참조

[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)