[알고리즘] 퀵 정렬[Quick sort]이란?

• 분할 알고리즘의 하나로 평균적으로 굉장히 빠른 시간 복잡도를 갖고 있는 정렬 방법이다.
• 기준이 되는 데이터 값을 정하고 (이를 피벗(Pivot)이라고 칭한다.) 이를 중심으로 피벗 앞에는 피벗보다 작은 값이 오고 피벗 뒤의 값에는 피벗보다 큰 값이 온다. 이렇게 두 개의 작고, 큰 부분들을 나누는 것을 분할이라고 부르며 분할되어진 두개의 리스트에 대해 재귀적으로 이 과정을 반복하여 정렬한다.
•  코드는 아래와 같다. 

def quick_sort(li):
    if len(li) <= 1:
        return li

    pivot = li[len(li)//2]
    less = []
    more = []
    equal = []
    for i in li:
        if i < pivot:
            less.append(i)
        elif i > pivot:
            more.append(i)
        else:
            equal.append(i)

    return quick_sort(less)+equal+quick_sort(more)