Algorithm Guidecomplexity: O(n log n)

퀵 정렬 (Quick Sort)

피벗(Pivot)을 기준으로 배열을 분할해가며 정렬하는 빠르고 효율적인 분할 정복 알고리즘입니다. 대부분의 언어에서 내장 정렬 함수의 기반이 되는 매우 중요한 알고리즘입니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Quick Sort

퀵 정렬을 시작합니다. 피벗은 항상 마지막 요소를 선택합니다.

Logic Node1 / 26

Live Python

1def quick_sort(arr, low, high):

# low: 0, high: 5

2 if low < high:

3 pi = partition(arr, low, high)

4 quick_sort(arr, low, pi - 1)

5 quick_sort(arr, pi + 1, high)

7def partition(arr, low, high):

8 pivot = arr[high]

9 i = low - 1

10 for j in range(low, high):

11 if arr[j] <= pivot:

12 i += 1

13 arr[i], arr[j] = arr[j], arr[i]

14 arr[i+1], arr[high] = arr[high], arr[i+1]

15 return i + 1

02 쉽게 이해하기

For Everyone

🔑비유

기준(피벗)을 정해 '작은 편 / 큰 편'으로 가르고, 각 편을 또 가르는 것.

💡쉽게 말하면

피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한 뒤 재귀적으로 정렬합니다.

평균 O(n log n)으로 매우 빨라요.

📍어디에 쓰나

–범용 정렬(대부분의 표준 라이브러리)
–대용량 데이터

03 파이썬 구현 코드

퀵 정렬 (Quick Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 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