Sắp xếp nhanh (Quick Sort): phân hoạch, cách chọn chốt, code C++ và Python

Tư duy chia để trị của Sắp xếp nhanh (Quick Sort)

Khác với các thuật toán O(n²) như sắp xếp chọn, sắp xếp nổi bọt hay sắp xếp chèn, Sắp xếp nhanh (Quick Sort) dùng chiến lược Chia để trị (Divide and Conquer) gồm 3 bước trên đoạn a[lo .. hi]:

1. Chọn chốt (Pivot): Chọn một phần tử trong đoạn a[lo .. hi] làm mốc so sánh, gọi là chốt (pivot).
2. Phân hoạch (Partition): Hoán đổi các phần tử trong đoạn sao cho mọi phần tử ở nửa bên trái đều ≤ pivot, và mọi phần tử ở nửa bên phải đều ≥ pivot.
3. Trị (Conquer): Gọi đệ quy sắp xếp độc lập nửa bên trái và nửa bên phải (dừng khi đoạn còn 0 hoặc 1 phần tử).

Điểm đắt giá nhất của Quick Sort là ngay sau khi bước phân hoạch kết thúc, không một phần tử nào ở nửa trái còn cần bước sang nửa phải nữa. Do đó khi hai nửa tự sắp xếp xong bằng đệ quy, toàn bộ mảng tự khắc tăng dần mà không cần bước trộn (merge) hay mảng phụ như sắp xếp trộn (Merge Sort).

Ví dụ chạy tay từng bước phân hoạch Hoare

Xét mảng 7 phần tử a = [8, 3, 7, 5, 9, 2, 6] (lo = 0, hi = 6). Chọn phần tử ở chính giữa làm chốt: mid = (0 + 6) / 2 = 3, suy ra pivot = a[3] = 5.

Theo lược đồ phân hoạch Hoare, ta đặt hai con trỏ i = 0 ở đầu trái và j = 6 ở đầu phải, cho tiến ngược chiều vào tâm:

• Tăng i sang phải chừng nào a[i] < 5 (dừng lại khi gặp a[i] ≥ 5).
• Giảm j sang trái chừng nào a[j] > 5 (dừng lại khi gặp a[j] ≤ 5).
• Nếu lúc dừng mà i ≤ j, ta đổi chỗ a[i] với a[j], rồi dịch i++, j-- và lặp lại cho tới khi i > j.

Sau đúng 2 lần hoán đổi, mảng tách thành hai nửa: nửa trái a[0 .. 2] = [2, 3, 5] (đều ≤ 5) và nửa phải a[3 .. 6] = [7, 9, 8, 6] (đều ≥ 5). Thuật toán tiếp tục gọi đệ quy cho đoạn [0 .. 2] và [3 .. 6] để thu được mảng [2, 3, 5, 6, 7, 8, 9].

So sánh phân hoạch Hoare và phân hoạch Lomuto

Trong các tài liệu thuật toán, bạn sẽ gặp hai cách viết hàm partition phổ biến là Lomuto và Hoare:

Trong phân hoạch Hoare, điều kiện trượt hai vòng while là < pivot và > pivot (nghiêm ngặt, không có dấu =). Nhờ dừng lại cả ở các phần tử bằng pivot rồi đổi chỗ và tiến i++, j--, khi gặp mảng toàn số bằng nhau, hai con trỏ vẫn gặp nhau ở chính giữa đoạn và giữ vững độ phức tạp O(n log n).

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

// Sắp xếp nhanh (Quick Sort) dùng phân hoạch Hoare với chốt ở chính giữa
void quickSortHoare(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;

    int pivot = a[lo + (hi - lo) / 2];  // chọn chốt ở giữa đoạn
    int i = lo, j = hi;

    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    // Gọi đệ quy sắp xếp hai nửa [lo .. j] và [i .. hi]
    if (lo < j) quickSortHoare(a, lo, j);
    if (i < hi) quickSortHoare(a, i, hi);
}

void inMang(const vector<int>& a) {
    for (size_t i = 0; i < a.size(); i++) {
        cout << a[i] << (i + 1 == a.size() ? "\n" : " ");
    }
}

int main() {
    vector<int> a1 = {8, 3, 7, 5, 9, 2, 6};
    quickSortHoare(a1, 0, (int)a1.size() - 1);
    inMang(a1);  // 2 3 5 6 7 8 9

    vector<int> a2 = {10, -3, 0, 5, -3, 8};
    quickSortHoare(a2, 0, (int)a2.size() - 1);
    inMang(a2);  // -3 -3 0 5 8 10

    vector<int> a3 = {42};
    quickSortHoare(a3, 0, (int)a3.size() - 1);
    inMang(a3);  // 42
    return 0;
}

def quick_sort_hoare(a, lo, hi):
    """Sắp xếp nhanh (Quick Sort) tại chỗ dùng phân hoạch Hoare với chốt ở giữa."""
    if lo >= hi:
        return

    pivot = a[(lo + hi) // 2]
    i, j = lo, hi

    while i <= j:
        while a[i] < pivot:
            i += 1
        while a[j] > pivot:
            j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1

    if lo < j:
        quick_sort_hoare(a, lo, j)
    if i < hi:
        quick_sort_hoare(a, i, hi)


for arr in ([8, 3, 7, 5, 9, 2, 6], [10, -3, 0, 5, -3, 8], [42]):
    quick_sort_hoare(arr, 0, len(arr) - 1)
    print(*arr)

Khi nào Quick Sort suy biến thành O(n²) và cách khắc phục

Độ phức tạp của Quick Sort phụ thuộc vào độ cân bằng của hai nửa sau mỗi lần phân hoạch:

• Tốt nhất và trung bình — O(n log n): Mỗi bước chia mảng thành hai phần tương đối đều nhau. Cây đệ quy chỉ cao O(log n) tầng, mỗi tầng duyệt qua O(n) phần tử nên tổng thời gian là O(n log n).
• Xấu nhất — O(n²): Nếu chốt pivot luôn rơi vào phần tử nhỏ nhất hoặc lớn nhất đoạn, một nửa sẽ có 0 phần tử và nửa kia còn n - 1 phần tử. Cây đệ quy suy biến thành đường thẳng cao n tầng với tổng số phép so sánh: \[\begin{aligned} & (n - 1) + (n - 2) + \dots + 1 \\ &= \frac{n(n - 1)}{2} = O(n^2) \end{aligned}\]

Hiện tượng suy biến này xảy ra ngay khi bạn chọn chốt cố định ở đầu a[lo] hoặc cuối a[hi] mà mảng đầu vào lại đã sắp xếp sẵn hoặc toàn phần tử trùng nhau (với Lomuto). Ba cách khắc phục triệt để trong thực tế gồm:

1. Chọn chốt ở giữa, ngẫu nhiên hoặc trung vị 3 phần tử (Median-of-Three): Lấy a[(lo + hi) / 2], chọn chỉ số ngẫu nhiên trong [lo .. hi], hoặc lấy trung vị của (a[lo], a[mid], a[hi]).
2. Phân hoạch 3 phần (Dutch National Flag): Chia đoạn thành 3 vùng: < pivot ([lo .. lt - 1]), == pivot ([lt .. gt]) và > pivot ([gt + 1 .. hi]). Vì vùng == pivot ở giữa đã nằm đúng vị trí, ta chỉ đệ quy 2 đầu và hoàn tất mảng toàn số trùng nhau chỉ trong O(n)!
3. Thuật toán lai Introsort (std::sort của C++): Chạy Quick Sort kết hợp chuyển sang Heap Sort nếu độ sâu đệ quy vượt quá 2 · log₂ n để khóa chặt cận trên O(n log n).

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

// Quick Sort phân hoạch 3 phần (Dutch National Flag): < pivot, == pivot, > pivot
void quickSort3Phan(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;

    int pivot = a[lo + (hi - lo) / 2];
    int lt = lo;      // a[lo .. lt - 1] < pivot
    int i = lo;       // a[lt .. i - 1]  == pivot
    int gt = hi;      // a[gt + 1 .. hi] > pivot

    while (i <= gt) {
        if (a[i] < pivot) {
            swap(a[lt], a[i]);
            lt++;
            i++;
        } else if (a[i] > pivot) {
            swap(a[i], a[gt]);
            gt--;
        } else {
            i++;
        }
    }

    // Đoạn [lt .. gt] đã bằng pivot và nằm đúng chỗ, chỉ đệ quy 2 đầu
    quickSort3Phan(a, lo, lt - 1);
    quickSort3Phan(a, gt + 1, hi);
}

int main() {
    vector<int> a1 = {5, 2, 5, 1, 5, 9, 2, 5, 1};
    quickSort3Phan(a1, 0, (int)a1.size() - 1);
    for (size_t i = 0; i < a1.size(); i++) {
        cout << a1[i] << (i + 1 == a1.size() ? "\n" : " ");
    }  // 1 1 2 2 5 5 5 5 9

    vector<int> a2 = {9, 7, 5, 3, 1};
    quickSort3Phan(a2, 0, (int)a2.size() - 1);
    for (size_t i = 0; i < a2.size(); i++) {
        cout << a2[i] << (i + 1 == a2.size() ? "\n" : " ");
    }  // 1 3 5 7 9
    return 0;
}

def quick_sort_3_phan(a, lo, hi):
    """Quick Sort phân hoạch 3 phần (Dutch National Flag): < pivot, == pivot, > pivot."""
    if lo >= hi:
        return

    pivot = a[(lo + hi) // 2]
    lt = lo  # a[lo .. lt - 1] < pivot
    i = lo   # a[lt .. i - 1]  == pivot
    gt = hi  # a[gt + 1 .. hi] > pivot

    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1

    quick_sort_3_phan(a, lo, lt - 1)
    quick_sort_3_phan(a, gt + 1, hi)


for arr in ([5, 2, 5, 1, 5, 9, 2, 5, 1], [9, 7, 5, 3, 1]):
    quick_sort_3_phan(arr, 0, len(arr) - 1)
    print(*arr)

Vì sao thực tế Quick Sort chạy cực nhanh?

Dù cùng có độ phức tạp O(n log n), Quick Sort thường chạy nhanh hơn Merge Sort khi sắp xếp mảng trong bộ nhớ nhờ hai lợi thế:

• Thân thiện với bộ nhớ đệm CPU (Cache Locality): Hai con trỏ i và j quét tuần tự qua các ô nhớ liền kề, tận dụng tối đa bộ nhớ đệm L1/L2 của CPU.
• Không tốn mảng tạm O(n): Quick Sort hoán đổi tại chỗ (in-place) và chỉ tốn O(log n) bộ nhớ ngăn xếp. Sau khi sắp xếp xong, bạn có thể áp dụng ngay tìm kiếm nhị phân trên mảng.

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành cài đặt Quick Sort và giải các bài toán sắp xếp trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• C. A. R. Hoare: Algorithm 64 — Quicksort (Communications of the ACM, 1961)
• cppreference: std::sort (Introsort)
• MIT 6.006 Introduction to Algorithms: Divide and Conquer Sorting
• Robert Sedgewick & Jon Bentley: Quicksort is Optimal