[정글 베이직 13] — 퀵 정렬 (Quick Sort)

 

📋 문제 소개

문제 설명

퀵 정렬(Quick Sort) 알고리즘을 구현한다. 피벗(pivot)을 기준으로 작은 값과 큰 값을 분할하여 재귀적으로 정렬한다.

INPUT

정렬되지 않은 정수 배열 arr

OUTPUT

오름차순으로 정렬된 배열

예제

입력

arr = [10, 7, 8, 9, 1, 5]

출력

[1, 5, 7, 8, 9, 10]

💡 힌트

피벗 선택(보통 마지막 원소). 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할 후 재귀.

① 문제 이해

항목	내용
문제	퀵 정렬로 배열을 오름차순 정렬한다.
피벗 선택	마지막 원소 arr[high]
예제	[10,7,8,9,1,5] → [1,5,7,8,9,10]

② 핵심 아이디어

피벗 기준으로 작은 값을 왼쪽, 큰 값을 오른쪽에 모은 뒤 피벗을 제자리에 놓는다. 그 다음 왼쪽과 오른쪽을 재귀적으로 정렬한다.

# 수도코드
partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in low..high-1:
        if arr[j] <= pivot:
            i++, swap(arr[i], arr[j])
    swap(arr[i+1], arr[high])   # 피벗 제자리
    return i+1

quick_sort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p-1)
        quick_sort(arr, p+1, high)

③ 코드 분석

def partition(arr, low, high):
    pivot = arr[high]    # ① 피벗
    i = low - 1          # ② 작은 원소 경계

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # ③ 교환

    arr[i+1], arr[high] = arr[high], arr[i+1]  # ④ 피벗 제자리
    return i + 1         # ⑤ 피벗 위치 반환

def quick_sort_helper(arr, low, high):
    if low < high:        # ⑥ 베이스 케이스
        p = partition(arr, low, high)
        quick_sort_helper(arr, low, p - 1)   # ⑦ 왼쪽
        quick_sort_helper(arr, p + 1, high)  # ⑧ 오른쪽

번호	코드	의미
①	pivot = arr[high]	마지막 원소를 피벗으로 선택
②	i = low-1	피벗보다 작은 원소들의 마지막 경계 (처음엔 비어있음)
③	arr[i],arr[j]=arr[j],arr[i]	파이썬 교환 — tmp 변수 불필요
④	arr[i+1], arr[high] = ...	피벗을 경계+1 자리에 배치 (올바른 최종 위치)
⑥	if low < high	원소가 1개 이하면 이미 정렬됨 — 재귀 종료

④ 자주 하는 실수

❌ 변수명 오타

내 코드에서 pibut = arr[high] 라고 썼다. 로직은 맞지만 pivot 이 맞는 표기다. 변수명 오타는 나중에 찾기 어려운 버그가 된다.

⚠️ 이미 정렬된 배열 주의

마지막 원소를 피벗으로 쓸 때 이미 정렬된 배열이 입력되면 매번 최솟값이 피벗이 돼 O(n²) 최악 케이스가 발생한다. 실전에서는 랜덤 피벗을 고려하자.

💡 파이썬에서 두 값 교환은 a, b = b, a 한 줄로 끝난다. C처럼 tmp 변수를 따로 쓸 필요 없다.

⑤ 시간복잡도

케이스	시간	상황
평균	O(n log n)	피벗이 중간값에 가까울 때
최악	O(n²)	이미 정렬된 배열 + 마지막 원소 피벗
공간	O(log n)	재귀 스택 깊이 (제자리 정렬)

⑥ 핵심 정리

• partition은 피벗을 올바른 자리에 배치하는 함수다. 정렬은 재귀가 한다.
• 경계 변수 i = low-1 — 처음에 비어있는 "작은 원소 영역"을 나타낸다.
• 파이썬 교환: a, b = b, a 로 tmp 불필요.
• 최악 케이스를 피하려면 랜덤 피벗 또는 median-of-three 전략을 쓴다.