퀵 정렬 (Quick Sort)

1. 한 줄 정의

퀵 정렬은 기준 원소(Pivot)를 기준으로 분할을 반복하는 분할 정복 정렬 알고리즘이다.

2. 핵심 아이디어

1. 기준값(Pivot)을 하나 선택
2. Pivot보다 작은 값은 왼쪽
3. Pivot보다 큰 값은 오른쪽
4. 좌·우 부분 배열에 대해 재귀 반복

3. 동작 과정 예시

예시 배열

[8, 3, 1, 7, 0, 10, 2]

Pivot = 7

[3, 1, 0, 2] 7 [8, 10]

이후 각 부분 배열에 대해 동일한 과정 반복

4. 분할(Partition) 과정이 핵심

대표적인 Partition 방식

1) Lomuto Partition (로무토 분할)

• 마지막 원소를 Pivot
• 구현 간단
• 성능은 상대적으로 떨어짐

2) Hoare Partition (호어 분할)

• 양쪽에서 포인터 이동
• 교환 횟수 적음
• 실무에서 더 자주 사용

5. 시간 복잡도

평균	O(N log N)
최선	O(N log N)
최악	O(N²)

최악의 경우

• 이미 정렬된 배열
• Pivot을 항상 끝/처음으로 선택한 경우

6. 공간 복잡도

• 평균: O(log N) (재귀 스택)
• 최악: O(N)

👉 제자리(in-place) 정렬

 

7. 퀵 정렬의 장점

• 평균적으로 매우 빠름
• 캐시 친화적
• 추가 메모리 거의 필요 없음

8. 단점 및 주의점

❌ 안정 정렬이 아님

• 동일한 값의 순서 보장 X

❌ 최악의 경우 성능 급락

• Pivot 선택이 중요

9. 최적화 기법

1️⃣ 랜덤 Pivot

pivot = random(left, right);

• 최악 케이스 확률 감소

2️⃣ Median-of-Three

• 첫, 중간, 마지막 중 중앙값 사용

3️⃣ Tail Recursion(꼬리 재귀) 제거

• 두 개의 재귀 함수 중 한쪽 재귀를 반복문으로 바꿔 재귀 깊이를 제한
• 스택 깊이 감소

4️⃣ 작은 배열은 삽입 정렬로 전환

• 실무 구현에서 흔함

10. 퀵 정렬 vs 다른 정렬

정렬	평균	최악	안정성
Quick	O(N log N)	O(N²)	❌
Merge	O(N log N)	O(N log N)	⭕
Heap	O(N log N)	O(N log N)	❌

11. 질문

Q. 왜 퀵 정렬이 빠른가요?

비교 횟수가 적고,
캐시 지역성이 좋아
실제 성능이 뛰어납니다.

Q. 최악의 경우를 어떻게 방지하나요?

랜덤 Pivot이나
IntroSort를 사용합니다.

12. 요약

퀵 정렬은 기준 원소를 중심으로 배열을 분할하며 정렬하는 분할 정복 알고리즘이다.
평균적으로 O(N log N)의 성능을 가지며 실제 실행 속도가 매우 빠르지만,
Pivot 선택에 따라 최악의 경우 O(N²)까지 성능이 저하될 수 있다.

13. 이해를 위한 코드 (Lomuto Partition 방식)

#include <vector>
#include <iostream>
using namespace std;

int Partition(vector<int>& arr, int left, int right)
{
    int pivot = arr[right];   // 마지막 원소를 Pivot으로 선택
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[right]);
    return i + 1; // Pivot의 최종 위치
}

void QuickSort(vector<int>& arr, int left, int right)
{
    if (left >= right)
        return;

    int pivotIndex = Partition(arr, left, right);

    QuickSort(arr, left, pivotIndex - 1);
    QuickSort(arr, pivotIndex + 1, right);
}

14. 이해를 위한 코드 (Hoare Partition 방식)

int HoarePartition(std::vector<int>& arr, int left, int right)
{
    int pivot = arr[left];   // Pivot을 맨 앞 값으로 선택
    int i = left - 1;
    int j = right + 1;

    while (true)
    {
        // 왼쪽에서 pivot 이상인 값 찾기
        do {
            i++;
        } while (arr[i] < pivot);

        // 오른쪽에서 pivot 이하인 값 찾기
        do {
            j--;
        } while (arr[j] > pivot);

        // 엇갈리면 종료
        if (i >= j)
            return j;

        std::swap(arr[i], arr[j]);
    }
}

void QuickSort(std::vector<int>& arr, int left, int right)
{
    if (left >= right)
        return;

    int p = HoarePartition(arr, left, right);

    QuickSort(arr, left, p);
    QuickSort(arr, p + 1, right);
}