Chương 03

Sắp Xếp Nâng Cao
Chia Để Trị & Heap

Bước nhảy vọt từ O(n²) sang O(n log n). Đây là nhóm thuật toán mạnh mẽ nhất, được sử dụng trong mọi thư viện chuẩn: QuickSort, Merge Sort và HeapSort.

🧩 Tư duy Chia để trị (Divide and Conquer)

Chiến lược Chia để trị gồm 3 bước cốt lõi:

  1. Divide (Chia): Chia bài toán lớn thành các bài toán con nhỏ hơn
  2. Conquer (Trị): Giải đệ quy các bài toán con (đến khi đủ nhỏ → base case)
  3. Combine (Kết hợp): Gộp kết quả các bài toán con thành lời giải bài toán gốc
🌳 Minh họa: Chia mảng [38, 27, 43, 3, 9, 82, 10]
38
27
43
3
9
82
10
↙ Divide ↘
38
27
43
3
9
82
10
↙ Divide ↘
38
27
43
3
9
82
10
↗ Merge (Combine) ↖
3
9
10
27
38
43
82

⚡ QuickSort — Lomuto Partition

Ý tưởng: Chọn một phần tử làm pivot, phân hoạch mảng thành 2 phần: ≤ pivot và > pivot. Sau đó đệ quy sắp xếp từng phần.

🔧 Lomuto Partition Scheme

Chọn pivot = a[hi] (phần tử cuối). Dùng biến i theo dõi ranh giới giữa phần ≤ pivot và > pivot.

  1. Đặt i = lo, duyệt j từ lo đến hi-1
  2. Nếu a[j] ≤ pivot: swap a[i] với a[j], rồi i++
  3. Sau vòng lặp: swap a[i] với a[hi] → pivot ở đúng vị trí
  4. Đệ quy: QuickSort(lo, i-1) và QuickSort(i+1, hi)
⚡ C++ — QuickSort (Lomuto) 
#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& a, int lo, int hi) {
    int pivot = a[hi];  // Chọn pivot là phần tử cuối
    int i = lo;         // Ranh giới phần <= pivot

    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }
    swap(a[i], a[hi]);  // Đặt pivot vào đúng vị trí
    return i;
}

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int pi = partition(a, lo, hi);
        quickSort(a, lo, pi - 1);   // Sắp xếp nửa trái
        quickSort(a, pi + 1, hi);   // Sắp xếp nửa phải
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    quickSort(a, 0, n - 1);

    for (int x : a) cout << x << " ";
    return 0;
}
⚠️ Worst case O(n²)

Xảy ra khi mảng đã sắp xếp + chọn pivot là phần tử cuối → luôn chia lệch. Giải pháp: dùng random pivot hoặc median-of-three.

🔀 Sắp xếp trộn (Merge Sort)

Ý tưởng: Chia mảng thành 2 nửa, đệ quy sắp xếp từng nửa, rồi trộn (merge) 2 nửa đã sắp xếp lại thành một mảng hoàn chỉnh.

⚡ C++ — Merge Sort 
#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> temp;
    int i = lo, j = mid + 1;

    // Trộn 2 nửa đã sắp xếp
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j])      // <= để đảm bảo STABLE
            temp.push_back(a[i++]);
        else
            temp.push_back(a[j++]);
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= hi) temp.push_back(a[j++]);

    // Copy lại vào mảng gốc
    for (int k = lo; k <= hi; k++)
        a[k] = temp[k - lo];
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);       // Sắp nửa trái
        mergeSort(a, mid + 1, hi);   // Sắp nửa phải
        merge(a, lo, mid, hi);       // Trộn lại
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    mergeSort(a, 0, n - 1);

    for (int x : a) cout << x << " ";
    return 0;
}
💡 Merge Sort = "Vua" của Stable Sort

Luôn O(n log n) trong mọi trường hợp. Nhược điểm duy nhất: cần O(n) bộ nhớ phụ (mảng temp). Nhưng trên Linked List → O(1) bộ nhớ phụ!

🏔️ HeapSort — Sắp xếp bằng Heap

Ý tưởng: Biến mảng thành Max-Heap (cây nhị phân đầy đủ, nút cha ≥ con). Lặp đi lặp lại: lấy phần tử lớn nhất (root) đặt vào cuối, rồi heapify lại.

🌳 Max-Heap trên mảng

Với nút tại index i: con trái = 2i+1, con phải = 2i+2, cha = (i-1)/2

82
43
38
27
9
3
10

Mảng: [82, 43, 38, 27, 9, 3, 10]

🧠 Các bước HeapSort
  1. Build Max-Heap: Duyệt từ n/2 - 1 về 0, gọi heapify tại mỗi nút
  2. Extract Max: Swap a[0] (max) với a[size-1], giảm size
  3. Heapify Root: Gọi heapify(0) để sửa heap sau khi swap
  4. Lặp bước 2-3 cho đến khi heap chỉ còn 1 phần tử
⚡ C++ — HeapSort 
#include <bits/stdc++.h>
using namespace std;

// Đảm bảo cây con gốc tại i là Max-Heap
void heapify(vector<int>& a, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && a[left] > a[largest])
        largest = left;
    if (right < n && a[right] > a[largest])
        largest = right;

    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);  // Đệ quy sửa xuống dưới
    }
}

void heapSort(vector<int>& a) {
    int n = a.size();

    // Bước 1: Xây dựng Max-Heap (bottom-up)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);

    // Bước 2: Lần lượt extract max
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);       // Đưa max về cuối
        heapify(a, i, 0);      // Heapify phần còn lại
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    heapSort(a);

    for (int x : a) cout << x << " ";
    return 0;
}
Ưu điểm
  • O(n log n) guaranteed — worst case
  • In-place — O(1) bộ nhớ phụ
  • Không bị worst case như QuickSort
Nhược điểm
  • Unstable
  • Không cache-friendly (nhảy index)
  • Thực tế chậm hơn QuickSort

📊 So sánh hiệu năng thực tế

Thuật toánBestAverageWorstSpaceStableGhi chú
QuickSort O(n log n)O(n log n)O(n²) O(log n)❌ Nhanh nhất thực tế, cache-friendly
Merge Sort O(n log n)O(n log n)O(n log n) O(n)✅ Stable, luôn đảm bảo O(n log n)
HeapSort O(n log n)O(n log n)O(n log n) O(1)❌ In-place + guaranteed O(n log n)
📝 Khi nào dùng thuật toán nào?

• QuickSort: Mặc định cho mọi bài — nhanh nhất thực tế
• Merge Sort: Cần stable, đếm inversions, sắp trên Linked List
• HeapSort: Cần O(n log n) guaranteed + O(1) space
• std::sort() trong C++ dùng Introsort = QuickSort + HeapSort + Insertion Sort

← Chương 2: Sắp Xếp Cơ Bản Chương 4: Linked List →