기쁘달

퀵 정렬 (Quick Sort)

13 min read

개념

피벗(Pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하는 정렬

분할 정복 방식이지만, 병합 과정 없이 제자리에서 정렬

시간복잡도

케이스시간복잡도
최선O(n log n)
평균O(n log n)
최악O(n²)
공간복잡도O(log n) ~ O(n)

특징

장점

  • 평균적으로 가장 빠름: 실전에서 가장 많이 사용
  • 제자리 정렬: 추가 메모리 적게 사용
  • 캐시 효율적: 메모리 접근 패턴이 좋음
  • 분할 정복: 병렬 처리 가능

단점

  • 최악 O(n²): 이미 정렬된 경우
  • 불안정 정렬: 같은 값의 순서가 바뀔 수 있음
  • 피벗 선택: 성능이 피벗에 의존적

구현 방법

기본 구현 (Lomuto Partition)

def quick_sort(arr, low, high):
    if low < high:
        # 피벗을 기준으로 분할
        pivot_index = partition(arr, low, high)
 
        # 피벗 왼쪽 정렬
        quick_sort(arr, low, pivot_index - 1)
        # 피벗 오른쪽 정렬
        quick_sort(arr, pivot_index + 1, high)
 
    return arr
 
def partition(arr, low, high):
    """Lomuto Partition: 마지막 요소를 피벗으로"""
    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
 
# 테스트
arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr, 0, len(arr) - 1))
# [1, 5, 7, 8, 9, 10]

Hoare Partition (더 효율적)

def quick_sort_hoare(arr, low, high):
    if low < high:
        pivot_index = hoare_partition(arr, low, high)
 
        quick_sort_hoare(arr, low, pivot_index)
        quick_sort_hoare(arr, pivot_index + 1, high)
 
    return arr
 
def hoare_partition(arr, low, high):
    """Hoare Partition: 첫 요소를 피벗으로"""
    pivot = arr[low]
    i = low - 1
    j = high + 1
 
    while True:
        # 피벗보다 큰 요소 찾기
        i += 1
        while arr[i] < pivot:
            i += 1
 
        # 피벗보다 작은 요소 찾기
        j -= 1
        while arr[j] > pivot:
            j -= 1
 
        if i >= j:
            return j
 
        # 교환
        arr[i], arr[j] = arr[j], arr[i]
 
# 테스트
arr = [10, 7, 8, 9, 1, 5]
print(quick_sort_hoare(arr, 0, len(arr) - 1))
# [1, 5, 7, 8, 9, 10]

Python식 간단 구현

def quick_sort_simple(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_simple(left) + middle + quick_sort_simple(right)
 
# 테스트
print(quick_sort_simple([10, 7, 8, 9, 1, 5]))
# [1, 5, 7, 8, 9, 10]
 
# 주의: 추가 메모리 O(n) 사용

동작 과정

초기: [10, 7, 8, 9, 1, 5]  (피벗: 5)

1단계: 피벗 5를 기준으로 분할
[1] [5] [10, 7, 8, 9]
 ↓   ↓       ↓
정렬됨      재귀

2단계: [10, 7, 8, 9] 정렬 (피벗: 9)
[7, 8] [9] [10]
  ↓     ↓    ↓
 재귀  정렬됨 정렬됨

3단계: [7, 8] 정렬 (피벗: 8)
[7] [8]
 ↓   ↓
정렬됨

최종: [1, 5, 7, 8, 9, 10]

템플릿

def quick_sort_template(arr, low, high):
    # 기저 조건
    if low >= high:
        return
 
    # 1. 분할 (Partition)
    pivot_index = partition_template(arr, low, high)
 
    # 2. 정복 (Conquer)
    quick_sort_template(arr, low, pivot_index - 1)  # 왼쪽
    quick_sort_template(arr, pivot_index + 1, high)  # 오른쪽
 
def partition_template(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

최적화 기법

1. 랜덤 피벗 선택

import random
 
def randomized_partition(arr, low, high):
    # 랜덤 인덱스 선택
    random_index = random.randint(low, high)
    # 마지막과 교환
    arr[random_index], arr[high] = arr[high], arr[random_index]
    # 일반 partition 수행
    return partition(arr, low, high)
 
def quick_sort_randomized(arr, low, high):
    if low < high:
        pivot_index = randomized_partition(arr, low, high)
        quick_sort_randomized(arr, low, pivot_index - 1)
        quick_sort_randomized(arr, pivot_index + 1, high)
    return arr
 
# 최악의 경우 확률 감소

2. 3-Way Partition (중복 값 최적화)

def quick_sort_3way(arr, low, high):
    """중복 값이 많을 때 효율적"""
    if low >= high:
        return
 
    lt, gt = partition_3way(arr, low, high)
 
    # 피벗과 같은 값들은 정렬 필요 없음
    quick_sort_3way(arr, low, lt - 1)
    quick_sort_3way(arr, gt + 1, high)
 
def partition_3way(arr, low, high):
    """피벗과 같은 값들을 중간에 모음"""
    pivot = arr[low]
    lt = low       # arr[low+1:lt] < pivot
    i = low + 1    # arr[lt:i] == pivot
    gt = high      # arr[gt:high+1] > pivot
 
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
 
    return lt, gt
 
# 테스트
arr = [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4]
quick_sort_3way(arr, 0, len(arr) - 1)
print(arr)  # [1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]

3. Hybrid Quick Sort (삽입 정렬 결합)

def quick_sort_hybrid(arr, low, high):
    # 작은 부분 배열은 삽입 정렬
    if high - low < 10:
        insertion_sort_range(arr, low, high)
        return
 
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_hybrid(arr, low, pivot_index - 1)
        quick_sort_hybrid(arr, pivot_index + 1, high)
 
def insertion_sort_range(arr, low, high):
    """부분 배열 삽입 정렬"""
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
 
# 작은 배열에서 오버헤드 감소

4. Median-of-Three 피벗 선택

def median_of_three(arr, low, high):
    """첫, 중간, 마지막 요소의 중앙값을 피벗으로"""
    mid = (low + high) // 2
 
    # 정렬
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
 
    # 중앙값을 마지막으로 이동
    arr[mid], arr[high] = arr[high], arr[mid]
    return arr[high]
 
def quick_sort_median(arr, low, high):
    if low < high:
        pivot = median_of_three(arr, low, high)
        pivot_index = partition(arr, low, high)
        quick_sort_median(arr, low, pivot_index - 1)
        quick_sort_median(arr, pivot_index + 1, high)
    return arr
 
# 최악의 경우 방지

핵심 요약

개념설명
원리피벗 기준 분할 정복
시간복잡도평균 O(n log n), 최악 O(n²)
공간복잡도O(log n) ~ O(n)
안정성불안정 정렬
특징평균적으로 가장 빠른 정렬

다른 정렬과 비교

정렬시간복잡도 (평균)최악공간복잡도안정성특징
퀵 정렬O(n log n)O(n²)O(log n)불안정가장 빠름
병합 정렬O(n log n)O(n log n)O(n)안정최악 보장
힙 정렬O(n log n)O(n log n)O(1)불안정메모리 효율

주의사항

1. 최악의 경우 방지

# 이미 정렬된 경우 O(n²)
arr = [1, 2, 3, 4, 5]  # 최악!
 
# 해결책
# 1. 랜덤 피벗
# 2. Median-of-Three
# 3. 3-Way Partition

2. 스택 오버플로우

# 재귀 깊이가 깊어지면 위험
import sys
sys.setrecursionlimit(10**6)
 
# 또는 꼬리 재귀 최적화
def quick_sort_tail_recursive(arr, low, high):
    while low < high:
        pivot_index = partition(arr, low, high)
 
        # 작은 쪽을 재귀, 큰 쪽을 반복
        if pivot_index - low < high - pivot_index:
            quick_sort_tail_recursive(arr, low, pivot_index - 1)
            low = pivot_index + 1
        else:
            quick_sort_tail_recursive(arr, pivot_index + 1, high)
            high = pivot_index - 1

3. 불안정 정렬

# 같은 값의 순서가 바뀔 수 있음
arr = [(5, 'a'), (3, 'b'), (5, 'c'), (2, 'd')]
# 정렬 후: (5, 'c')가 (5, 'a')보다 앞에 올 수 있음
 
# 안정 정렬 필요시 병합 정렬 사용

자주 나오는 문제 유형

1. K번째 작은 수 찾기 (Quick Select)

문제: 정렬 없이 K번째 작은 수 찾기

def quick_select(arr, k):
    """K번째 작은 수 찾기 (0-indexed)"""
    if len(arr) == 1:
        return arr[0]
 
    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]
 
    if k < len(left):
        return quick_select(left, k)
    elif k < len(left) + len(middle):
        return middle[0]
    else:
        return quick_select(right, k - len(left) - len(middle))
 
# 테스트
print(quick_select([7, 10, 4, 3, 20, 15], 2))  # 7 (3번째 작은 수)
 
# 시간복잡도: 평균 O(n), 최악 O(n²)

핵심: 한쪽만 재귀하므로 O(n)

2. 배열을 특정 값 기준으로 분할

문제: K보다 작은 값들을 왼쪽, 큰 값들을 오른쪽으로

def partition_by_value(arr, k):
    """K를 기준으로 분할"""
    left = 0
    right = len(arr) - 1
 
    while left <= right:
        # 왼쪽에서 K 이상인 요소 찾기
        while left <= right and arr[left] < k:
            left += 1
 
        # 오른쪽에서 K 미만인 요소 찾기
        while left <= right and arr[right] >= k:
            right -= 1
 
        # 교환
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
 
    return arr
 
# 테스트
print(partition_by_value([3, 5, 8, 5, 10, 2, 1], 5))
# [3, 1, 2, 5, 10, 5, 8] (순서는 다를 수 있음)
 
# 시간복잡도: O(n)

핵심: Two Pointer로 한 번의 순회

3. 색 정렬 (Dutch National Flag)

문제: 0, 1, 2로만 이루어진 배열 정렬

def sort_colors(arr):
    """3-Way Partition 응용"""
    low = 0          # 0의 끝
    mid = 0          # 현재 위치
    high = len(arr) - 1  # 2의 시작
 
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
 
    return arr
 
# 테스트
print(sort_colors([2, 0, 2, 1, 1, 0]))
# [0, 0, 1, 1, 2, 2]
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

핵심: 한 번의 순회로 정렬

4. Top K Frequent Elements

문제: 가장 빈번한 K개의 요소 찾기

from collections import Counter
import random
 
def top_k_frequent(nums, k):
    """Quick Select로 Top K 찾기"""
    count = Counter(nums)
    unique = list(count.keys())
 
    def partition(left, right, pivot_idx):
        pivot_freq = count[unique[pivot_idx]]
        # 피벗을 끝으로
        unique[pivot_idx], unique[right] = unique[right], unique[pivot_idx]
 
        store_idx = left
        for i in range(left, right):
            if count[unique[i]] < pivot_freq:
                unique[store_idx], unique[i] = unique[i], unique[store_idx]
                store_idx += 1
 
        # 피벗을 제자리에
        unique[right], unique[store_idx] = unique[store_idx], unique[right]
        return store_idx
 
    def quick_select(left, right, k_smallest):
        if left == right:
            return
 
        pivot_idx = random.randint(left, right)
        pivot_idx = partition(left, right, pivot_idx)
 
        if k_smallest == pivot_idx:
            return
        elif k_smallest < pivot_idx:
            quick_select(left, pivot_idx - 1, k_smallest)
        else:
            quick_select(pivot_idx + 1, right, k_smallest)
 
    n = len(unique)
    quick_select(0, n - 1, n - k)
    return unique[n - k:]
 
# 테스트
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))
# [1, 2]
 
# 시간복잡도: 평균 O(n)

핵심: Quick Select로 빈도수 기준 분할

추천 연습 문제

기초

중급

고급

언제 사용할까?

사용 가능

  • 일반적인 정렬: 평균적으로 가장 빠름
  • 캐시 효율 중요: 메모리 접근 패턴 좋음
  • 제자리 정렬 필요: 추가 메모리 적음
  • Quick Select: K번째 요소 찾기

사용 불가

  • 최악의 경우 보장 필요: 병합 정렬 사용
  • 안정 정렬 필요: 병합 정렬 사용
  • 이미 정렬된 데이터: 랜덤화 없으면 O(n²)

결론: 실전에서 가장 많이 사용되는 정렬, 최적화 필수!

그래프 뷰

백링크