Thuật Toán Sắp Xếp

1. Khái niệm & bản chất của sắp xếp trong tối ưu thuật toán

Sắp xếp (Sorting) là quá trình tái sắp đặt các phần tử trong một tập dữ liệu theo một trật tự xác định (thường là tăng dần hoặc giảm dần theo một hoặc nhiều tiêu chí).

Trong lập trình thi đấu và khoa học máy tính, sắp xếp không đơn thuần là định dạng lại dữ liệu hiển thị, mà là một phép biến đổi cấu trúc dữ liệu nhằm:

• Tạo tính đơn điệu (Monotonicity): Đưa dãy số về trạng thái có trật tự để áp dụng các kỹ thuật tối ưu như Hai con trỏ (Two Pointers), Tìm kiếm nhị phân (Binary Search) hoặc Tham lam (Greedy).
• Khai thác tính chất lân cận (Adjacency Property): Gom các phần tử có giá trị bằng nhau hoặc gần nhau nhất về các vị trí liền kề, giúp giảm không gian tìm kiếm từ $\mathcal{O}(N^2)$ xuống $\mathcal{O}(N)$.

2. Tính chất lân cận & chứng minh toán học

2.1. Định lý về cặp phần tử có khoảng cách nhỏ nhất

Định lý: Trong một tập hợp các số thực $A = \{A_1, A_2, \dots, A_N\}$, sau khi sắp xếp tăng dần $A_1 \le A_2 \le \dots \le A_N$, giá trị nhỏ nhất của $|A_i - A_j|$ giữa hai phần tử phân biệt ($i < j$) luôn đạt được tại ít nhất một cặp phần tử kề nhau $(A_k, A_{k+1})$.

2.2. Chứng minh toán học

Xét hai chỉ số bất kỳ $i < j$. Nếu $j > i + 1$ (hai phần tử không kề nhau), tồn tại phần tử trung gian $A_{i+1}$ thỏa mãn:

$$A_i \le A_{i+1} \le A_j$$

Hiệu khoảng cách giữa $A_i$ và $A_j$: $$A_j - A_i = (A_j - A_{i+1}) + (A_{i+1} - A_i)$$

Vì $A_j - A_{i+1} \ge 0$, ta luôn có: $$A_j - A_i \ge A_{i+1} - A_i$$

Hệ quả: Mọi cặp phần tử không kề nhau đều có khoảng cách lớn hơn hoặc bằng khoảng cách của cặp kề nhau $(A_i, A_{i+1})$. Do đó, để tìm khoảng cách nhỏ nhất, ta chỉ cần duyệt qua $N - 1$ cặp kề nhau sau khi sắp xếp.

Ví dụ minh họa 1: Tìm khoảng cách nhỏ nhất giữa hai phần tử

Cho mảng gồm 6 phần tử chưa sắp xếp: $A = [15, 3, 9, 22, 4, 11]$

1. Bước 1: Sắp xếp tăng dần $\mathcal{O}(N \log N)$: $$A = [3, 4, 9, 11, 15, 22]$$

2. Bước 2: Quét $N - 1 = 5$ cặp kề nhau $\mathcal{O}(N)$:

$$\implies \text{Kết quả: Khoảng cách nhỏ nhất là } \mathbf{1} \text{ (giữa cặp 3 và 4), tìm ra trong đúng 5 phép trừ!}$$

3. Các ứng dụng thuật toán kinh điển của sắp xếp

4. Hàm sort & nguyên lý Strict Weak Ordering

4.1. Cú pháp chuẩn trong C++

C++ cung cấp hai hàm sắp xếp có sẵn:

• sort(first, last): Sử dụng thuật toán IntroSort (kết hợp giữa QuickSort, HeapSort và InsertionSort), đạt độ phức tạp thời gian $\mathcal{O}(N \log N)$ trong mọi trường hợp (trung bình và xấu nhất). Không bảo toàn thứ tự ban đầu của các phần tử bằng nhau.
• stable_sort(first, last): Sử dụng thuật toán MergeSort, độ phức tạp $\mathcal{O}(N \log N)$, đảm bảo bảo toàn nguyên vẹn thứ tự xuất hiện ban đầu của các phần tử có giá trị bằng nhau.

4.2. Nguyên lý Strict Weak Ordering (toán tử so sánh nghiêm ngặt)

Một hàm so sánh cmp(a, b) truyền vào sort bắt buộc phải thỏa mãn 3 tiên đề toán học:

1. Tính bất phản xạ (Irreflexivity): cmp(a, a) luôn trả về false.
2. Tính bất đối xứng (Asymmetry): Nếu cmp(a, b) là true thì cmp(b, a) bắt buộc phải là false.
3. Tính bắc cầu (Transitivity): Nếu cmp(a, b) là true và cmp(b, c) là true thì cmp(a, c) phải là true.

Cảnh báo quan trọng:

Cảnh báo bẫy lỗi: BẪY DẤU <= TRONG COMPARATOR

Nếu viết return a <= b;, khi a == b thì cả cmp(a, b) và cmp(b, a) đều trả về true $\implies$ Vi phạm tiên đề Bất phản xạ và Bất đối xứng $\implies$ sort sẽ tiếp tục truy cập vùng nhớ ngoài biên của mảng $\implies$ RUNTIME ERROR / CRASH CHƯƠNG TRÌNH. Lưu ý quan trọng: Luôn dùng toán tử so sánh nghiêm ngặt (< hoặc >). Khi hai phần tử bằng nhau (a == b), hàm so sánh bắt buộc phải trả về false!

5. Các kỹ thuật Custom Comparator nâng cao

5.1. Sắp xếp đa tiêu chí với vector lồng nhau (multi-criteria sorting)

Khi mỗi phần tử gồm nhiều thuộc tính số (ví dụ: điểm bắt đầu $L = a[0]$ và điểm kết thúc $R = a[1]$ của một đoạn thẳng), ta sử dụng vector lồng nhau vector<vector<int>> để tận dụng mảng sẵn có:

// Ví dụ: Sắp xếp các đoạn thẳng theo điểm kết thúc a[1] tăng dần,
// nếu trùng điểm kết thúc thì theo điểm bắt đầu a[0] giảm dần
bool cmpInterval(const vector<int> &a, const vector<int> &b) {

    if (a[1] != b[1]) {
        return a[1] < b[1]; // Ưu tiên kết thúc sớm hơn đứng trước
    }
    return a[0] > b[0]; // Cùng điểm kết thúc: Bắt đầu muộn hơn đứng trước

}

Ví dụ minh họa 2: Sắp xếp danh sách 4 đoạn thẳng

Cho 4 đoạn thẳng: $\{ [1, 5], [2, 3], [3, 6], [1, 3] \}$

• Trước khi sắp xếp: $[1, 5], [2, 3], [3, 6], [1, 3]$
• Tiêu chí 1 (Điểm kết thúc tăng dần): Các đoạn kết thúc tại $3$ đứng trước, sau đó đến $5$, rồi đến $6$.
• Tiêu chí 2 (Cùng điểm kết thúc $\implies$ bắt đầu giảm dần): Giữa $[2, 3]$ và $[1, 3]$, đoạn $[2, 3]$ có điểm bắt đầu $2 > 1$ nên được xếp trước.

Kết quả sau sắp xếp: $[[2, 3], [1, 3], [1, 5], [3, 6]]$

5.2. Sắp xếp lưu chỉ số ban đầu (index tracking)

Khi bài toán yêu cầu in ra vị trí gốc của các phần tử sau khi sắp xếp, sử dụng vector 2 chiều vector<vector<long long>> lưu cặp {giá_trị, chỉ_số_gốc}:

// Khởi tạo vector 2 chiều n hàng, 2 cột: a[i][0] là giá trị, a[i][1] là chỉ số gốc
vector<vector<long long>> a(n, vector<long long>(2));

for (int i = 0; i < n; ++i) {
    cin >> a[i][0];   // Giá trị phần tử

    a[i][1] = i + 1;  // Chỉ số ban đầu (1-based)
}

// sort mặc định so sánh cột 0 (giá trị), nếu bằng nhau so sánh tiếp cột 1 (chỉ số gốc)
sort(a.begin(), a.end());

5.3. Comparator hàm mục tiêu (objective comparison)

Bài toán ghép $N$ chuỗi số để tạo thành số lớn nhất:

bool cmpConcat(const string &a, const string &b) {
    // Sắp xếp sao cho chuỗi ghép a + b lớn hơn chuỗi ghép b + a
    return a + b > b + a;

}

6. Mẫu cài đặt chuẩn thi đấu (competitive template)

# include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu hóa tốc độ I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> a(n);

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

    }

    // Bước 1: Sắp xếp mảng O(N log N)
    sort(a.begin(), a.end());

    // Bước 2: Khai thác trật tự tuyến tính O(N)
    long long min_diff = a[1] - a[0];
    for (int i = 1; i < n - 1; ++i) {
        min_diff = min(min_diff, a[i + 1] - a[i]);
    }

    cout << min_diff << "\n";
    return 0;
}

7. Ranh giới áp dụng: Khi nào được & không được sắp xếp?

• ĐƯỢC PHÉP SẮP XẾP: Khi bài toán khảo sát tính chất trên toàn bộ tập hợp mà không phụ thuộc vào vị trí ban đầu của phần tử (như tìm $\min/\max$, đếm giá trị phân biệt, tìm cặp thỏa mãn điều kiện đại số).
• KHÔNG ĐƯỢC PHÉP SẮP XẾP: Khi bài toán có ràng buộc gắn liền với dòng thời gian hoặc vị trí liền kề nguyên thủy (như tìm đoạn con liên tiếp, chuỗi con tăng dài nhất bảo toàn thứ tự ban đầu).