[퀵 정렬] quick sort - python

출처:https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

Quick Sort

---

시간복잡도: 최악 - O(n²), 평균 -O(n log n)

퀵 정렬(quick sort)은 비교 정렬, 불안정 정렬에 속한다.

분할 정복 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데에서 하나의 원소를 고른다. (pivot)

2. 분할:

    pivot 앞에는 pivot보다 작은 값

    pivot 뒤에는 큰 값의 원소들이 오도록 pivot을 기준으로 리스트를 둘로 나눈다.

3. 분할된 리스트는 재귀적으로 반복하여 리스트의 크기가 0이나 1이 될 때까지 반복한다.

def quick_sort(x):
    if len(x) < 2:
        return x
    else:
        pivot = x[0]
        less = [i for i in x[1:] if i <= pivot]
        more = [i for i in x[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(more)
 
a = [100, 20, 30, 1, 6, 2, 7]
 
print(quick_sort(a))