Sorting Algorithms

IBa cách đơn giản: nổi bọt, chọn, chèn

Trong cả bài, dãy được đánh số từ $1$ tới $n$ và ta sắp tăng dần. Một cặp vị trí $i < j$ có $a_i > a_j$ được gọi là một nghịch thế (inversion): hai số đứng sai thứ tự so với dãy đã sắp. Dãy đã tăng dần có $0$ nghịch thế, dãy giảm dần có nhiều nhất, $\frac{n(n-1)}{2}$ nghịch thế.

Sắp xếp nổi bọt (bubble sort). Đi từ đầu tới cuối dãy, gặp hai số kề nhau mà số trước lớn hơn số sau thì đổi chỗ. Sau một lượt như vậy, số lớn nhất bị đẩy dần về cuối dãy, giống bọt khí nổi lên mặt nước. Lặp lại cho phần còn lại; khi một lượt không đổi chỗ lần nào thì dãy đã tăng dần và ta dừng.

for (ll p = 1; p < n; p++) {
    bool changed = false;
    for (ll i = 1; i <= n - p; i++)
        if (a[i] > a[i + 1]) {
            swap(a[i], a[i + 1]);
            changed = true;
        }
    if (!changed) break;
}

Độ phức tạp: $O(n^2)$, với $n = 10^4$ cần khoảng $5 \cdot 10^7$ phép so sánh.

Có một tính chất rất hay của nổi bọt: mỗi lần đổi chỗ hai số kề nhau đang sai thứ tự xóa đi đúng một nghịch thế, vì chỉ có cặp của hai số đó đổi thứ tự, mọi cặp khác vẫn như cũ. Vậy số lần đổi chỗ của nổi bọt đúng bằng số nghịch thế của dãy. Hơn nữa, mọi thuật toán chỉ đổi chỗ hai phần tử kề nhau đều phải đổi ít nhất chừng ấy lần. Ở hình trên, dãy $5, 2, 7, 1, 4, 3$ có $9$ nghịch thế và nổi bọt đổi chỗ đúng $9$ lần.

Sắp xếp chọn (selection sort). Ở bước $i$, tìm số nhỏ nhất trong đoạn $a_i, \dots, a_n$ rồi đổi nó về vị trí $i$. Sau bước $i$, đoạn $a_1, \dots, a_i$ chứa $i$ số nhỏ nhất của dãy theo đúng thứ tự.

for (ll i = 1; i < n; i++) {
    ll best = i;
    for (ll j = i + 1; j <= n; j++)
        if (a[j] < a[best]) best = j;
    swap(a[i], a[best]);
}

Độ phức tạp: $O(n^2)$ phép so sánh nhưng chỉ $n - 1$ lần đổi chỗ, với $n = 10^4$ cần khoảng $5 \cdot 10^7$ phép so sánh.

Sắp xếp chọn luôn so sánh đủ $\frac{n(n-1)}{2}$ lần, kể cả khi dãy đã tăng sẵn, nhưng nó đổi chỗ ít nhất trong ba cách. Khi đổi chỗ là việc tốn kém, hay khi đề yêu cầu in ra các lần đổi chỗ và giới hạn số lần đổi, sắp xếp chọn thường là lựa chọn đúng.

Sắp xếp chèn (insertion sort). Giữ đoạn đầu $a_1, \dots, a_{i-1}$ đã tăng dần, rồi chèn $a_i$ vào đúng chỗ của nó: lần lượt dời các số lớn hơn $a_i$ sang phải một ô, rồi đặt $a_i$ vào chỗ trống. Đây cũng là cách nhiều người xếp bài trên tay.

for (ll i = 2; i <= n; i++) {
    ll x = a[i], j = i - 1;
    while (j >= 1 && a[j] > x) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = x;
}

Độ phức tạp: $O(n + k)$ với $k$ là số nghịch thế, tức $O(n^2)$ khi dãy giảm dần nhưng chỉ $O(n)$ khi dãy gần như đã sắp xếp.

Mỗi lần dời một số sang phải cũng xóa đúng một nghịch thế, nên sắp xếp chèn chạy rất nhanh khi dãy chỉ có ít số đứng sai chỗ. Vì lý do này, các bản cài sort trong thư viện thường dùng sắp xếp chèn cho các đoạn ngắn.

Ví dụNhật Ký Sắp Xếp Nổi Bọt

Đề. Cho một hoán vị của $1, 2, 3, 4, 5$ chưa tăng dần. Chạy nổi bọt: xét lần lượt các cặp vị trí $(1, 2), (2, 3), (3, 4), (4, 5)$, cặp nào sai thứ tự thì đổi chỗ; hết bốn cặp mà dãy chưa tăng dần thì làm lại từ cặp đầu. In ra dãy ngay sau mỗi lần đổi chỗ.

Lời giải. Chỉ cần làm đúng như đề mô tả và in dãy sau mỗi lần đổi chỗ. Vòng lặp ngoài dừng khi một lượt không đổi chỗ lần nào, vì khi đó dãy đã tăng dần. Dãy có năm số nên có nhiều nhất $10$ nghịch thế, tức là in nhiều nhất $10$ dòng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[6];

signed main() {
    for (ll i = 1; i <= 5; i++) cin >> a[i];
    bool changed = true;
    while (changed) {
        changed = false;
        for (ll i = 1; i <= 4; i++)
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                changed = true;
                for (ll j = 1; j <= 5; j++) cout << a[j] << (j == 5 ? '\n' : ' ');
            }
    }
}

ChạyInput5 1 4 2 3

Output1 5 4 2 3
1 4 5 2 3
1 4 2 5 3
1 4 2 3 5
1 2 4 3 5
1 2 3 4 5

Độ phức tạp: nhiều nhất $10$ lần đổi chỗ, mỗi lần in $5$ số.

IISắp xếp trộn

Cả ba cách trên đều chỉ đổi chỗ hoặc dời các số kề nhau, nên khi dãy có cỡ $n^2$ nghịch thế thì chúng phải làm cỡ $n^2$ bước. Muốn nhanh hơn, phải cho các số “nhảy xa”.

Sắp xếp trộn (merge sort) làm điều đó bằng cách chia đôi. Để sắp đoạn $[l, r]$: nếu đoạn chỉ có một số thì không cần làm gì; ngược lại đặt $mid = \lfloor (l + r)/2 \rfloor$, sắp riêng hai nửa $[l, mid]$ và $[mid + 1, r]$ bằng chính cách này, rồi trộn hai nửa đã sắp thành một. Hàm gọi lại chính nó trên đoạn nhỏ hơn như vậy được gọi là hàm đệ quy.

Trộn hai dãy đã tăng dần dùng hai con trỏ (bài 0.7), mỗi con trỏ đứng ở số nhỏ nhất chưa lấy của một dãy. Mỗi bước, so hai số đang trỏ, lấy số nhỏ hơn đưa vào kết quả rồi tiến con trỏ đó. Ví dụ trộn $1, 4, 6, 9$ với $2, 3, 7$ cho $1, 2, 3, 4, 6, 7, 9$. Cách này đúng vì số nhỏ nhất còn lại luôn nằm ở đầu một trong hai dãy; trộn hai dãy dài $p$ và $q$ tốn $O(p + q)$.

Độ dài đoạn giảm một nửa sau mỗi tầng chia, nên có khoảng $\log_2 n$ tầng. Ở mỗi tầng, các đoạn rời nhau và phủ cả dãy, nên tổng công trộn của một tầng là $O(n)$. Cả thuật toán vì thế tốn $O(n \log n)$; với $n = 2 \cdot 10^5$ chỉ có $18$ tầng.

Trong lúc trộn, ta còn đếm được số nghịch thế. Một nghịch thế hoặc nằm trọn trong nửa trái, hoặc nằm trọn trong nửa phải, hoặc có một số ở nửa trái và một số ở nửa phải. Hai loại đầu do hai lời gọi đệ quy tự đếm. Loại thứ ba đếm ngay khi trộn: lúc lấy một số $a_j$ của nửa phải ra, mọi số của nửa trái chưa được lấy đều lớn hơn $a_j$ và đứng trước nó, nên mỗi số đó tạo với $a_j$ một nghịch thế. Gọi $i$ là con trỏ của nửa trái, các số chưa lấy là $a_i, \dots, a_{mid}$, tức là có $mid - i + 1$ nghịch thế mới.

Ví dụĐếm Cặp Ngược Thứ Tự

Đề. Cho dãy $N \le 2 \cdot 10^5$ số nguyên, $|a_i| \le 10^9$. Đếm số cặp $i < j$ có $a_i > a_j$; hai số bằng nhau không tính.

Lời giải. Sắp xếp trộn và cộng $mid - i + 1$ mỗi lần lấy một số của nửa phải ra trước. Điều kiện lấy bên trái là a[i] <= a[j]: hai số bằng nhau thì lấy bên trái trước, nên cặp đó không bị đếm, đúng với dấu so sánh chặt của đề. Mảng phụ tmp khai báo toàn cục để mọi lời gọi dùng chung. Số nghịch thế có thể tới $\frac{N(N-1)}{2} \approx 2 \cdot 10^{10}$, nên cần kiểu long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N], tmp[N];

ll solve(ll l, ll r) {
    if (l == r) return 0;
    ll mid = (l + r) >> 1;
    ll res = solve(l, mid) + solve(mid + 1, r);
    ll i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            res += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (ll x = l; x <= r; x++) a[x] = tmp[x];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n) << '\n';
}

ChạyInput4
3 1 2 1

Output4

Độ phức tạp: $O(N \log N)$, với $N = 2 \cdot 10^5$ cần khoảng $3{,}6 \cdot 10^6$ phép tính.

IIISắp xếp nhanh và phần tử thứ k

Sắp xếp nhanh (quicksort) cũng chia để trị nhưng theo chiều ngược lại: phân chia trước, không cần trộn sau. Chọn một số của đoạn làm chốt (pivot), đưa các số nhỏ hơn chốt sang bên trái và các số lớn hơn chốt sang bên phải, rồi sắp riêng hai bên. Ghép bên trái, chốt, bên phải lại là xong, vì mọi số bên trái đều nhỏ hơn mọi số bên phải.

Thời gian chạy phụ thuộc vào chốt. Nếu chốt luôn chia đoạn thành hai phần gần bằng nhau, ta có $\log_2 n$ tầng như sắp xếp trộn, tổng $O(n \log n)$. Nhưng nếu luôn lấy số đầu đoạn làm chốt mà dãy đã tăng dần sẵn, thì bên trái luôn rỗng, mỗi tầng chỉ bớt đi một số, và cả thuật toán tốn $O(n^2)$. Cách chữa quen thuộc là chọn chốt ngẫu nhiên trong đoạn: khi đó không có dữ liệu nào làm thuật toán chậm một cách cố định, và thời gian trung bình là $O(n \log n)$.

Ví dụNhật Ký Sắp Xếp Nhanh Hậu Tự

Đề. Cho $N \le 1000$ số đôi một khác nhau. Sắp xếp nhanh với chốt là số đầu đoạn: chia đoạn thành dãy các số nhỏ hơn chốt và dãy các số lớn hơn chốt (giữ nguyên thứ tự xuất hiện), sắp bên trái, rồi sắp bên phải, rồi ghép bên trái, chốt, bên phải. Mỗi đoạn có ít nhất hai số, sau khi sắp xong thì in ra trên một dòng.

Lời giải. Viết đúng hàm đệ quy như đề, nhận một dãy và trả về dãy đã sắp. Lệnh in đặt sau hai lời gọi con, nên đoạn nhỏ được in trước đoạn chứa nó. Với dãy $4, 1, 5, 2, 3$ ở hình trên, đoạn $2, 3$ xong trước, rồi tới $1, 2, 3$, cuối cùng là cả dãy; đoạn chỉ có số $5$ hay số $3$ thì không in.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;

vector<ll> qs(vector<ll> a) {
    if (a.size() <= 1) return a;
    ll p = a[0];
    vector<ll> lo, hi;
    for (ll i = 1; i < (ll)a.size(); i++) {
        if (a[i] < p) lo.push_back(a[i]);
        else hi.push_back(a[i]);
    }
    lo = qs(lo);
    hi = qs(hi);
    vector<ll> res = lo;
    res.push_back(p);
    for (ll i = 0; i < (ll)hi.size(); i++) res.push_back(hi[i]);
    for (ll i = 0; i < (ll)res.size(); i++) cout << res[i] << (i + 1 == (ll)res.size() ? '\n' : ' ');
    return res;
}

signed main() {
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    qs(a);
}

ChạyInput5
4 1 5 2 3

Output2 3
1 2 3
1 2 3 4 5

Độ phức tạp: $O(N^2)$ trong trường hợp xấu nhất vì chốt cố định là số đầu; với $N = 1000$ cần khoảng $10^6$ phép tính.

Ý tưởng phân hoạch còn cho một thuật toán rất có ích: tìm phần tử nhỏ thứ $k$ mà không cần sắp cả dãy. Sau khi phân hoạch quanh chốt, ta biết chốt đứng ở vị trí thứ mấy. Nếu vị trí đó đúng là $k$ thì xong; nếu không, phần tử cần tìm nằm hẳn ở một bên, nên chỉ cần làm tiếp ở bên đó. Mỗi tầng chỉ đi tiếp một nhánh, nên với chốt ngẫu nhiên, tổng công việc trung bình là $n + \frac{n}{2} + \frac{n}{4} + \dots < 2n$, tức $O(n)$. Thư viện C++ có sẵn hàm làm việc này:

nth_element(a + 1, a + k, a + n + 1);

Độ phức tạp: trung bình $O(n)$, với $n = 10^6$ cần khoảng vài triệu phép tính.

Sau lệnh trên, a[k] là số nhỏ thứ $k$ của dãy, các số đứng trước nó đều không lớn hơn nó và các số đứng sau đều không nhỏ hơn nó, nhưng hai phần đó chưa được sắp xếp.

IVSắp xếp đếm

Có $n = 10^7$ số nguyên trong $[1, 10^4]$. sort cần cỡ $n \log_2 n \approx 2{,}3 \cdot 10^8$ phép so sánh, trong khi chỉ có $10^4$ giá trị khác nhau. Ta chỉ cần biết mỗi giá trị xuất hiện bao nhiêu lần: đếm vào mảng cnt[v], rồi viết $v$ ra đúng cnt[v] lần theo thứ tự tăng của $v$. Cách này gọi là sắp xếp đếm (counting sort), tốn $O(n + V)$ khi các giá trị nằm trong $[0, V]$.

Sắp xếp đếm chỉ đi qua mảng hai lượt, mỗi lượt là một phép cộng vào ô nhớ, còn sort phải so sánh và đổi chỗ cỡ $2 \cdot 10^8$ lần, chậm hơn khoảng 30 lần.

Khi mỗi phần tử còn mang dữ liệu khác (tên, chỉ số) và ta sắp theo một khóa nguyên nhỏ, cần giữ thứ tự ban đầu của các phần tử cùng khóa. Một cách sắp xếp giữ được điều này gọi là ổn định (stable). Lấy tổng tiền tố (bài 0.3) của mảng đếm để biết khối của mỗi khóa bắt đầu ở đâu, rồi duyệt dãy từ trái sang phải, đặt mỗi phần tử vào ô trống đầu tiên trong khối của khóa nó. Phần tử đến trước nhận vị trí nhỏ hơn, nên thứ tự của các phần tử cùng khóa được giữ nguyên.

for (ll i = 1; i <= n; i++) st[key[i] + 1]++;
st[0] = 1;
for (ll v = 1; v <= V + 1; v++) st[v] += st[v - 1];
for (ll i = 1; i <= n; i++) ord[st[key[i]]++] = i;

Độ phức tạp: $O(n + V)$, với $n = 10^6$ và $V = 10^6$ cần khoảng $3 \cdot 10^6$ phép tính.

Sau đoạn trên, ord[1..n] là các chỉ số theo khóa tăng dần, cùng khóa thì giữ thứ tự ban đầu. Tính ổn định còn cho phép sắp theo nhiều khóa bằng nhiều lượt: sắp theo khóa phụ trước, rồi sắp ổn định theo khóa chính. Áp dụng cho các chữ số từ hàng đơn vị lên hàng cao, ta được sắp xếp theo cơ số (radix sort).

Sắp xếp đếm chỉ đáng dùng khi $V$ cỡ $n$ trở xuống. Với giá trị tới $10^9$, mảng đếm cần $10^9$ ô, và khi đó nên dùng sort.

Ví dụDãy Số Theo Thứ Tự Tăng

Đề. Có $n \le 10^7$ số nguyên dương $a_i \le 10^4$, mỗi số một dòng. In dãy sau khi sắp không giảm, mỗi số một dòng.

Lời giải. Giá trị nhỏ còn $n$ rất lớn: đếm cnt[v] rồi in $v$ đúng cnt[v] lần, $O(n + 10^4)$. Phần tính toán chỉ vài dòng; phần chậm nhất lại là đọc và ghi, vì đầu vào và đầu ra đều cỡ 60 MB. Ngay cả cin đã tắt đồng bộ cũng mất cỡ một giây cho $10^7$ số, nên ta tự đọc và ghi theo từng khối lớn. Hàm gc lấy từng ký tự từ một khối $2^{16}$ byte đọc bằng fread, hàm read ghép các chữ số thành một số, hàm put gom ký tự vào một khối rồi ghi ra bằng fwrite khi đầy. Mỗi giá trị $v$ được đổi thành xâu một lần bằng to_string rồi ghi cnt[v] lần.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, cnt[10005];
char ibuf[1 << 16], obuf[1 << 16];
ll ip, il, op;

char gc() {
    if (ip == il) {
        il = fread(ibuf, 1, sizeof ibuf, stdin);
        ip = 0;
        if (il == 0) return 0;
    }
    return ibuf[ip++];
}

ll read() {
    char c = gc();
    while (c < '0') c = gc();
    ll x = 0;
    while (c >= '0') {
        x = x * 10 + c - '0';
        c = gc();
    }
    return x;
}

void put(char c) {
    if (op == sizeof obuf) {
        fwrite(obuf, 1, op, stdout);
        op = 0;
    }
    obuf[op++] = c;
}

signed main() {
    n = read();
    for (ll i = 1; i <= n; i++) cnt[read()]++;
    for (ll v = 1; v <= 10000; v++) {
        string s = to_string(v);
        for (ll k = 1; k <= cnt[v]; k++) {
            for (char c : s) put(c);
            put('\n');
        }
    }
    fwrite(obuf, 1, op, stdout);
}

ChạyInput8
4
1
4
2
10000
2
1
7

Output1
1
2
2
4
4
7
10000

Độ phức tạp: $O(n + V)$ thời gian và $O(V)$ bộ nhớ ngoài hai khối đệm; với $n = 10^7$ cần khoảng $2 \cdot 10^7$ phép tính, cộng thời gian đọc ghi.

VVì sao không nhanh hơn n log n

Có thuật toán nào chỉ dựa vào so sánh mà nhanh hơn $O(n \log n)$ không? Câu trả lời là không. Một dãy $n$ số khác nhau có $n!$ thứ tự ban đầu, và mỗi thứ tự cần một cách sắp riêng. Mỗi phép so sánh chỉ trả lời “có” hoặc “không”, nên nhiều nhất chia đôi số khả năng còn lại; muốn phân biệt hết $n!$ khả năng thì cần ít nhất khoảng $\log_2 n!$ phép so sánh, mà con số này cỡ $n \log_2 n$. Sắp xếp đếm vượt được giới hạn này vì nó không so sánh hai phần tử nào, mà dùng thẳng giá trị làm chỉ số.

VIVài cách sắp xếp kỳ lạ

Ngoài các thuật toán nghiêm túc ở trên, giới lập trình còn có những cách “sắp xếp” để cười, nhưng mỗi cách lại nhắc một điều đáng nhớ:

• Sắp xếp Stalin: đi từ trái sang, số nào nhỏ hơn số vừa giữ lại thì bị loại khỏi dãy. Chạy $O(n)$ và luôn cho dãy tăng dần, chỉ có điều là mất dữ liệu. Thứ nó trả về là một dãy con tăng, chưa chắc dài nhất.
• Sắp xếp Bogo: xáo ngẫu nhiên cả dãy cho tới khi dãy tình cờ tăng dần. Mỗi lần xáo chỉ có xác suất $\frac{1}{n!}$ trúng, nên trung bình cần cỡ $n \cdot n!$ bước; với $n = 12$ đã là vài tỉ.
• Sắp xếp bằng ngủ (sleep sort): với mỗi số $x$, cho một luồng chờ $x$ giây rồi in $x$. Số nhỏ thức dậy trước nên được in trước, nhưng thời gian chạy là giá trị lớn nhất chứ không phải số phần tử.
• Sắp xếp mì sợi (spaghetti sort): cắt các sợi mì dài đúng bằng từng số, dựng cả bó đứng trên bàn, hạ bàn tay xuống; sợi đầu tiên chạm tay là sợi dài nhất. Trên giấy là $O(n)$, nhưng chỉ chạy được trên bàn bếp.

Muốn nghe các thuật toán sắp xếp “kêu” ra sao, bạn có thể xem video mô phỏng có âm thanh trong mục Đọc thêm.