퀵 정렬

📌 개요

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 전략을 사용하여 정렬을 수행하는 효율적인 알고리즘입니다. 평균적으로 시간 복잡도는 O(N log N)이며, 실제로도 상당히 빠른 정렬로 평가받습니다.

🔧 핵심 개념

1. Pivot(피벗) 을 하나 선택
2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
3. 각각의 파티션에 대해 재귀적으로 정렬 수행

---

⚙️ 시간 복잡도

경우	시간 복잡도
평균/최선	O(N log N)
최악	O(N²)

❗ 최악의 경우는 정렬이 거의 되어 있거나, 잘못된 피벗 선택 시 발생합니다.

---

🔍 퀵 정렬 코드 분석

🧩 Partition 함수

int Partition(vector<int>& v, int left, int right)
{
    int pivot = v[left];        // 피벗: 배열의 첫 요소
    int low = left + 1;         // 피벗 다음 요소부터 시작
    int high = right;           // 배열 끝 인덱스

    while (low <= high)
    {
        // 피벗보다 작거나 같은 값일 동안 low 증가
        while (low <= right && v[low] <= pivot)
            low++;

        // 피벗보다 크거나 같은 값일 동안 high 감소
        while (high >= left + 1 && v[high] >= pivot)
            high--;

        if (low < high)
            swap(v[low], v[high]);  // low와 high가 가리키는 값 교환
    }

    swap(v[left], v[high]);         // 피벗과 high 위치 교환
    return high;                    // 피벗의 최종 위치 반환
}

💬 Partition 함수 핵심 포인트

• pivot 기준으로 좌우 그룹을 나누는 역할
• low, high를 조절하여 그룹을 분할
• 피벗의 정렬된 위치를 반환하며 이 위치를 기준으로 재귀 정렬

---

🧩 QuickSort 함수

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

    int pivot = Partition(v, left, right); // 피벗 위치를 기준으로 분할
    QuickSort(v, left, pivot - 1);         // 왼쪽 정렬
    QuickSort(v, pivot + 1, right);        // 오른쪽 정렬
}

💬 QuickSort 함수 핵심 포인트

• 종료 조건: left >= right이면 정렬 불필요
• 분할 → 정복의 흐름을 재귀적으로 수행
• 병합은 필요 없음 (이미 정렬이 보장됨)

---

🧪 전체 실행 예시

int main()
{
    vector<int> v;

    srand(time(0));
    for (int i = 0; i < 50; i++)
        v.push_back(rand() % 100); // 랜덤 데이터 생성

    QuickSort(v, 0, v.size() - 1); // 퀵 정렬 수행

    for (int num : v)
        cout << num << " ";
    cout << endl;

    return 0;
}

✔️ 결과: 랜덤하게 섞인 숫자 50개가 오름차순으로 정렬되어 출력됩니다.

---

🧠 퀵 정렬 작동 과정 요약

1. 피벗 선택 (보통 맨 앞 원소)
2. low, high 인덱스로 양쪽에서 접근
3. 교차되기 전까지 low < high일 때 값을 교환
4. 교차되면 pivot과 high 위치 교환
5. 반환된 피벗 위치 기준으로 좌우 정렬 재귀 호출

---

📊 퀵 정렬과 다른 정렬 비교

정렬 방식	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성
버블 정렬	O(N²)	O(N²)	O(1)	안정적
선택 정렬	O(N²)	O(N²)	O(1)	불안정
삽입 정렬	O(N²)	O(N²)	O(1)	안정적
퀵 정렬	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)	불안정

---