Bài 24: Chia để trị trong C++ và Python: sắp xếp trộn (merge sort), sắp xếp nhanh (quick sort), đếm cặp nghịch thế

Series: Thuật toán nâng cao Độ khó: Trung bình Bài 24 / Thuật toán nâng cao Chia để trị Sắp xếp

// Thuật toán nâng cao · Bài 24

Chia để trị: sắp xếp trộn, sắp xếp nhanh và đếm cặp nghịch thế

Chia bài toán thành hai nửa, giải từng nửa rồi ghép lại. Từ ý tưởng đơn giản ấy ta có hai thuật toán sắp xếp $O(n \log n)$ kinh điển và cách đếm hàng tỉ cặp số chỉ trong nháy mắt.

Lời mở đầu

Chào mừng em tới series thứ ba: Thuật toán nâng cao. Nếu em đã học xong series Thuật toán cơ bản (đệ quy, tìm kiếm nhị phân, tham lam, quy hoạch động, BFS/DFS…) thì đây là bước tiếp theo để chạm tới những bài khó trong đề HSG cấp tỉnh, chuyên Tin và đội tuyển. Series gồm 9 bài, mỗi bài vẫn giữ đúng cách học quen thuộc: lý thuyết có hình minh hoạ, code C++ kèm Python, khung chạy tay từng dòng và 8 bài tập có gợi ý.

Bài mở đầu series nói về chia để trị (divide and conquer). Em đã gặp nó mà có thể chưa để ý: tìm kiếm nhị phân ở bài 16 mỗi bước bỏ đi một nửa, đệ quy ở bài 15 gọi lại chính nó với bài toán nhỏ hơn. Hôm nay ta dùng chia để trị để viết hai thuật toán sắp xếp nổi tiếng nhất và giải bài đếm cặp nghịch thế, một bài cực kỳ hay gặp trong đề thi.

Bài 24Chia để trị, sắp xếp nhanh Bài 25Ngăn xếp, hàng đợi đơn điệu Bài 26Toán modulo và tổ hợp Bài 27Quy hoạch động nâng cao Bài 28Xâu: Hash và KMP Bài 29Đường đi ngắn nhất Bài 30DSU và cây khung Bài 31Fenwick, Segment Tree Bài 32Tổng ôn và đề thi thử

Trong bài này bạn sẽ học: ba bước của chia để trị: chia, trị, kết hợp; vì sao chia đôi cho độ phức tạp $O(n \log n)$; thuật toán sắp xếp trộn (merge sort) và kỹ thuật trộn hai dãy tăng; cách đếm cặp nghịch thế ngay trong lúc trộn; thuật toán sắp xếp nhanh (quick sort) với phép phân hoạch và chốt ngẫu nhiên; khi nào nên tự cài, khi nào dùng sort có sẵn. Có khung chạy tay merge sort, quick sort và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Chia để trị là gì Phần 2Sắp xếp trộn Phần 3Đếm nghịch thế Phần 4Sắp xếp nhanh Phần 5Chọn cách sắp xếp Bài tập8 bài + gợi ý

Phần 1Chia để trị là gì?

Chia để trị giải một bài toán lớn theo đúng ba bước:

Chia: tách bài toán thành các bài toán con cùng dạng nhưng nhỏ hơn (thường là chia đôi).
Trị: giải từng bài toán con bằng cách gọi đệ quy. Bài con đủ nhỏ (chẳng hạn chỉ còn 1 phần tử) thì giải trực tiếp.
Kết hợp: ghép đáp án của các bài con thành đáp án của bài lớn.

Ví dụ đơn giản nhất: tìm số lớn nhất của dãy. Chia dãy làm đôi, tìm max của mỗi nửa, rồi lấy số lớn hơn trong hai kết quả. Cách này không nhanh hơn duyệt một vòng for, nhưng nó cho em thấy rõ khung của mọi lời giải chia để trị.

Xem code C++ / Python: tìm max bằng chia để trị (bấm để mở)

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

int a[100005];

int findMax(int l, int r){
    if(l == r) return a[l];                 // bài toán nhỏ nhất: 1 phần tử
    int m = (l + r) / 2;                    // CHIA đôi đoạn
    int x = findMax(l, m);                  // TRỊ nửa trái
    int y = findMax(m + 1, r);              // TRỊ nửa phải
    return max(x, y);                       // KẾT HỢP hai đáp án
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << findMax(0, n - 1);
    return 0;
}

def find_max(a, l, r):
    if l == r:                         # bài toán nhỏ nhất: 1 phần tử
        return a[l]
    m = (l + r) // 2                   # CHIA đôi đoạn
    x = find_max(a, l, m)              # TRỊ nửa trái
    y = find_max(a, m + 1, r)          # TRỊ nửa phải
    return max(x, y)                   # KẾT HỢP hai đáp án

n = int(input())
a = list(map(int, input().split()))
print(find_max(a, 0, n - 1))

Khuôn mẫu chia để trị

Mọi hàm chia để trị trên đoạn [l, r] đều có cùng một dáng:

T solve(int l, int r){
    if(l == r) return ...;          // bài toán nhỏ nhất, giải trực tiếp
    int m = (l + r) / 2;            // CHIA
    T x = solve(l, m);              // TRỊ nửa trái
    T y = solve(m + 1, r);          // TRỊ nửa phải
    return ghep(x, y);              // KẾT HỢP
}

Phần khó nhất (và quyết định độ phức tạp) luôn là bước kết hợp.

Vì sao chia đôi lại nhanh? Mỗi lần chia, độ dài đoạn giảm một nửa, nên sau khoảng $\log_2 n$ lần chia thì mọi đoạn chỉ còn 1 phần tử. Cây đệ quy có $\log_2 n$ tầng. Nếu ở mỗi tầng, bước kết hợp của tất cả các đoạn cộng lại tốn $O(n)$ thì tổng cộng là $O(n \log n)$. Với $n = 10^5$: $n^2 = 10^{10}$ phép tính (quá chậm), còn $n \log_2 n \approx 1{,}7 \cdot 10^6$ (chạy trong chớp mắt).

Hình 1. Sắp xếp trộn dãy 8 phần tử: 3 tầng chia đôi (xanh dương) tới khi mỗi đoạn còn 1 phần tử, rồi 3 tầng trộn ngược lên (xanh lá).

Hình trên chỉ cho thấy kết quả của từng tầng. Thực tế máy tính không chia hết một tầng rồi mới sang tầng sau, mà đi theo đúng thứ tự gọi đệ quy: chia nửa trái tới tận cùng, trộn xong nửa trái rồi mới sang nửa phải. Em bấm Tiếp từng bước để thấy rõ thứ tự đó, có thể đổi dãy số tuỳ thích:

MÔ PHỎNGMerge sort chia đôi rồi trộn, từng lời gọi đệ quyNhập dãy tối đa 10 số rồi bấm Tiếp / Tự chạy. Mỗi hàng là một tầng của cây đệ quy.

Dãy số

chưa gọi tớiđang xử lýđã chia, chờ hai nửađã sắp xếp

Phần 2Sắp xếp trộn (merge sort)

Áp dụng khuôn mẫu cho bài sắp xếp tăng dần:

Chia đoạn [l, r] thành [l, m] và [m + 1, r].
Trị: sắp xếp mỗi nửa bằng đệ quy. Đoạn 1 phần tử thì đã tăng sẵn.
Kết hợp: trộn hai nửa đã tăng thành một đoạn tăng.

Bước trộn dùng đúng kỹ thuật hai con trỏ ở bài 17: con trỏ i chạy trên nửa trái, j chạy trên nửa phải. Mỗi bước so sánh a[i] với a[j], số nào nhỏ hơn thì đưa vào mảng tạm tmp rồi tiến con trỏ đó lên. Một nửa hết thì chép nốt nửa còn lại. Mỗi phần tử được chép đúng một lần nên trộn đoạn dài $k$ tốn $O(k)$.

Bước	Nửa trái (từ i)	Nửa phải (từ j)	So sánh	tmp
1	2 5 6 8	3 6 7 9	2 ≤ 3, lấy 2	2
2	5 6 8	3 6 7 9	5 > 3, lấy 3	2 3
3	5 6 8	6 7 9	5 ≤ 6, lấy 5	2 3 5
4	6 8	6 7 9	6 ≤ 6, lấy 6 bên trái	2 3 5 6
5	8	6 7 9	8 > 6, lấy 6	2 3 5 6 6
6	8	7 9	8 > 7, lấy 7	2 3 5 6 6 7
7	8	9	8 ≤ 9, lấy 8	2 3 5 6 6 7 8
8	(hết)	9	chép nốt 9	2 3 5 6 6 7 8 9

Bảng 1. Trộn hai nửa đã tăng [2, 5, 6, 8] và [3, 6, 7, 9] (tầng trộn cuối cùng của Hình 1). Số in đậm là vị trí con trỏ đang đứng.

Xem code C++ / Python: sắp xếp trộn (merge sort) (bấm để mở)

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

int a[200005], tmp[200005];

void mergeSort(int l, int r){
    if(l >= r) return;                       // đoạn 0 hoặc 1 phần tử: đã sắp xếp
    int m = (l + r) / 2;
    mergeSort(l, m);                         // trị nửa trái
    mergeSort(m + 1, r);                     // trị nửa phải
    int i = l, j = m + 1, k = l;             // kết hợp: trộn hai nửa đã tăng
    while(i <= m && j <= r){
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = tmp[t];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    mergeSort(0, n - 1);
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

import sys

def merge_sort(a):
    if len(a) <= 1:                  # 0 hoặc 1 phần tử: đã sắp xếp
        return a
    m = len(a) // 2
    left = merge_sort(a[:m])         # trị nửa trái
    right = merge_sort(a[m:])        # trị nửa phải
    res, i, j = [], 0, 0             # kết hợp: trộn hai nửa đã tăng
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
print(*merge_sort(a))

C++▶ Chạy tay từng dòng codemergeSort(l, r): chia đôi, sắp xếp từng nửa bằng đệ quy, rồi trộn hai nửa đã tăng vào tmp (ô vàng: con trỏ i, ô đỏ: con trỏ j).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int a[100005], tmp[100005];

6void mergeSort(int l, int r){

7 if(l >= r) return;

8 int m = (l + r) / 2;

9 mergeSort(l, m);

10 mergeSort(m + 1, r);

11 int i = l, j = m + 1, k = l;

12 while(i <= m && j <= r){

13 if(a[i] <= a[j]) tmp[k++] = a[i++];

14 else tmp[k++] = a[j++];

15 }

16 while(i <= m) tmp[k++] = a[i++];

17 while(j <= r) tmp[k++] = a[j++];

18 for(int t = l; t <= r; t++) a[t] = tmp[t];

19}

21int main(){

22 int n;

23 cin >> n;

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

25 mergeSort(0, n - 1);

26 for(int i = 0; i < n; i++) cout << a[i] << " ";

27 return 0;

28}

Hai điểm cần nhớ về merge sort

1. Luôn $O(n \log n)$, kể cả khi dãy đã tăng hay giảm sẵn, vì cách chia không phụ thuộc giá trị.
2. Ổn định (stable): nhờ điều kiện a[i] <= a[j] (lấy bên trái khi bằng nhau), hai phần tử bằng nhau giữ nguyên thứ tự ban đầu. Đổi thành < thì vẫn sắp xếp đúng nhưng mất tính ổn định. Đổi lại, merge sort cần thêm mảng tạm $O(n)$.

Phần 3Đếm cặp nghịch thế

Cặp chỉ số $(i, j)$ gọi là nghịch thế nếu $i < j$ mà $a_i > a_j$: số đứng trước lại lớn hơn số đứng sau. Số cặp nghịch thế đo xem dãy “lộn xộn” cỡ nào: dãy tăng có 0 cặp, dãy giảm $n$ phần tử có $\frac{n(n-1)}{2}$ cặp. Nó cũng bằng đúng số lần đổi chỗ hai số kề nhau ít nhất để sắp xếp dãy (đây là số lần đổi chỗ của thuật toán nổi bọt).

Hai vòng for đếm mọi cặp tốn $O(n^2)$, quá chậm khi $n = 10^5$. Chia để trị: mỗi cặp nghịch thế $(i, j)$ thuộc một trong ba loại:

cả hai nằm ở nửa trái: đệ quy nửa trái đếm giúp;
cả hai nằm ở nửa phải: đệ quy nửa phải đếm giúp;
$i$ ở nửa trái, $j$ ở nửa phải: đếm trong lúc trộn.

Điểm mấu chốt: khi trộn, hai nửa đã tăng. Lúc ta lấy $a_j$ bên phải vì $a_i > a_j$, thì mọi số $a_i, a_{i+1}, \ldots, a_m$ còn lại bên trái đều $\ge a_i > a_j$. Vậy $a_j$ tạo nghịch thế với đúng $m - i + 1$ số bên trái, cộng một phát là xong, không cần duyệt từng số.

Thử với Bảng 1: ở bước 2 lấy 3 bên phải khi bên trái còn 5, 6, 8 → cộng 3 cặp (5,3), (6,3), (8,3). Bước 5 lấy 6 bên phải khi bên trái còn 8 → cộng 1. Bước 6 lấy 7 → cộng 1. Bước 8 chép 9 khi bên trái đã hết → cộng 0. Tầng trộn này đếm được $3 + 1 + 1 = 5$ cặp chéo.

Em xem từng bước trong mô phỏng dưới đây (các ô đỏ là những số bên trái tạo cặp nghịch thế với số bên phải vừa được lấy), rồi thử tự nhập hai nửa khác:

MÔ PHỎNGĐếm cặp nghịch thế trong lúc trộn hai nửaNhập hai nửa (mỗi nửa tối đa 7 số). Xem vì sao mỗi lần lấy số bên phải lại cộng được nhiều cặp một lúc.

Nửa tráiNửa phải

đang so sánhsố bên phải được lấycác số tạo cặp nghịch thế với nóđã vào tmpđã lấy

Xem code C++ / Python: đếm cặp nghịch thế trong $O(n \log n)$ (bấm để mở)

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

int a[200005], tmp[200005];

long long countInv(int l, int r){
    if(l >= r) return 0;
    int m = (l + r) / 2;
    long long res = countInv(l, m) + countInv(m + 1, r);   // cặp nằm gọn một bên
    int i = l, j = m + 1, k = l;
    while(i <= m && j <= r){
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            res += m - i + 1;        // a[i..m] đều > a[j]: thêm m - i + 1 cặp
            tmp[k++] = a[j++];
        }
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = tmp[t];
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << countInv(0, n - 1);
    return 0;
}

import sys

def count_inv(a):
    """Trả về (dãy đã sắp xếp, số cặp nghịch thế)."""
    if len(a) <= 1:
        return a, 0
    m = len(a) // 2
    left, x = count_inv(a[:m])
    right, y = count_inv(a[m:])
    res, i, j, cnt = [], 0, 0, x + y          # cặp nằm gọn một bên
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            cnt += len(left) - i              # left[i:] đều > right[j]
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res, cnt

data = sys.stdin.read().split()
n = int(data[0])
print(count_inv(list(map(int, data[1:n + 1])))[1])

Chú ý kiểu dữ liệu

Với $n = 2 \cdot 10^5$, số cặp nghịch thế có thể tới $\frac{n(n-1)}{2} \approx 2 \cdot 10^{10}$, vượt quá int. Biến đếm bắt buộc là long long. Và để ý dấu <= khi so sánh: hai số bằng nhau không phải nghịch thế, nên khi bằng nhau phải lấy bên trái trước.

Phần 4Sắp xếp nhanh (quick sort)

Merge sort chia theo vị trí (cắt đôi ở giữa) và làm việc vất vả ở bước kết hợp. Quick sort làm ngược lại: dồn công sức vào bước chia, để bước kết hợp không phải làm gì cả.

Chia (phân hoạch): chọn một phần tử làm chốt (pivot). Dồn các số nhỏ hơn chốt sang trái, các số còn lại sang phải, rồi đặt chốt vào giữa. Lúc này chốt đã đứng đúng vị trí cuối cùng của nó.
Trị: sắp xếp phần bên trái và phần bên phải chốt bằng đệ quy.
Kết hợp: không cần làm gì, vì mọi số bên trái đã nhỏ hơn mọi số bên phải.

Cách phân hoạch dễ cài nhất (phân hoạch Lomuto): lấy chốt là a[r], biến i đánh dấu cuối “nhóm nhỏ hơn chốt”. Duyệt j từ l tới r - 1, gặp a[j] < pivot thì tăng i và đổi chỗ a[i], a[j]. Cuối cùng đổi chốt vào ô i + 1. Em bấm Tự chạy để xem nhóm ô vàng (nhỏ hơn chốt) lớn dần:

C++▶ Chạy tay từng dòng codePhân hoạch quanh pivot = a[r]: các số nhỏ hơn pivot dồn về đầu đoạn (ô vàng), rồi pivot vào giữa và đứng yên vĩnh viễn (ô xanh lá).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int a[100005];

6void quickSort(int l, int r){

7 if(l >= r) return;

8 int pivot = a[r];

9 int i = l - 1;

10 for(int j = l; j < r; j++){

11 if(a[j] < pivot){

12 i++;

13 swap(a[i], a[j]);

14 }

15 }

16 swap(a[i + 1], a[r]);

17 quickSort(l, i);

18 quickSort(i + 2, r);

19}

21int main(){

22 int n;

23 cin >> n;

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

25 quickSort(0, n - 1);

26 for(int i = 0; i < n; i++) cout << a[i] << " ";

27 return 0;

28}

Độ phức tạp. Nếu chốt chia đoạn thành hai phần xấp xỉ bằng nhau thì giống merge sort: $O(n \log n)$. Nhưng nếu xui, chốt luôn là số lớn nhất hoặc nhỏ nhất (em thử dữ liệu mẫu “đã tăng sẵn” ở trên), mỗi lần chỉ bớt được 1 phần tử và tổng thời gian thành $O(n^2)$. Người ra đề rất thích cho dãy đã sắp xếp để “bẫy” cách chọn chốt cố định. Cách chữa: chọn chốt ngẫu nhiên, đổi nó về cuối đoạn rồi phân hoạch như cũ. Khi đó thời gian trung bình là $O(n \log n)$ với mọi dữ liệu vào.

Xem code C++ / Python: sắp xếp nhanh (quick sort) với chốt ngẫu nhiên (bấm để mở)

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

int a[200005];
mt19937 rng(12345);

void quickSort(int l, int r){
    if(l >= r) return;
    int p = l + rng() % (r - l + 1);   // chọn chốt ngẫu nhiên
    swap(a[p], a[r]);
    int pivot = a[r], i = l - 1;
    for(int j = l; j < r; j++)
        if(a[j] < pivot) swap(a[++i], a[j]);
    swap(a[i + 1], a[r]);              // pivot về đúng vị trí i + 1
    quickSort(l, i);
    quickSort(i + 2, r);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    quickSort(0, n - 1);
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

import sys, random

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)                  # chọn chốt ngẫu nhiên
    less = [x for x in a if x < pivot]
    equal = [x for x in a if x == pivot]
    greater = [x for x in a if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

data = sys.stdin.read().split()
n = int(data[0])
print(*quick_sort(list(map(int, data[1:n + 1]))))

Dãy có rất nhiều số bằng nhau

Với phân hoạch Lomuto, nếu cả dãy toàn số bằng nhau thì chốt luôn đứng ở cuối và quick sort lại rơi về $O(n^2)$ dù đã chọn chốt ngẫu nhiên. Bản Python ở trên tránh được nhờ chia làm ba nhóm: nhỏ hơn, bằng, lớn hơn chốt (phân hoạch 3 đường). Trong C++ khi đi thi, cách an toàn nhất vẫn là dùng sort có sẵn.

Tìm số nhỏ thứ $k$ mà không cần sắp xếp hết. Sau một lần phân hoạch, chốt đứng ở vị trí $p$. Nếu $k = p$ thì chốt chính là đáp án; nếu $k < p$ chỉ cần đệ quy một phía bên trái, ngược lại thì bên phải. Vì chỉ đi một nhánh nên thời gian trung bình là $O(n)$. Thuật toán này tên là quickselect, và C++ có sẵn hàm nth_element(a, a + k, a + n) làm đúng việc đó.

MÔ PHỎNGQuickselect: tìm số nhỏ thứ k chỉ bằng cách đi một phíaNhập dãy (tối đa 12 số) và k. Mỗi lượt phân hoạch, phần chắc chắn không chứa đáp án bị làm mờ.

Dãy sốk

pivotnhỏ hơn pivotlớn hơn hoặc bằng pivotđã loạiđáp án

Phần 5Chọn thuật toán sắp xếp nào?

Thuật toán	Thời gian	Bộ nhớ thêm	Ổn định	Dùng khi
Chọn, chèn, nổi bọt (bài 6)	$O(n^2)$	$O(1)$	chèn, nổi bọt: có	$n \le 5000$
Đếm phân phối (bài 13)	$O(n + V)$	$O(V)$	có	giá trị nhỏ, $V \le 10^7$
Sắp xếp trộn	$O(n \log n)$	$O(n)$	có	đếm nghịch thế, đếm cặp giữa hai nửa
Sắp xếp nhanh	$O(n \log n)$ TB, $O(n^2)$ xấu nhất	$O(\log n)$	không	quickselect, tìm số nhỏ thứ k
`sort` (C++)	$O(n \log n)$	$O(\log n)$	không	mặc định khi đi thi
`stable_sort`, `sorted` (Python)	$O(n \log n)$	$O(n)$	có	cần giữ thứ tự các phần tử bằng nhau

Bảng 2. So sánh các cách sắp xếp. sort của C++ là introsort (quick sort, khi đệ quy quá sâu thì chuyển sang heap sort), còn Python dùng Timsort, một biến thể của merge sort.

Khi đi thi: nếu chỉ cần sắp xếp thì luôn dùng sort (C++) hoặc sort/sorted (Python), vừa nhanh vừa không có lỗi. Tự cài merge sort khi em cần làm thêm việc trong lúc trộn, như đếm nghịch thế hoặc đếm cặp thoả điều kiện giữa hai nửa. Tự cài phân hoạch khi cần quickselect hoặc khi đề bắt buộc tự viết thuật toán sắp xếp.

Chia để trị không chỉ để sắp xếp

Những bài kinh điển khác cũng giải bằng chia để trị: lũy thừa nhanh $a^b = (a^{b/2})^2$ trong $O(\log b)$ (bài 26 sẽ học kỹ), tháp Hà Nội, tổng đoạn con lớn nhất (bài tập 5), cặp điểm gần nhất (bài tập 8). Dấu hiệu chung: đáp án của cả đoạn ghép được từ đáp án hai nửa cộng với phần “vắt ngang” qua điểm giữa.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

Collecting Numbers (CSES 2216) (Dễ)
Tìm Ký Tự Thứ K (Trung bình)
Dãy nghịch thế (NKINV) (Khá)
Xâu Fibonacci (FIB2) (Khá)
Trò Chơi (HSG12 Hà Nội 2025 – Bài 4) (Khó)
Kth Smallest Product of Two Sorted Arrays (LeetCode 2040) (Khó)

Xem toàn bộ bài cùng chủ đề: nhãn Chia để trị.

Bài tậpLuyện chia để trị

Bài 1Sắp xếp trộnDễ

Cho dãy $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Hãy tự cài sắp xếp trộn (không dùng hàm sort có sẵn) để in dãy theo thứ tự giảm dần.

Input

5
3 1 4 1 5

Output

5 4 3 1 1

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Giống hệt phần 2, chỉ đổi điều kiện trộn thành a[i] >= a[j] để lấy số lớn hơn trước.

Xem code tham khảo (C++ / Python)

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

int a[200005], tmp[200005];

void mergeSort(int l, int r){
    if(l >= r) return;
    int m = (l + r) / 2;
    mergeSort(l, m);
    mergeSort(m + 1, r);
    int i = l, j = m + 1, k = l;
    while(i <= m && j <= r){
        if(a[i] >= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = tmp[t];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    mergeSort(0, n - 1);
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

import sys

def merge_sort(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    left, right = merge_sort(a[:m]), merge_sort(a[m:])
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] >= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    return res + left[i:] + right[j:]

data = sys.stdin.read().split()
n = int(data[0])
print(*merge_sort(list(map(int, data[1:n + 1]))))

Bài 2Lũy thừa nhanhDễ

Cho hai số nguyên $a$ và $b$ ($1 \le a \le 10^9$, $0 \le b \le 10^{18}$). Tính $a^b \bmod (10^9 + 7)$.

Input

2 10

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Chia để trị trên số mũ: $a^b = (a^{b/2})^2$ nếu $b$ chẵn, và $a^b = (a^{b/2})^2 \cdot a$ nếu $b$ lẻ. Mỗi lần gọi đệ quy, $b$ giảm một nửa nên chỉ cần khoảng 60 lần. Nhớ đưa $a$ về $a \bmod p$ trước, và dùng long long cho tích hai số nhỏ hơn $p$.

Xem code tham khảo (C++ / Python)

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

const long long MOD = 1000000007;

long long power(long long a, long long b){
    if(b == 0) return 1;
    long long h = power(a, b / 2);       // trị nửa số mũ
    long long res = h * h % MOD;         // kết hợp
    if(b % 2 == 1) res = res * a % MOD;
    return res;
}

int main(){
    long long a, b;
    cin >> a >> b;
    cout << power(a % MOD, b);
    return 0;
}

MOD = 10**9 + 7

def power(a, b):
    if b == 0:
        return 1
    h = power(a, b // 2)          # trị nửa số mũ
    res = h * h % MOD             # kết hợp
    if b % 2 == 1:
        res = res * a % MOD
    return res

a, b = map(int, input().split())
print(power(a % MOD, b))   # Python có sẵn pow(a, b, MOD)

Bài 3Đếm nghịch thếTrung bình

Cho dãy $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Đếm số cặp $(i, j)$ với $i < j$ và $a_i > a_j$.

Input

5
2 4 1 3 5

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đúng code phần 3. Ba cặp nghịch thế là (2, 1), (4, 1), (4, 3). Đáp án có thể tới $2 \cdot 10^{10}$ nên phải dùng long long.

Xem code tham khảo (C++ / Python)

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

int a[200005], tmp[200005];

long long countInv(int l, int r){
    if(l >= r) return 0;
    int m = (l + r) / 2;
    long long res = countInv(l, m) + countInv(m + 1, r);   // cặp nằm gọn một bên
    int i = l, j = m + 1, k = l;
    while(i <= m && j <= r){
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            res += m - i + 1;        // a[i..m] đều > a[j]: thêm m - i + 1 cặp
            tmp[k++] = a[j++];
        }
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = tmp[t];
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << countInv(0, n - 1);
    return 0;
}

import sys

def count_inv(a):
    """Trả về (dãy đã sắp xếp, số cặp nghịch thế)."""
    if len(a) <= 1:
        return a, 0
    m = len(a) // 2
    left, x = count_inv(a[:m])
    right, y = count_inv(a[m:])
    res, i, j, cnt = [], 0, 0, x + y          # cặp nằm gọn một bên
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            cnt += len(left) - i              # left[i:] đều > right[j]
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res, cnt

data = sys.stdin.read().split()
n = int(data[0])
print(count_inv(list(map(int, data[1:n + 1])))[1])

Bài 4Số nhỏ thứ kTrung bình

Cho dãy $n$ số nguyên ($n \le 10^6$) và số $k$ ($1 \le k \le n$). In ra số đứng ở vị trí thứ $k$ nếu sắp xếp dãy tăng dần. Yêu cầu chạy trong $O(n)$ trung bình.

Input

6 3
7 2 9 4 1 5

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Quickselect ở cuối phần 4: phân hoạch quanh chốt ngẫu nhiên, chốt đứng ở vị trí $p$. Nếu $p = k - 1$ (đánh số từ 0) thì xong, nếu không thì chỉ đi tiếp một phía. Để dãy có nhiều số bằng nhau không làm chậm, code dưới dùng phân hoạch 3 đường (nhỏ hơn, bằng, lớn hơn chốt) như bản Python. Trong C++ có thể gọi thẳng nth_element(a, a + k - 1, a + n). Dãy tăng là 1 2 4 5 7 9.

Xem code tham khảo (C++ / Python)

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

int a[1000005];
mt19937 rng(2024);

int quickSelect(int l, int r, int k){        // phần tử sẽ đứng ở vị trí k
    while(true){
        if(l == r) return a[l];
        int pivot = a[l + rng() % (r - l + 1)];
        int lt = l, i = l, gt = r;            // phân hoạch 3 đường
        while(i <= gt){
            if(a[i] < pivot) swap(a[lt++], a[i++]);
            else if(a[i] > pivot) swap(a[i], a[gt--]);
            else i++;
        }
        // a[l..lt-1] < pivot, a[lt..gt] = pivot, a[gt+1..r] > pivot
        if(k < lt) r = lt - 1;                // chỉ đi tiếp một phía
        else if(k > gt) l = gt + 1;
        else return pivot;
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << quickSelect(0, n - 1, k - 1);
    return 0;
}

import sys, random

def quick_select(a, k):                 # số nhỏ thứ k (k đếm từ 0)
    while True:
        pivot = random.choice(a)
        less = [x for x in a if x < pivot]
        eq = a.count(pivot)
        if k < len(less):
            a = less
        elif k < len(less) + eq:
            return pivot
        else:
            k -= len(less) + eq
            a = [x for x in a if x > pivot]

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
print(quick_select(list(map(int, data[2:2 + n])), k - 1))

Bài 5Tổng đoạn con lớn nhấtTrung bình

Cho dãy $n$ số nguyên ($n \le 10^5$, $|a_i| \le 10^9$). Tìm tổng lớn nhất của một đoạn con liên tiếp khác rỗng. Hãy giải bằng chia để trị trong $O(n \log n)$.

Input

8
-2 1 -3 4 -1 2 1 -5

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đoạn tốt nhất của [l, r] hoặc nằm gọn trong nửa trái, hoặc gọn trong nửa phải, hoặc vắt qua điểm giữa. Đoạn vắt qua giữa = (tổng lớn nhất của một đoạn kết thúc tại $m$, đi ngược sang trái) + (tổng lớn nhất của một đoạn bắt đầu tại $m + 1$, đi sang phải), tính bằng hai vòng lặp $O(r - l)$. Ví dụ: đoạn 4 −1 2 1 có tổng 6. (Bài này còn có cách $O(n)$ là thuật toán Kadane, nhưng ở đây ta luyện chia để trị.)

Xem code tham khảo (C++ / Python)

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

long long a[100005];

long long best(int l, int r){
    if(l == r) return a[l];
    int m = (l + r) / 2;
    long long res = max(best(l, m), best(m + 1, r));
    long long s = 0, L = LLONG_MIN, R = LLONG_MIN;
    for(int i = m; i >= l; i--){ s += a[i]; L = max(L, s); }      // kết thúc tại m
    s = 0;
    for(int i = m + 1; i <= r; i++){ s += a[i]; R = max(R, s); }  // bắt đầu tại m + 1
    return max(res, L + R);                                       // đoạn vắt qua giữa
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << best(0, n - 1);
    return 0;
}

import sys

def best(a, l, r):
    if l == r:
        return a[l]
    m = (l + r) // 2
    res = max(best(a, l, m), best(a, m + 1, r))
    s, L = 0, float('-inf')
    for i in range(m, l - 1, -1):        # kết thúc tại m
        s += a[i]; L = max(L, s)
    s, R = 0, float('-inf')
    for i in range(m + 1, r + 1):        # bắt đầu tại m + 1
        s += a[i]; R = max(R, s)
    return max(res, L + R)               # đoạn vắt qua giữa

data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
print(best(a, 0, n - 1))

Bài 6Cặp nghịch thế gấp đôiKhá

Cho dãy $n$ số nguyên ($n \le 10^5$, $|a_i| \le 2^{31} - 1$). Đếm số cặp $(i, j)$ với $i < j$ và $a_i > 2 \cdot a_j$.

Input

5
1 3 2 3 1

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Vẫn chia đôi như đếm nghịch thế, nhưng đếm và trộn tách thành hai bước: trước khi trộn, với mỗi $j$ ở nửa phải (đã tăng), dùng con trỏ $i$ trên nửa trái tăng dần tới khi $a_i > 2a_j$; khi đó mọi số từ $i$ tới $m$ đều thoả, cộng $m - i + 1$. Vì $a_j$ tăng nên $i$ chỉ tiến lên, tổng $O(n)$ mỗi tầng. Sau đó mới trộn như bình thường. Nhớ dùng long long khi tính $2a_j$. Hai cặp: (3, 1) ở vị trí 2 và 5, (3, 1) ở vị trí 4 và 5.

Xem code tham khảo (C++ / Python)

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

long long a[100005], tmp[100005];

long long solve(int l, int r){
    if(l >= r) return 0;
    int m = (l + r) / 2;
    long long res = solve(l, m) + solve(m + 1, r);
    int i = l;
    for(int j = m + 1; j <= r; j++){             // bước 1: đếm cặp chéo
        while(i <= m && a[i] <= 2 * a[j]) i++;
        res += m - i + 1;
    }
    merge(a + l, a + m + 1, a + m + 1, a + r + 1, tmp + l);   // bước 2: trộn
    for(int t = l; t <= r; t++) a[t] = tmp[t];
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << solve(0, n - 1);
    return 0;
}

import sys
from heapq import merge

def solve(a):                      # trả về (dãy đã sắp xếp, số cặp)
    if len(a) <= 1:
        return a, 0
    m = len(a) // 2
    left, x = solve(a[:m])
    right, y = solve(a[m:])
    cnt, i = x + y, 0
    for v in right:                # bước 1: đếm cặp chéo
        while i < len(left) and left[i] <= 2 * v:
            i += 1
        cnt += len(left) - i
    return list(merge(left, right)), cnt     # bước 2: trộn

data = sys.stdin.read().split()
n = int(data[0])
print(solve(list(map(int, data[1:n + 1])))[1])

Bài 7Đoạn con có tổng nhỏ hơn tKhá

Cho dãy $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^9$, có thể âm) và số $t$ ($|t| \le 2 \cdot 10^{14}$). Đếm số đoạn con liên tiếp có tổng nhỏ hơn $t$.

Input

5 4
5 -1 3 4 -1

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Gọi $P_0 = 0, P_i = a_1 + \cdots + a_i$ (mảng cộng dồn). Đoạn $(l, r]$ có tổng $P_r - P_l$, cần đếm cặp $l < r$ với $P_r - P_l < t$, tức $P_l > P_r - t$. Vì có số âm nên không dùng được hai con trỏ trên dãy gốc, nhưng chia để trị trên mảng $P$ thì được: với mỗi $r$ ở nửa phải, đếm số $l$ ở nửa trái (đã tăng) có $P_l > P_r - t$ bằng một con trỏ, rồi trộn. Năm đoạn thoả mãn là [−1], [−1, 3], [3], [4, −1] và [−1] cuối cùng.

Xem code tham khảo (C++ / Python)

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

long long P[200005], tmp[200005], t;

long long solve(int l, int r){                 // cặp l <= x < y <= r với P[y] - P[x] < t
    if(l >= r) return 0;
    int m = (l + r) / 2;
    long long res = solve(l, m) + solve(m + 1, r);
    int i = l;
    for(int j = m + 1; j <= r; j++){           // P[j] tăng dần
        while(i <= m && P[i] <= P[j] - t) i++; // P[i] chưa đủ lớn
        res += m - i + 1;                      // P[i..m] đều > P[j] - t
    }
    merge(P + l, P + m + 1, P + m + 1, P + r + 1, tmp + l);
    for(int x = l; x <= r; x++) P[x] = tmp[x];
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n >> t;
    for(int i = 1; i <= n; i++){ long long x; cin >> x; P[i] = P[i - 1] + x; }
    cout << solve(0, n);
    return 0;
}

import sys
from heapq import merge

def solve(P, t):                    # (P đã sắp xếp, số cặp x < y có P[y] - P[x] < t)
    if len(P) <= 1:
        return P, 0
    m = len(P) // 2
    left, x = solve(P[:m], t)
    right, y = solve(P[m:], t)
    cnt, i = x + y, 0
    for v in right:
        while i < len(left) and left[i] <= v - t:
            i += 1
        cnt += len(left) - i
    return list(merge(left, right)), cnt

data = sys.stdin.read().split()
n, t = int(data[0]), int(data[1])
P = [0]
for x in data[2:2 + n]:
    P.append(P[-1] + int(x))
print(solve(P, t)[1])

Bài 8Cặp điểm gần nhấtKhá

Cho $n$ điểm trên mặt phẳng ($2 \le n \le 10^5$, toạ độ nguyên, $|x|, |y| \le 10^9$). In ra bình phương khoảng cách nhỏ nhất giữa hai điểm.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Sắp xếp theo $x$, chia đôi bằng đường thẳng đứng qua điểm giữa. Gọi $d$ là khoảng cách nhỏ nhất trong hai nửa. Cặp vắt qua đường chia chỉ có thể gần hơn nếu cả hai điểm cách đường chia dưới $d$: gom các điểm đó lại, sắp theo $y$, và với mỗi điểm chỉ cần so với các điểm phía sau có hiệu $y$ nhỏ hơn $d$ (chứng minh được là không quá vài điểm). Tính toàn bộ bằng bình phương khoảng cách để không dùng số thực. Hai điểm (0, 0) và (1, 1) cách nhau $\sqrt{2}$.

Xem code tham khảo (C++ / Python)

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

typedef long long ll;
vector<pair<ll, ll>> p;          // (x, y)

ll sq(ll v){ return v * v; }

ll solve(int l, int r){          // các điểm p[l..r) đã sắp theo x
    if(r - l <= 3){
        ll best = LLONG_MAX;
        for(int i = l; i < r; i++)
            for(int j = i + 1; j < r; j++)
                best = min(best, sq(p[i].first - p[j].first) + sq(p[i].second - p[j].second));
        return best;
    }
    int m = (l + r) / 2;
    ll midx = p[m].first;
    ll d = min(solve(l, m), solve(m, r));
    vector<pair<ll, ll>> strip;   // (y, x) các điểm gần đường chia
    for(int i = l; i < r; i++)
        if(sq(p[i].first - midx) < d) strip.push_back({p[i].second, p[i].first});
    sort(strip.begin(), strip.end());
    for(int i = 0; i < (int)strip.size(); i++)
        for(int j = i + 1; j < (int)strip.size() && sq(strip[j].first - strip[i].first) < d; j++)
            d = min(d, sq(strip[j].first - strip[i].first) + sq(strip[j].second - strip[i].second));
    return d;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    p.resize(n);
    for(auto &q : p) cin >> q.first >> q.second;
    sort(p.begin(), p.end());
    cout << solve(0, n);
    return 0;
}

import sys

def solve(p, l, r):                 # p[l:r] đã sắp theo x
    if r - l <= 3:
        best = float('inf')
        for i in range(l, r):
            for j in range(i + 1, r):
                best = min(best, (p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2)
        return best
    m = (l + r) // 2
    midx = p[m][0]
    d = min(solve(p, l, m), solve(p, m, r))
    strip = sorted((y, x) for x, y in p[l:r] if (x - midx) ** 2 < d)
    for i in range(len(strip)):
        for j in range(i + 1, len(strip)):
            dy = strip[j][0] - strip[i][0]
            if dy * dy >= d:
                break
            d = min(d, dy * dy + (strip[j][1] - strip[i][1]) ** 2)
    return d

data = sys.stdin.buffer.read().split()
n = int(data[0])
p = sorted((int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n))
print(solve(p, 0, n))

Bài tiếp theo · Bài 25

Ngăn xếp đơn điệu và hàng đợi đơn điệu

Tìm số lớn hơn gần nhất bên phải, min/max trên cửa sổ trượt: những bài tưởng $O(n^2)$ hoá ra chỉ cần $O(n)$ nhờ một ngăn xếp giữ thứ tự.

Học bài 25 →

← Bài 23: Tổng ôn Thuật toán cơ bản Xem cả series Thuật toán nâng cao

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!

Lập Trình Thuật Toán

Bài 24: Chia để trị trong C++ và Python: sắp xếp trộn (merge sort), sắp xếp nhanh (quick sort), đếm cặp nghịch thế

Lời mở đầu

Phần 1Chia để trị là gì?

Phần 2Sắp xếp trộn (merge sort)

Phần 3Đếm cặp nghịch thế

Phần 4Sắp xếp nhanh (quick sort)

Phần 5Chọn thuật toán sắp xếp nào?

Bài tậpLuyện chia để trị

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++