퀵 정렬(Quick Sort)

퀵 정렬 구현하기

---

퀵 정렬

• 복잡도 : O(nlogn)
• 순서
  1. 기준 값이 되는 피벗 값을 구한다. (리스트의 첫번째)
  2. 피벗 값보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 위치시킨다.
  3. 분류가 끝나면 왼쪽, 오른쪽 각각의 피벗을 구해 1번부터 다시 반복한다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    
    left = []
    right = []
    
    for i in array[1:]:
        if i > pivot:
            right.append(i)
        else:
            left.append(i)
    result = quick_sort(left) + [pivot] + quick_sort(right)
    
    return result