힙 정렬과 병합 정렬

📌 힙 정렬 (Heap Sort)

💡 개념 요약

• 힙(Heap): 우선순위 큐(Priority Queue)를 구성할 때 자주 사용되는 자료구조.
• 힙 정렬은 힙에 데이터를 모두 넣은 후 하나씩 꺼내서 정렬하는 방식.
• 최소 힙(Min-Heap)을 사용하면 오름차순 정렬 가능.
• 시간복잡도: O(NlogN)

---

✅ 코드 분석

void HeapSort(vector<int>& v)
{
    // 최소 힙 선언 (작은 수부터 정렬)
    priority_queue<int, vector<int>, greater<int>> pq;

    // 모든 데이터를 힙에 삽입 (O(NlogN))
    for (int num : v)
        pq.push(num);

    // 기존 벡터 초기화
    v.clear();

    // 힙에서 하나씩 꺼내 정렬된 순서로 다시 삽입 (O(NlogN))
    while (!pq.empty())
    {
        v.push_back(pq.top());
        pq.pop();
    }
}

🔍 핵심 포인트

• greater<int>: 최소 힙 사용을 위해 필요.
• 삽입과 삭제 모두 log N, 총 N개의 요소 → O(NlogN) 보장.
• 내부적으로 std::priority_queue를 사용하므로 안정 정렬이 아님.

---

🧪 사용 예시

vector<int> v{1, 5, 3, 4, 2};
HeapSort(v);
// 출력: 1 2 3 4 5

---

📌 병합 정렬 (Merge Sort)

💡 개념 요약

• 분할 정복(Divide and Conquer) 전략 기반.
• 배열을 절반으로 나누고, 각각을 정렬한 뒤 합치는 방식.
• 시간복잡도: O(NlogN) / 추가 공간 필요.

---

✅ 전체 흐름 요약

1. 분할(Divide): 배열을 반으로 나눈다.
2. 정복(Conquer): 재귀적으로 정렬한다.
3. 결합(Combine): 정렬된 두 배열을 하나로 병합한다.

---

✅ 병합 정렬 코드 분석

void MergeSort(vector<int>& v, int left, int right)
{
    if (left >= right)
        return; // base case: 하나의 원소만 남은 경우

    int mid = (left + right) / 2;

    // 왼쪽 절반 정렬
    MergeSort(v, left, mid);

    // 오른쪽 절반 정렬
    MergeSort(v, mid + 1, right);

    // 정렬된 두 부분을 병합
    MergeResult(v, left, mid, right);
}

✅ 병합 함수 코드 분석

void MergeResult(vector<int>& v, int left, int mid, int right)
{
    int leftIdx = left;
    int rightIdx = mid + 1;

    vector<int> temp;

    // 두 배열을 병합 (정렬된 상태로)
    while (leftIdx <= mid && rightIdx <= right)
    {
        if (v[leftIdx] <= v[rightIdx])
            temp.push_back(v[leftIdx++]);
        else
            temp.push_back(v[rightIdx++]);
    }

    // 왼쪽이 남은 경우 복사
    while (leftIdx <= mid)
        temp.push_back(v[leftIdx++]);

    // 오른쪽이 남은 경우 복사
    while (rightIdx <= right)
        temp.push_back(v[rightIdx++]);

    // temp를 원래 배열에 복사
    for (int i = 0; i < temp.size(); i++)
        v[left + i] = temp[i];
}

---

🧪 사용 예시

vector<int> v{1, 5, 3, 4, 2};
MergeSort(v, 0, v.size() - 1);
// 출력: 1 2 3 4 5

---

🔍 핵심 포인트

• 안정 정렬(Stable)이다.
• 메모리 사용량이 크다 (추가 temp 벡터 필요).
• 실제 메모리 제약이 없고 정밀한 정렬이 필요할 때 유용.

---

📊 정렬 알고리즘 비교

정렬 알고리즘	시간 복잡도	공간 복잡도	안정성	정렬 방식
버블 정렬	O(N²)	O(1)	O	교환 기반
선택 정렬	O(N²)	O(1)	X	선택 기반
삽입 정렬	O(N²)	O(1)	O	삽입 기반
힙 정렬	O(NlogN)	O(1) (in-place)	X	힙 구조 기반
병합 정렬	O(NlogN)	O(N)	O	분할 정복 기반

---