[WEEK01] 퀵 소트

퀵 소트

퀵 소트(Quick Sort)는 분할 정복(Divide and Conquer) 알고리즘을 기반으로 하는 정렬 방법이다. 평균적으로 O(n log n)의 시간 복잡도를 가지며, 적절한 피벗 선택을 통해 빠른 정렬이 가능하다.

퀵 소트 동작 방식

1. 피벗(Pivot) 선택: 배열에서 하나의 요소를 피벗으로 선택한다.
2. 분할(Partitioning): 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한다.
3. 재귀적 호출: 분할된 왼쪽과 오른쪽 부분 배열에 대해 다시 퀵 소트를 수행한다.
4. 정렬 완료: 재귀 호출이 종료되면 정렬이 완료된다.

퀵 소트 구현

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 피벗 선택
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 사용 예시
data = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(data))

시간 복잡도 분석

• 평균 및 최선의 경우: O(n log n)
• 최악의 경우 (이미 정렬된 배열에서 한쪽으로만 분할될 때): O(n²)

퀵 소트의 장단점

✅ 장점

• 평균적으로 매우 빠른 정렬 속도를 보임
• 추가적인 메모리 공간을 적게 사용 (인플레이스 정렬 가능)

❌ 단점

• 최악의 경우 O(n²)으로 느려질 수 있음
• 재귀 호출이 많아 스택 오버플로우 발생 가능

최적화 방법

• 랜덤 피벗 선택: 매번 무작위로 피벗을 선택하여 최악의 경우를 방지
• 하이브리드 정렬: 작은 크기의 배열에서는 삽입 정렬을 사용하여 성능 개선

정리

퀵 소트는 분할 정복을 활용한 매우 효율적인 정렬 알고리즘이다. 최악의 경우를 방지하는 최적화 기법을 적용하면 안정적으로 O(n log n)의 성능을 유지할 수 있다.

---

def quick_sort(arr, left, right):
    pl = left    # 왼쪽 커서
    pr = right   # 오른쪽 커서
    x = arr[(left+right) // 2]   # 피벗

    while pl < pr:
        while arr[pl] < x:
            pl += 1
        while arr[pr] > x:
            pr -= 1
        if pl <= pr:
            arr[pl], arr[pr] = arr[pr], arr[pl]
            pl += 1
            pr -= 1

        if left < pr:
            quick_sort(arr, left, pr)
        if pl < right:
            quick_sort(arr, pl, right)

n = int(input())
arr = list()
for _ in range(n):
    arr.append(int(input()))

quick_sort(arr, 0, n-1)

for num in arr:
    print(num)

입력 예시	출력 예시
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7