📌 퀵 정렬이란?

• 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함

---

📌 퀵 정렬 구현하기

👉그림으로 과정 이해하기

---

✅ Code

def qsort(data):
    if len(data) <= 1:
        return data
    
    left, right = list(), list()
    pivot = data[0]
    
    for index in range(1, len(data)):
        if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])
    
    return qsort(left) + [pivot] + qsort(right)

• 파이썬 list comprehension을 사용하면 다음과 같이 구현할 수 있다.

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]

    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

😉 이해가 잘 안된다면 여기를 클릭

---

📌 시간 복잡도

• 퀵 정렬의 시간 복잡도는 $O(n log n)$
• 단, 최악의 경우(맨 처음 pivot이 가장 크거나, 가장 작아서 모든 데이터를 비교하는 상황)에는 $O( 𝑛^2 )$