Algorithm Guidecomplexity: O(n log n)

퀵 정렬 (Quick Sort)

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

01퀵 정렬 (Quick Sort)

알고리즘 작동 원리 탐색

퀵 정렬을 시작합니다. 기준값 하나를 정해 그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 몰아냅니다.

맨 뒤의 15를 기준값으로 삼습니다. 이제 앞에서부터 훑으며 15보다 작은 것을 찾습니다.

38은 기준값 15보다 큽니다. 오른쪽에 남을 값이므로 그대로 둡니다.

27도 15보다 큽니다. 계속 지나갑니다.

43도 마찬가지입니다. 아직 왼쪽으로 보낼 값을 못 만났습니다.

10을 만났습니다. 15보다 작으니 왼쪽 구역으로 보내야 합니다.

왼쪽 구역의 첫 자리에 있던 38과 자리를 바꿉니다. 이제 10이 왼쪽에 섰습니다.

마지막 76도 15보다 큽니다. 훑기가 끝났습니다.

왼쪽 구역이 10 하나로 끝났으니, 기준값 15가 앉을 자리는 그 바로 뒤입니다.

15를 그 자리로 옮깁니다.

15는 이제 영원히 제자리입니다. 왼쪽 [10]과 오른쪽 [43, 38, 76, 27]을 각각 따로 정렬합니다.

왼쪽은 10 하나뿐이라 더 할 일이 없습니다.

오른쪽 구역으로 넘어갑니다. 맨 뒤의 27을 기준값으로 삼습니다.

43은 27보다 큽니다. 그대로 둡니다.

38도 큽니다. 지나갑니다.

76까지 전부 27보다 컸습니다 — 왼쪽으로 보낼 값이 하나도 없습니다.

왼쪽 구역이 비었으니 27은 이 구역의 맨 앞에 앉습니다.

27을 그 자리로 옮깁니다.

27도 제자리를 잡았습니다. 남은 [38, 76, 43]을 같은 방법으로 정렬합니다.

이번엔 맨 뒤의 43이 기준값입니다.

38은 43보다 작습니다. 왼쪽 구역으로 보냅니다.

이미 왼쪽 첫 자리에 있어 움직일 필요가 없습니다.

76은 43보다 큽니다. 오른쪽에 남습니다.

왼쪽에 38 하나가 들어갔으니 43은 그 뒤에 앉습니다.

43을 그 자리로 옮깁니다.

정렬 완료 · 10 15 27 38 43 76. 기준값을 하나씩 제자리에 박아 나가면 전체가 정렬됩니다.

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

1 / 26

02 쉽게 이해하기

For Everyone

🔑핵심 동작

피벗을 기준으로 작은 쪽과 큰 쪽으로 가르고 각 쪽을 또 가릅니다. 피벗이 한쪽으로 치우치면 O(n²)까지 늘어납니다.

💡쉽게 말하면

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

평균 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