8.8K 673 107

Đã đăng vào thg 8 25, 2021 7:57 SA 18 phút đọc

668

Bài toán Sắp xếp và các giải thuật Sắp xếp cơ bản

I. Bài toán sắp xếp

Sắp xếp là một khái niệm mà chúng ta dễ dàng gặp trong cuộc sống cũng như trong công việc. Cùng lấy một vài ví dụ:

Sắp xếp lại đồ đạc trong phòng, trong nhà.
Sắp xếp các tài liệu trong tủ sách theo thứ tự.
Sắp xếp công việc cho anh em trong công ty. $...$

Trong Tin học, việc sắp xếp luôn luôn diễn ra không ngừng mà đôi khi chúng ta không nhận ra. Chẳng hạn, trong mỗi folder của máy tính, các tệp đều được sắp xếp theo thứ tự bảng chữ cái, và người dùng hoàn toàn có thể điều chỉnh việc sắp xếp theo những thứ tự khác nhau như: ngày tạo tệp, kích thước tệp,...Có đến $40\%$ thời gian tính toán của máy tính là dành cho việc sắp xếp. Mục tiêu của tất cả những việc này, không gì khác ngoài giúp cho dữ liệu được tổ chức một cách khoa học, ngăn nắp, dễ dàng tìm kiếm khi cần đến. Không phải ngẫu nhiên mà giải thuật Sắp xếp nhanh (Quick Sort) được bình chọn là một trong những giải thuật tiêu biểu nhất của thế kỷ XX.

Trong chuyên đề này, chúng ta sẽ cùng xem xét bài toán sắp xếp các đối tượng trong một tập hợp cố định. Giả sử, ta có một tập hợp gồm $n$ phần tử $a_1, a_2,..., a_n;$ mỗi phần tử có một giá trị $a_i.key$ được gọi là khóa sắp xếp. Khi đó mỗi phần tử có thể được biểu diễn bằng một struct hoặc class, hoặc cũng có thể chỉ là các phần tử đơn lẻ thông thường với kiểu dữ liệu nguyên thủy. Nhiệm vụ đặt ra là cần sắp xếp mảng $a$ gồm $n$ đối tượng thành tập có giá trị khóa tăng dần:

$a_1.key \le a_2.key \le \cdots \le a_n.key$

II. Một số giải thuật sắp xếp thường gặp

1. Sắp xếp nổi bọt (Bubble Sort)

Ý tưởng: Xét các cặp phần tử của dãy, nếu như chúng đang đứng sai thứ tự (phần tử đứng trước lại có khóa lớn hơn phần tử đứng sau) thì đổi chỗ chúng, cho tới khi không còn cặp nào đứng sai thứ tự.

Cài đặt mã giả C++:

void bubble_sort(a[])
{
    for (i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i].key > a[j].key)
                swap(a[i], a[j]);
}

Đánh giá độ phức tạp: Tại lượt duyệt thứ $i$ của vòng lặp bên ngoài, ta cần thực hiện $n - i$ lần phép so sánh a[i].key > a[j].key. Như vậy tổng số phép so sánh là:

$(n - 1) + (n - 2) + \cdots + 1 = \frac{n.(n - 1)}{2}$

Vậy giải thuật có độ phức tạp tương đương $O(n^2)$ . Do đó, trong lập trình thi đấu giải thuật này chỉ phù hợp khi cần sắp xếp những tập hợp có khoảng $2000$ phần tử hoặc ít hơn, nếu nhiều hơn sẽ gây ra quá thời gian chạy (TLE).

Ví dụ 1: Sắp xếp tăng dần mảng $A$ gồm $n$ số nguyên $a_1, a_2,..., a_n?$

void bubble_sort(int a[])
{
    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i] > a[j])
                swap(a[i], a[j]);
}

Ví dụ 2: Một danh sách học sinh gồm $n$ học sinh, mỗi học sinh có $3$ thông số: Tên, Lớp, Điểm tổng kết. Cần sắp xếp các học sinh này theo thứ tự tăng dần về Điểm tổng kết?

Ta có thể biểu diễn danh sách học sinh bằng một mảng $A$ gồm $n$ phần tử kiểu struct lưu ba thông số trên:

struct Student
{
    string name, class; // Tên và lớp.
    double final_point; // Điểm tổng kết.
};

Student a[maxn]; // Mảng A có tối đa maxn phần tử.

Kế đến, áp dụng giải thuật sắp xếp nổi bọt với khóa sắp xếp là trường $\text{final\_point}$ của mỗi phần tử:

void bubble_sort(Student a[])
{
    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (a[i].final_point > a[j].final_point)
                swap(a[i], a[j]);
}

2. Sắp xếp nhanh (Quick Sort)

Giải thuật Sắp xếp nổi bọt chưa đủ tốt với các trường hợp tập sắp xếp có kích thước lớn. Trong trường hợp đó, ta cần một giải thuật tốt hơn, đó là Sắp xếp nhanh.

Ý tưởng: Coi rằng ta đang cần sắp xếp một đoạn có chỉ số từ $1$ tới $n$ trên mảng. Để sắp xếp một đoạn $a_{l...r}$ trong dãy, ta làm như sau:

Nếu đoạn đó chỉ gồm $1$ phần tử thì nó đã được sắp xếp.
Nếu đoạn đó có nhiều hơn $1$ phần tử, chọn giá trị $a[mid]$ nằm giữa đoạn làm chốt. Kế đến, ta hoán đổi các phần tử ở hai bên của chốt sao cho: Mọi phần tử có khóa sắp xếp nhỏ hơn khóa của chốt sẽ đứng sang bên trái nó, mọi phần tử có khóa sắp xếp lớn hơn khóa của chốt sẽ đứng sang bên phải nó.
Tiếp tục sắp xếp theo kiểu trên với hai đoạn con ở hai bên, cuối cùng ta sẽ thu được mảng ban đầu sắp xếp tăng dần theo khóa.

Mã giả C++: Chọn $a_{mid}$ là phần tử ở giữa đoạn $(l, r),$ đồng thời duy trì hai biến $i = l, j = r$ . Chạy $i$ sang phải và $j$ sang trái, nếu phát hiện một cặp vị trí sai thứ tự: $i \le j$ và $a_i.key \ge a_{mid}.key \ge a_j.key$ thì hoán đổi vị trí của chúng. Duy trì làm như vậy tới khi $i > j,$ rồi tiếp tục gọi đệ quy để sắp xếp hai đoạn con trái - phải:

void quick_sort(l, r, a[])
{
    i = l, j = r;
    mid = (l + r) / 2;
    
    while (i <= j)
    {
        // Tìm cặp (i, j) bị đứng sai thứ tự.
        while (a[i].key < a[mid].key)
            ++i;
        while (a[j].key > a[mid].key)
            --j;
            
        // Nếu i <= j thì đây là một cặp sai thứ tự, cần đổi chỗ.
        if (i <= j)
        {
            swap(a[i], a[j]);
            i = i + 1;
            j = j - 1;
        }
    }
    
    // Nếu đoạn [l, j] có nhiều hơn 1 phần tử thì sắp xếp nó.
    if (l < j)
        quick_sort(l, j, a);
    // Nếu đoạn [i, r] có nhiều hơn 1 phần tử thì sắp xếp nó.
    if (i < r)
        quick_sort(i, r, a);
}

Ở chương trình chính, khi cần sắp xếp một mảng thì chỉ cần gọi hàm quick_sort(a, 1, n) là được!

Đánh giá độ phức tạp:

Quick Sort là một giải thuật sắp xếp không ổn định, vì độ phức tạp của nó có thể thay đổi tùy thuộc vào cách lựa chọn phần tử làm chốt của lập trình viên. Tuy nhiên, nếu như ta luôn luôn chọn chốt là phần tử ở giữa của đoạn cần sắp xếp, thì các tính toán thực tế cho thấy, Quick Sort sẽ có độ phức tạp trung bình là $O(n.\log(n))$ . Trường hợp xấu nhất là $O(n^2),$ nếu như bạn chia đoạn cần sắp xếp thành hai mảng con với một bên có $1$ phần tử và bên còn lại chứa các phần tử khác, tuy nhiên trường hợp này chỉ là trên lý thuyết, còn với cách cài đặt ở đây thì tỉ lệ xảy ra là cực kỳ thấp.
Trên thực tế, đối với những bạn code bằng C++ hoặc những ngôn ngữ bậc cao hơn, thì việc cài đặt lại giải thuật Quick Sort là không cần thiết, vì các ngôn ngữ này đều đã hỗ trợ xây dựng sẵn hàm sắp xếp bằng chính giải thuật Quick Sort, người dùng chỉ cần tùy biến để điều chỉnh cách sắp xếp theo ý mình. Ở đây, mình cài đặt chi tiết về giải thuật chỉ với mục tiêu giúp các bạn hiểu hơn về nguyên lí của giải thuật, từ đó hiểu hơn về cách sử dụng của Hàm sắp xếp trong C++ (sẽ được giới thiệu chi tiết ở phần $\text{IV}$ ).

Ví dụ 1: Sắp xếp tăng dần mảng $A$ gồm $n$ phần tử số nguyên $a_1, a_2,..., a_n$ :

void quick_sort(int l, int r, int a[])
{
    int i = l, j = r;
    int mid = (l + r) / 2;
    
    while (i <= j)
    {
        while (a[i] < a[mid])
            ++i;
        while (a[j] > a[mid])
            --j;
            
        if (i <= j)
        {
            swap(a[i], a[j]);
            i = i + 1;
            j = j - 1;
        }
    }
    
    if (l < j)
        quick_sort(l, j, a);
    if (i < r)
        quick_sort(i, r, a);
}

main()
{
    {Nhập_mảng_a};
    
    quick_sort(1, n, a);
    
    {In_mảng};
}

Ví dụ 2: Một danh sách hàng hóa gồm $n$ món hàng, mỗi món có hai thông số là Giá và Số lượng. Cần sắp xếp lại danh sách hàng hóa theo thứ tự tăng dần về giá, nếu hai món hàng có giá bằng nhau thì xếp chúng giảm dần theo số lượng?

Với bài toán này, ta sử dụng một mảng $A$ gồm các phần tử kiểu pair < int, int > để kiểm soát Giá và Số lượng của các món hàng. Đồng thời, cần viết trước một hàm để kiểm tra xem một phần tử $a_i$ có đang nằm sai vị trí so với phần tử $a_j$ hay không? Coi rằng $a_i$ là phần tử đứng trước và $a_j$ là phần tử đứng sau, thì thứ tự đúng phải là: $a_i.first < a_j.first$ hoặc $(a_i.first = a_j.first \text{ and } a_i.second > a_j.second)$ .

// a_left, a_right đại diện cho hai phần tử a[i] và a[j].
bool cmp(pair < int, int > a_left, pair < int, int > a_right)
{
    return (a_left.first < a_right.first
            || (a_left.first == a_right.first && a_left.second > a_right.second));
}

Sử dụng hàm trên để kiểm tra một cặp $(a_i, a_j)$ trong đoạn cần sắp xếp có nằm đúng vị trí so với $a_{mid}$ hay không, nếu không thì cần đổi chỗ chúng:

void quick_sort(int l, int r, pair < int, int > a[])
{
    int i = l, j = r;
    int mid = (l + r) / 2;

    while (i <= j)
    {
        while (cmp(a[i], a[mid]))
            ++i;
        while (cmp(a[mid], a[j]))
            --j;

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

    if (l < j)
        quick_sort(l, j, a);
    if (i < r)
        quick_sort(i, r, a);
}

3. Sắp xếp bằng đếm phân phối (Counting Sort)

3.1. Kĩ thuật đếm phân phối

Đếm phân phối là một kĩ thuật khá hữu ích khi cần đếm số lượng các phần tử trong một mảng. Tạo mảng $freq[v]$ là số lượng giá trị $v$ trong mảng $A$ gồm $n$ phần tử, ta xây dựng mảng này như sau:

for (int i = 1; i <= n; ++i)
    freq[a[i]] = freq[a[i]] + 1;

Kĩ thuật này sử dụng được trong nhiều bài toán, với điều kiện phải tạo ra được một mảng $freq$ có kích thước $m$ - với $m$ là giá trị lớn nhất có thể trong mảng $A$ . Việc $m$ tối đa có thể bằng bao nhiêu sẽ phụ thuộc nhiều vào trình biên dịch, nhưng đối với C++ và kinh nghiệm của người viết, thì $m$ chỉ nên đạt tới khoảng $10^8$ với kiểu int và khoảng $10^7$ với kiểu long long (điều này liên quan tới việc tính toán bộ nhớ khi khai báo mảng, tổng bộ nhớ sử dụng trong cả bài không được vượt quá giới hạn bộ nhớ của đề bài cho phép - thông thường là $512MB$ ).

3.2. Áp dụng đếm phân phối trong sắp xếp

Bây giờ, ứng dụng đếm phân phối, ta sẽ đếm các giá trị khóa của dãy $A$ bằng mảng $freq[a_i.key]$ . Giả sử các khóa sắp xếp khác nhau trong dãy lần lượt là $0, 1, 2,..., k$ thì sau khi sắp xếp, ta có:

Các phần tử có khóa bằng $0$ sẽ nằm từ vị trí $1$ tới vị trí $freq[0]$ .
Các phần tử có khóa bằng $1$ sẽ nằm từ vị trí $freq[0] + 1$ tới vị trí $freq[0] + freq[1]$ .
Các phần tử có khóa bằng $2$ sẽ nằm từ vị trí $freq[0] + freq[1] + 1$ tới vị trí $freq[0] + freq[1] + freq[2]$ . $...$
Các phần tử có khóa bằng $k$ sẽ nằm từ vị trí $freq[0] + freq[1] + \cdots + freq[k - 1] + 1$ tới vị trí $freq[0] + freq[1] + \cdots + freq[k]$ .

Cài đặt mã giả C++:

void counting_sort(a[])
{
    for (i = 1; i <= n; ++i)
        freq[a[i].key] = freq[a[i].key] + 1;

    pos = 1;
    for (key = key_min; key <= key_max; ++key)
        for (i = 1; i <= freq[key]; ++i)
        {
            a[pos] = key;
            pos = pos + 1;
        }   
}

Đánh giá độ phức tạp: Giải thuật sắp xếp bằng đếm phân phối sẽ có độ phức tạp là $O\big(\text{max}(n, k)\big),$ do tổng số lần thực hiện cập nhật lại các phần tử trên mảng chỉ là $n$ lần, nhưng ta phải duyệt qua $k$ khóa khác nhau. Đây là một giải thuật tốt trong trường hợp các khóa sắp xếp trong mảng không quá lớn. Nếu như khóa quá lớn, không thể khởi tạo được mảng tần số thì ta cần áp dụng tới kĩ thuật Rời rạc hóa để "nén" các khóa lại thành nhỏ hơn hoặc bằng $n,$ kĩ thuật này sẽ được đề cập ở một chuyên đề khác.

Ví dụ 1: Sắp xếp mảng số nguyên dương $A$ gồm $n$ phần tử có giá trị không vượt quá $10^6$ theo thứ tự tăng dần?

// Mảng freq để đếm các giá trị trong mảng, khóa lớn nhất có thể là 10^6.
int freq[1000001]; 

void counting_sort(int l, int r, int a[])
{
    for (int i = l; i <= r; ++i)
        freq[a[i]]++;
        
    // Tìm giá trị nhỏ nhất và lớn nhất trong đoạn cần sắp xếp.
    int min_key = *min_element(a + l, a + r + 1);
    int max_key = *max_element(a + l, a + r + 1);
    
    int pos = l;
    for (int key = min_key; key <= max_key; ++key)
        for (int i = 1; i <= freq[key]; ++i)
            a[++pos] = key;
}

Ví dụ 2: Cho một dãy kí tự $S$ chỉ gồm toàn các chữ cái latin in thường, hãy tìm ra các kí tự xuất hiện nhiều lần nhất trong dãy?

Nhận xét ở bài này, khóa của các phần tử là các kí tự. Mảng đếm phân phối không thể dùng trực tiếp chỉ số là các kí tự, nhưng ta có thể mã hóa các kí tự ấy thành các con số dựa trên số hiệu $ASCII$ của từng kí tự. Vậy chỉ cần khai báo một mảng $freq[26]$ và mã hóa các kí tự thành số hiệu của chúng sau khi trừ đi số hiệu của kí tự a:

int freq[26];

void find_character_with_maximum_freq(string s)
{
    for (int i = 0; i < s.size; ++i)
        freq[s[i] - 'a']++;
    
    // Tìm số lần xuất hiện nhiều nhất của một kí tự trong mảng freq[].
    int maximum_freq = *max_element(freq, freq + 25 + 1);
    for (int key = 0; key <= 25; ++key)
        if (freq[key] == maximum_freq)
            cout << (char)(key + 'a') << endl;
}

III. Hàm sắp xếp trong thư viện STL C++

Trong thư viện STL của C++ cung cấp sẵn một hàm sắp xếp sử dụng giải thuật Quick Sort. Để sử dụng hàm này, các bạn cần khai báo thư viện <algorithm> và không gian tên using namespace std. Dưới đây là hướng dẫn sử dụng hàm chi tiết:

1. Hàm sắp xếp cơ bản

Thư viện thuật toán cung cấp một hàm sắp xếp có thể sắp xếp các kiểu dữ liệu bao gồm số, kí tự, chuỗi kí tự và cả các kiểu dữ liệu tự định nghĩa của người dùng. Cú pháp như sau:

sort(l, r);

Trong đó, $l$ và $r$ là hai biến trỏ vào địa chỉ của phần tử đầu và phần tử cuối trong đoạn cần sắp xếp. Hàm sẽ sắp xếp toàn bộ các phần tử thuộc đoạn $[l, r - 1]$ . Tuy nhiên hàm sort() sẽ đứng đơn lẻ chứ không đi kèm các câu lệnh khác. Mặc định hàm sort() sẽ sắp xếp các phần tử trong đoạn cần sắp xếp theo thứ tự tăng dần (số hoặc kí tự theo đúng quy tắc riêng của mỗi kiểu dữ liệu).

Ví dụ:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a[] = {5, 2, 10, 3, 1};
    vector < int > v;
    v.push_back(-10);
    v.push_back(5);
    v.push_back(2);
    v.push_back(9); // v = {-10, 5, 2, 9}.

    // Sắp xếp mảng và vector tăng dần.
    sort(a, a + 4 + 1); // a = {1, 2, 3, 5, 10}.
    sort(v.begin(), v.end()); // v = {-10, 2, 5, 9}.

    // In ra kết quả sắp xếp.
    cout << "Kết quả sắp xếp: " << endl;
    for (int i = 0; i < 5; ++i)
        cout << a[i] << ' ';
    cout << endl;
    for (int i = 0; i < 4; ++i)
        cout << v[i] << ' ';

    return 0;
}

Kết quả chạy chương trình trên như sau:

Kết quả sắp xếp:
1 2 3 5 10
-10 2 5 9

2. Tùy biến việc sắp xếp theo ý thích

Hàm sắp xếp thực tế còn có một tham số thứ ba, dùng để điều chỉnh việc sắp xếp theo ý muốn của người dùng. Cú pháp dạng này của hàm sắp xếp là:

sort(l, r, cmp);

Trong đó, cmp là một hàm kiểu boolean do người dùng tự định nghĩa, hoặc là một trong hai từ khóa thể hiện phép so sánh: less hoặc greater.

2.1. Sử dụng 2 phép toán `less` và `greater`

Hai từ khóa less và greater thể hiện cho hai phép toán sắp xếp tăng dần hoặc giảm dần (thực ra chính là thể hiện của các toán tử < và >), khi muốn điều chỉnh cách sắp xếp ta chỉ cần thêm hai phép toán này vào tham số thứ ba của hàm sắp xếp theo cú pháp:

sort(l, r, greater < {Kiểu_phần_tử} >());
sort(l, r, less < {Kiểu_phần_tử} >());

Trong đó, {Kiểu_phần_tử} là kiểu dữ liệu của các phần tử trong tập hợp cần sắp xếp.

Ví dụ:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a[] = {5, 2, 10, 3, 1};

    sort(a, a + 4 + 1); // a = {1, 2, 3, 5, 10}.

    // In ra kết quả sắp xếp.
    cout << "Sắp xếp tăng dần: " << endl;
    for (int i = 0; i < 5; ++i)
        cout << a[i] << ' ';
    cout << endl;

    sort(a, a + 4 + 1, greater < int >()); // a = {10, 5, 3, 2, 1}.

    cout << "Sắp xếp giảm dần: " << endl;
    for (int i = 0; i < 4; ++i)
        cout << a[i] << ' ';

    return 0;
}

Kết quả chạy chương trình trên như sau:

Sắp xếp tăng dần:
1 2 3 5 10
Sắp xếp giảm dần:
10 5 3 2 1

Lưu ý:

Phép so sánh mặc định của hàm sort là less, do đó nếu muốn sắp xếp tăng dần ta không cần thêm từ khóa less mà chỉ cần viết hàm sắp xếp và bỏ qua tham số thứ ba là được.
Đối với tập hợp gồm các phần tử kiểu pair, hàm sắp xếp sẽ tự động sắp xếp ưu tiên theo trường giá trị first, nếu như hai phần tử trước sau có trường first bằng nhau thì mới xét tới trường second. Cụ thể, phép toán less sẽ ưu tiên sắp xếp các phần tử tăng dần theo trường giá trị first, nếu trường first bằng nhau thì sẽ sắp xếp tăng dần theo trường giá trị second; tương tự với phép toán greater.

2.2. Sử dụng hàm sắp xếp tự định nghĩa

Khi muốn sắp xếp theo những cách riêng, ví dụ như sắp xếp các số chẵn ra phía đầu, số lẻ ra phía cuối, hoặc khi kiểu dữ liệu của tập cần sắp xếp là những kiểu dữ liệu do người dùng tự định nghĩa, ta có thể tự viết ra một hàm cmp dùng làm tham số thứ ba cho hàm sort. Cú pháp như sau:

bool cmp({Tham_số_thứ_nhất}, {Tham_số_thứ_hai})
{
    {Định_nghĩa_quan_hệ_so_sánh_giữa_hai_tham_số};
}

Trong đó, {Tham_số_thứ_nhất} đại diện cho phần tử đứng trước, {Tham_số_thứ_hai} đại diện cho phần tử đứng sau trong dãy. Hàm sort() sẽ tự động sắp xếp lại các phần tử theo thứ tự bạn quy định giống như hai tham số này. Lấy ví dụ, nếu ta muốn sắp xếp một dãy số nguyên giảm dần, bạn cũng có thể viết như sau:

#include <bits/stdc++.h>

using namespace std;

bool cmp(int A, int B)
{
    return A > B;
}

int main()
{
    int a[] = {5, 2, 10, 3, 1};

    // Sắp xếp mảng.
    sort(a, a + 5, cmp); // a = {10, 5, 3, 2, 1}.

    // In ra kết quả sắp xếp.
    cout << "Kết quả sắp xếp: " << endl;
    for (int i = 0; i < 5; ++i)
        cout << a[i] << ' ';

    return 0;
}

Biên dịch và chạy chương trình trên sẽ cho ra kết quả:

Kết quả sắp xếp:
10 5 3 2 1

IV. Tài liệu tham khảo