Bài 16.4: Thuật toán quicksort trong C++

Chào mừng quay trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng nhau "mổ xẻ" một trong những thuật toán sắp xếp kinh điển và mạnh mẽ nhất: Quicksort. Nếu bạn đã từng tìm hiểu về sắp xếp, chắc chắn bạn đã nghe qua cái tên này. Quicksort nổi tiếng vì hiệu suất thường thấy rất cao trong thực tế, mặc dù trong trường hợp xấu nhất lại có thể không "quick" như tên gọi của nó.

Vậy, Quicksort hoạt động như thế nào? Tại sao nó lại phổ biến đến vậy? Và làm thế nào để triển khai nó trong C++? Hãy cùng tìm hiểu nhé!

Quicksort là gì? Nguyên lý Hoạt động

Quicksort là một thuật toán sắp xếp dựa trên nguyên tắc "Chia để trị" (Divide and Conquer). Nguyên tắc này bao gồm ba bước chính:

Chia (Divide): Chia bài toán lớn thành các bài toán con nhỏ hơn.
Trị (Conquer): Giải quyết các bài toán con một cách đệ quy.
Kết hợp (Combine): Kết hợp kết quả của các bài toán con để có lời giải cho bài toán lớn.

Đối với Quicksort, các bước này được cụ thể hóa như sau:

Chọn Chốt (Pick a Pivot): Chọn một phần tử từ mảng cần sắp xếp. Phần tử này được gọi là chốt (pivot). Việc chọn chốt ảnh hưởng lớn đến hiệu suất của thuật toán.
Phân hoạch (Partition): Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn chốt nằm về phía bên trái của chốt, và tất cả các phần tử lớn hơn chốt nằm về phía bên phải của chốt. Các phần tử bằng chốt có thể nằm ở bất kỳ bên nào (hoặc tập trung xung quanh chốt). Sau bước này, chốt sẽ nằm ở vị trí cuối cùng của nó trong mảng đã sắp xếp. Bước này chính là trái tim của Quicksort.
Đệ quy (Recursively Sort): Áp dụng đệ quy thuật toán Quicksort cho mảng con bên trái của chốt và mảng con bên phải của chốt.

Bước kết hợp không cần thiết trong Quicksort vì sau khi các mảng con được sắp xếp đệ quy, toàn bộ mảng sẽ tự động được sắp xếp.

Đi sâu vào Phân hoạch (Partitioning)

Bước phân hoạch là phần phức tạp nhất và quan trọng nhất để hiểu Quicksort. Có nhiều cách để thực hiện phân hoạch, nhưng một trong những cách phổ biến và dễ hiểu là Partitioning theo kiểu Lomuto.

Giả sử chúng ta chọn phần tử cuối cùng của mảng (hoặc mảng con) làm chốt. Quá trình phân hoạch diễn ra như sau:

Chúng ta duy trì một chỉ số i (ban đầu là low - 1, với low là chỉ số bắt đầu của mảng con). Chỉ số i này sẽ trỏ đến vị trí cuối cùng của dãy các phần tử nhỏ hơn hoặc bằng chốt mà chúng ta đã tìm thấy cho đến hiện tại.
Chúng ta duyệt qua mảng từ chỉ số low đến high - 1 (với high là chỉ số cuối cùng của mảng con, nơi chứa chốt). Sử dụng chỉ số j cho vòng lặp này.
Với mỗi phần tử arr[j]:
- Nếu arr[j] nhỏ hơn hoặc bằng chốt, điều đó có nghĩa là nó thuộc về phần bên trái của chốt. Chúng ta tăng i lên 1 (++i) và hoán đổi (swap) arr[i] với arr[j]. Việc này đảm bảo rằng các phần tử nhỏ hơn chốt luôn được đẩy về phía đầu mảng con (sau vị trí i).
Sau khi duyệt hết mảng con (trừ chốt), tất cả các phần tử nhỏ hơn hoặc bằng chốt đã được đưa về các vị trí từ low đến i. Các phần tử lớn hơn chốt nằm ở các vị trí từ i+1 đến high-1.
Cuối cùng, chúng ta đặt chốt vào vị trí đúng của nó bằng cách hoán đổi arr[i + 1] với arr[high] (chính là chốt). Vị trí i + 1 lúc này là vị trí đầu tiên mà một phần tử lớn hơn chốt có thể nằm, hoặc nếu không có phần tử nào lớn hơn, nó là vị trí ngay sau phần tử lớn nhất nhỏ hơn chốt.
Hàm phân hoạch trả về chỉ số của chốt sau khi đã đặt đúng vị trí (i + 1).

Lựa chọn Chốt (Pivot Selection)

Việc chọn chốt ảnh hưởng lớn đến hiệu suất của Quicksort.

Chọn phần tử đầu tiên hoặc cuối cùng: Đơn giản để triển khai, nhưng nếu mảng đầu vào đã được sắp xếp hoặc gần sắp xếp, cách chọn này sẽ dẫn đến trường hợp xấu nhất (O(n^2)).
Chọn ngẫu nhiên: Chọn một phần tử ngẫu nhiên trong mảng con làm chốt. Điều này giúp giảm thiểu khả năng gặp phải trường hợp xấu nhất trên các dữ liệu đầu vào có cấu trúc cụ thể.
Chọn Median-of-Three: Chọn giá trị trung vị (median) của ba phần tử (ví dụ: phần tử đầu, giữa và cuối) làm chốt. Cách này thường cho hiệu suất tốt hơn trong thực tế.

Trong ví dụ code dưới đây, chúng ta sẽ sử dụng cách đơn giản nhất: chọn phần tử cuối cùng làm chốt để minh họa rõ ràng cơ chế phân hoạch Lomuto.

Cài đặt Quicksort trong C++

Chúng ta cần các hàm sau:

swap: Hàm tiện ích để hoán đổi hai phần tử. May mắn thay, thư viện chuẩn C++ cung cấp swap.
partition: Hàm thực hiện bước phân hoạch, nhận mảng/vector, chỉ số bắt đầu (low), chỉ số kết thúc (high) và trả về chỉ số của chốt sau khi phân hoạch.
quickSort: Hàm chính thực hiện sắp xếp đệ quy.

Đây là mã nguồn C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>

void inMang(const vector<int>& a) {
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;
}

int phanHoach(vector<int>& a, int d, int c) {
    int g = a[c];
    int i = (d - 1);

    for (int j = d; j <= c - 1; j++) {
        if (a[j] <= g) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[c]);
    return (i + 1);
}

void quickSapXep(vector<int>& a, int d, int c) {
    if (d < c) {
        int p = phanHoach(a, d, c);
        quickSapXep(a, d, p - 1);
        quickSapXep(a, p + 1, c);
    }
}

int main() {
    vector<int> a = {10, 7, 8, 9, 1, 5};
    int n = a.size();

    cout << "Mang truoc khi sap xep: ";
    inMang(a);

    quickSapXep(a, 0, n - 1);

    cout << "Mang sau khi sap xep:  ";
    inMang(a);

    vector<int> b = {4, 2, 7, 1, 3, 6, 5};
    int n2 = b.size();

    cout << "\nMang truoc khi sap xep: ";
    inMang(b);

    quickSapXep(b, 0, n2 - 1);

    cout << "Mang sau khi sap xep:  ";
    inMang(b);

    return 0;
}

Mang truoc khi sap xep: 10 7 8 9 1 5 
Mang sau khi sap xep:  1 5 7 8 9 10 

Mang truoc khi sap xep: 4 2 7 1 3 6 5 
Mang sau khi sap xep:  1 2 3 4 5 6 7

Giải thích Code

Hàm inMang: Đây là một hàm trợ giúp đơn giản để hiển thị nội dung của vector<int>. Nó duyệt qua từng phần tử và in ra, sau đó xuống dòng. Sử dụng const& để tránh sao chép vector không cần thiết.
Hàm phanHoach(vector<int>& a, int d, int c):
- Tham số a: Vector cần thao tác (truyền tham chiếu để có thể thay đổi).
- Tham số d, c: Chỉ số bắt đầu và kết thúc của đoạn mảng con hiện tại cần phân hoạch.
- int g = a[c];: Chọn phần tử cuối cùng của đoạn làm chốt.
- int i = (d - 1);: Khởi tạo chỉ số i. Vị trí i+1 sẽ là nơi chúng ta đặt chốt vào cuối hàm. Ban đầu, i nằm ngoài đoạn hợp lệ (d đến c) và nhỏ hơn d.
- for (int j = d; j <= c - 1; j++): Vòng lặp chính duyệt từ đầu đoạn (d) đến trước phần tử chốt (c-1).
- if (a[j] <= g): Nếu phần tử hiện tại a[j] nhỏ hơn hoặc bằng chốt:
  - i++;: Tăng i lên. Lúc này i trỏ đến vị trí đầu tiên trong đoạn mà chúng ta chưa chắc đó là phần tử nhỏ hơn chốt.
  - swap(a[i], a[j]);: Hoán đổi a[i] với a[j]. Điều này đưa a[j] (phần tử nhỏ hơn chốt) vào vị trí i, đảm bảo rằng tất cả các phần tử từ d đến i đều nhỏ hơn hoặc bằng chốt.
- swap(a[i + 1], a[c]);: Sau vòng lặp, tất cả các phần tử từ d đến i nhỏ hơn hoặc bằng chốt. Các phần tử từ i+1 đến c-1 lớn hơn chốt. Hoán đổi chốt (đang ở a[c]) với phần tử tại a[i+1] để đặt chốt vào vị trí phân hoạch chính xác.
- return (i + 1);: Trả về chỉ số của chốt sau khi nó đã được đặt đúng vị trí.
Hàm quickSapXep(vector<int>& a, int d, int c):
- Tham số a: Vector cần sắp xếp (truyền tham chiếu).
- Tham số d, c: Chỉ số bắt đầu và kết thúc của đoạn mảng con hiện tại cần sắp xếp.
- if (d < c): Đây là điều kiện dừng đệ quy. Nếu d >= c, đoạn mảng con chỉ có 0 hoặc 1 phần tử, đã được sắp xếp, nên dừng lại.
- int p = phanHoach(a, d, c);: Gọi hàm phân hoạch để chia đoạn mảng con hiện tại và lấy về chỉ số của chốt (p).
- quickSapXep(a, d, p - 1);: Gọi đệ quy để sắp xếp đoạn mảng con bên trái chốt (từ d đến p - 1).
- quickSapXep(a, p + 1, c);: Gọi đệ quy để sắp xếp đoạn mảng con bên phải chốt (từ p + 1 đến c).
Hàm main:
- Khởi tạo một vector<int> mẫu.
- In vector trước khi sắp xếp.
- Gọi quickSapXep trên vector, với d = 0 và c = n - 1 (toàn bộ vector).
- In vector sau khi sắp xếp để kiểm tra kết quả.
- Thêm một ví dụ khác để minh họa.

Phân tích Hiệu suất (Complexity Analysis)

Hiệu suất của Quicksort phụ thuộc nhiều vào việc lựa chọn chốt và cách phân hoạch chia mảng.

Trường hợp Tốt nhất (Best Case): O(n log n)
- Xảy ra khi mỗi lần phân hoạch, chốt luôn chia mảng/mảng con thành hai nửa có kích thước gần bằng nhau.
- Độ sâu của cây đệ quy là O(log n). Mỗi cấp của cây đệ quy thực hiện tổng cộng O(n) công việc (duyệt và hoán đổi).
- Tổng cộng: O(n log n).
Trường hợp Trung bình (Average Case): O(n log n)
- Ngay cả khi việc chia mảng không hoàn hảo, nếu chốt không liên tục là phần tử nhỏ nhất hoặc lớn nhất, Quicksort vẫn cho hiệu suất rất tốt.
- Trong thực tế, Quicksort thường là một trong những thuật toán sắp xếp dựa trên so sánh nhanh nhất do các hằng số nhỏ trong thời gian thực thi.
Trường hợp Xấu nhất (Worst Case): O(n^2)
- Xảy ra khi mỗi lần phân hoạch, chốt luôn là phần tử nhỏ nhất hoặc lớn nhất trong mảng con. Điều này dẫn đến việc một mảng con có kích thước N-1 và mảng con còn lại có kích thước 0.
- Độ sâu của cây đệ quy trở thành O(n). Mỗi cấp vẫn cần O(n) công việc.
- Tổng cộng: O(n^2).
- Tình huống này xảy ra với cách chọn chốt là phần tử đầu/cuối nếu mảng đầu vào đã được sắp xếp hoặc đảo ngược.
Độ phức tạp không gian (Space Complexity):
- Quicksort là một thuật toán sắp xếp tại chỗ (in-place), có nghĩa là nó chỉ sử dụng một lượng bộ nhớ nhỏ phụ trợ ngoài bộ nhớ lưu trữ mảng.
- Không gian cần thiết chủ yếu là cho ngăn xếp đệ quy.
- Trường hợp Tốt nhất/Trung bình: O(log n) (độ sâu cây đệ quy).
- Trường hợp Xấu nhất: O(n) (độ sâu cây đệ quy tuyến tính).

Tại sao Quicksort phổ biến?

Mặc dù có trường hợp xấu nhất là O(n^2), Quicksort vẫn rất phổ biến vì:

Hiệu suất trung bình rất tốt: Trong hầu hết các trường hợp thực tế, Quicksort nhanh hơn các thuật toán O(n log n) khác như Mergesort do constant factor nhỏ.
Tại chỗ (In-place): Nó không yêu cầu thêm bộ nhớ đáng kể ngoài bộ nhớ của mảng ban đầu (không như Mergesort cần O(n) không gian phụ).
Cache-friendly: Cách truy cập bộ nhớ tuần tự trong bước phân hoạch giúp tận dụng tốt cache của CPU.

Bài tập ví dụ: C++ Bài 9.B4: Dãy số tăng

Cho dãy số nguyên dương gồm \(n\) phần tử \(a_1, a_2,..., a_n\). Bạn có thể sử dụng bao nhiêu thao tác tùy ý (có thể không dùng) để thay đổi các phần tử của dãy.

Với một thao tác bạn được chọn hai số \([l, r]\) bất kì sao cho \(1\leq l < r\leq n\), và đảo ngược vị trí của các phần tử trong đoạn từ \(l\) đến \(r\) đó. Nói cách khác, bạn có thể biến đổi dãy con \([a_l, a_{l+1},..., a_r]\) thành \([a_r, a_{r-1},... a_l]\) trong một thao tác.

Ví dụ: Cho \(n = 5\) và dãy \([1, 4, 2, 3, 5]\), chọn \(l = 2\) và \(r = 4\), sau khi biến đổi dãy sẽ được đổi thành \([1, 3, 2, 4, 5]\).

Nhiệm vụ của bạn là kiểm tra xem dãy số đã cho có thể biến đổi thành dãy tăng sau một vài thao tác không.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên \(t\ (1\leq t\leq 10^4)\) - số lượng test.

Dòng đầu tiên của mỗi test chứa một số nguyên \(n\ (1\leq n\leq 20)\) - độ dài của dãy.

Dòng thứ hai của mỗi test chứa \(n\) số nguyên \(a_1, a_2,... a_n\ (1\leq a_i\leq 10^9)\) - các phần tử của dãy.

OUTPUT FORMAT

In ra \(t\) dòng, mỗi dòng là kết quả của mỗi testcase. Nếu dãy đã cho thỏa mãn in ra YES, ngược lại in ra NO.

Ví dụ:

Input

2
5
1 4 2 3 5
6
10 9 8 8 2 1

Output

YES
NO

Giải thích ví dụ mẫu

Ví dụ 1:
- Dữ liệu: n = 5, dãy [1, 4, 2, 3, 5]
- Giải thích: Bạn có thể chọn đoạn từ vị trí 2 đến 4 và đảo ngược nó để biến dãy thành [1, 3, 2, 4, 5], dãy này đã được sắp xếp tăng dần.
Ví dụ 2:
- Dữ liệu: n = 6, dãy [10, 9, 8, 8, 2, 1]
- Giải thích: Dù bạn có thực hiện các thao tác đảo ngược, không thể sắp xếp dãy này thành dãy tăng dần.

Bạn cần kiểm tra xem dãy có thể trở thành dãy tăng dần sau một số thao tác đảo ngược không.

1. Phân tích bài toán và ràng buộc:

Mục tiêu: Biến đổi dãy ban đầu thành dãy tăng dần nghiêm ngặt (ví dụ: 1 2 3 4 5, không có phần tử trùng lặp liền kề).
Thao tác: Đảo ngược một đoạn con [l, r] bất kỳ. Có thể sử dụng bao nhiêu thao tác tùy ý (kể cả 0).
Ràng buộc: n rất nhỏ (1 <= n <= 20), t rất lớn (1 <= t <= 10^4). Giá trị phần tử lên đến 10^9.

2. Suy luận hướng giải:

Đích đến duy nhất: Nếu một dãy có thể biến đổi thành dãy tăng dần nghiêm ngặt, thì dãy tăng dần đó phải chứa chính xác các phần tử của dãy ban đầu, được sắp xếp theo thứ tự tăng dần. Thao tác đảo ngược chỉ thay đổi vị trí, không thêm, bớt hay thay đổi giá trị phần tử.
Điều kiện cần: Từ nhận xét trên, điều kiện cần đầu tiên là dãy ban đầu khi được sắp xếp phải tạo thành một dãy tăng dần nghiêm ngặt. Điều này có nghĩa là tất cả các phần tử trong dãy ban đầu phải là duy nhất (distinct). Nếu có phần tử trùng lặp, không thể tạo thành dãy tăng dần nghiêm ngặt.
Kiểm tra khả năng biến đổi: Nếu dãy ban đầu chứa các phần tử duy nhất, thì dãy đã sắp xếp tăng dần chính là đích đến. Ta cần kiểm tra xem có thể đạt được dãy này bằng các thao tác đảo ngược hay không.
Số lượng thao tác: Ràng buộc N <= 20 và T <= 10^4 gợi ý rằng giải pháp cho mỗi test case phải rất hiệu quả, khả năng cao là O(N) hoặc O(N log N), không thể là O(N^2) cho việc thử mọi đoạn đảo ngược nếu cần nhiều thao tác. Điều này dẫn đến giả thuyết rằng nếu dãy có thể sắp xếp được, thì có thể chỉ cần một thao tác đảo ngược đặc biệt để đưa nó về dạng sắp xếp.
Thao tác "đặc biệt": Thao tác đảo ngược duy nhất có khả năng sắp xếp toàn bộ dãy mà không làm hỏng các phần tử đã đúng vị trí là thao tác đảo ngược chính xác cái đoạn con mà các phần tử đang bị sai vị trí so với dãy đã sắp xếp.

3. Các bước thực hiện (Hướng giải chi tiết):

Đọc input: Đọc số lượng test t. Vòng lặp t lần.
Với mỗi test case:
- Đọc số nguyên n.
- Đọc n số nguyên vào một vector<long long> (vì giá trị phần tử có thể lớn). Gọi vector này là a.
- Tạo một bản sao của a, gọi là sx.
- Sắp xếp sx bằng sort.
- Kiểm tra điều kiện cần (phần tử duy nhất): Duyệt qua sx, kiểm tra xem có bất kỳ hai phần tử liền kề nào bằng nhau không (sx[i] == sx[i+1]). Nếu có, in ra NO và chuyển sang test case tiếp theo. (Cách khác: Dùng unique và kiểm tra kích thước, hoặc dùng is_sorted với < operator).
- Tìm đoạn con sai lệch:
  - Tìm chỉ số l (0-based index) đầu tiên mà a[l] != sx[l]. Duyệt từ đầu mảng.
  - Nếu không tìm thấy l (tức là a đã giống hệt sx), dãy ban đầu đã tăng dần, in ra YES.
  - Nếu tìm thấy l, tìm chỉ số r (0-based index) cuối cùng mà a[r] != sx[r]. Duyệt từ cuối mảng về.
- Thực hiện đảo ngược "thử":
  - Tạo một bản sao của dãy a, gọi là tmp.
  - Đảo ngược đoạn con từ chỉ số l đến r (bao gồm cả l và r) trong tmp. Sử dụng reverse(tmp.begin() + l, tmp.begin() + r + 1).
- Kiểm tra kết quả đảo ngược:
  - So sánh tmp với sx. Nếu chúng giống hệt nhau, điều đó có nghĩa là chỉ cần một thao tác đảo ngược đoạn [l, r] đã làm cho dãy trở thành tăng dần nghiêm ngặt. In ra YES.
  - Nếu tmp khác với sx, in ra NO.
- (Lưu ý về ví dụ 1: Có vẻ giải thích trong ví dụ mẫu về dãy kết quả sau đảo ngược là [1, 3, 2, 4, 5] và nói rằng nó tăng dần là một sự nhầm lẫn. Hãy bám sát định nghĩa dãy tăng dần nghiêm ngặt và kiểm tra với dãy đã sắp xếp đúng [1, 2, 3, 4, 5].)

4. Sử dụng các hàm chuẩn của C++ (std):

#include <iostream>: Để đọc/ghi input/output.
#include <vector>: Để sử dụng vector cho dãy số.
#include <algorithm>: Chứa sort, reverse, is_sorted (có thể dùng để kiểm tra nghiêm ngặt).
#include <numeric>: Có thể dùng cho các mục đích khác nhưng không bắt buộc cho hướng giải này.
Kiểm tra nghiêm ngặt có thể dùng vòng lặp hoặc is_sorted kết hợp với lambda function hoặc custom comparator nếu cần kiểm tra không chỉ tăng dần mà còn nghiêm ngặt, nhưng cách đơn giản nhất là dùng vòng lặp for kiểm tra sx[i] >= sx[i+1].
So sánh hai vector có thể dùng toán tử ==.

5. Cấu trúc code tổng quát:

#include <iostream>
#include <vector>
#include <algorithm>

void giai() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 1) {
        cout << "YES\n";
        return;
    }

    vector<long long> sx = a;
    sort(sx.begin(), sx.end());

    bool ok = true;
    for (int i = 0; i < n - 1; ++i) {
        if (sx[i] >= sx[i + 1]) {
            ok = false;
            break;
        }
    }

    if (!ok) {
        cout << "NO\n";
        return;
    }

    int l = -1, r = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] != sx[i]) {
            if (l == -1) {
                l = i;
            }
            r = i;
        }
    }

    if (l == -1) {
        cout << "YES\n";
        return;
    }

    vector<long long> tmp = a;
    reverse(tmp.begin() + l, tmp.begin() + r + 1);

    if (tmp == sx) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        giai();
    }
    return 0;
}

YES
NO

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.