Các thuật toán tìm kiếm và sắp xếp năm 2024

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%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 nn phần tử a1,a2,...,an;a_1, a_2,..., a_n; mỗi phần tử có một giá trị ai.keya_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 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ử.

2 hoặc

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ử.

3, 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 aa gồm nn đối tượng thành tập có giá trị khóa tăng dần:

a1.key≤a2.key≤⋯≤an.keya_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ứ ii của vòng lặp bên ngoài, ta cần thực hiện n−in - i lần phép so sánh

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ử.

4. Như vậy tổng số phép so sánh là:

(n−1)+(n−2)+⋯+1=n.(n−1)2(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(n2)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 20002000 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 AA gồm nn số nguyên a1,a2,...,an?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 nn học sinh, mỗi học sinh có 33 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 AA gồm nn phần tử kiểu

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ử.

2 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ừ 11 tới nn trên mảng. Để sắp xếp một đoạn al...ra_{l...r} trong dãy, ta làm như sau:

• Nếu đoạn đó chỉ gồm 11 phần tử thì nó đã được sắp xếp.
• Nếu đoạn đó có nhiều hơn 11 phần tử, chọn giá trị a[mid]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 amida_{mid} là phần tử ở giữa đoạn (l,r),(l, r), đồng thời duy trì hai biến i=l,j=ri = l, j = r. Chạy ii sang phải và jj sang trái, nếu phát hiện một cặp vị trí sai thứ tự: i≤ji \le j và ai.key≥amid.key≥aj.keya_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,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

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ử.

6 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))O(n.\log(n)). Trường hợp xấu nhất là O(n2),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ó 11 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 IV\text{IV}).

Ví dụ 1: Sắp xếp tăng dần mảng AA gồm nn phần tử số nguyên a1,a2,...,ana_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 nn 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 AA gồm các phần tử kiểu

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ử.

7 để 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ử aia_i có đang nằm sai vị trí so với phần tử aja_j hay không? Coi rằng aia_i là phần tử đứng trước và aja_j là phần tử đứng sau, thì thứ tự đúng phải là: ai.firstaj.second)(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 (ai,aj)(a_i, a_j) trong đoạn cần sắp xếp có nằm đúng vị trí so với amida_{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]freq[v] là số lượng giá trị vv trong mảng AA gồm nn 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 freqfreq có kích thước mm - với mm là giá trị lớn nhất có thể trong mảng AA. Việc mm 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ì mm chỉ nên đạt tới khoảng 10810^8 với kiểu

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ử.

8 và khoảng 10710^7 với kiểu

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ử.

9 (đ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à 512MB512MB).

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 AA bằng mảng freq[ai.key]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,...,k0, 1, 2,..., k thì sau khi sắp xếp, ta có:

• Các phần tử có khóa bằng 00 sẽ nằm từ vị trí 11 tới vị trí freq[0]freq[0].
• Các phần tử có khóa bằng 11 sẽ nằm từ vị trí freq[0]+1freq[0] + 1 tới vị trí freq[0]+freq[1]freq[0] + freq[1].
• Các phần tử có khóa bằng 22 sẽ nằm từ vị trí freq[0]+freq[1]+1freq[0] + freq[1] + 1 tới vị trí freq[0]+freq[1]+freq[2]freq[0] + freq[1] + freq[2].......
• Các phần tử có khóa bằng kk sẽ nằm từ vị trí freq[0]+freq[1]+⋯+freq[k−1]+1freq[0] + freq[1] + \cdots + freq[k - 1] + 1 tới vị trí freq[0]+freq[1]+⋯+freq[k]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(max(n,k)),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à nn lần, nhưng ta phải duyệt qua kk 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,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 AA gồm nn phần tử có giá trị không vượt quá 10610^6 theo thứ tự tăng dầ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]);
}

0

Ví dụ 2: Cho một dãy kí tự SS 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 ASCIIASCII của từng kí tự. Vậy chỉ cần khai báo một mảng freq[26]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ự

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]);
}

0:

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]);
}

1

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

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]);
}

1 và không gian tên

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. 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:

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]);
}

2

Trong đó, ll và rr 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][l, r - 1]. Tuy nhiên hàm

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]);
}

3 sẽ đứng đơn lẻ chứ không đi kèm các câu lệnh khác. Mặc định hàm

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]);
}

3 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ụ:

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]);
}

3

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

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]);
}

4

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à:

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]);
}

5

Trong đó,

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]);
}

5 là một hàm kiểu

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]);
}

6 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:

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]);
}

7 hoặc

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]);
}

8.

2.1. Sử dụng 2 phép toán

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]);
}

7 và

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]);
}

8

Hai từ khóa

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]);
}

7 và

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]);
}

8 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ử

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);
}

3 và

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);
}

4), 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:

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]);
}

6

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ụ:

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]);
}

7

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

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]);
}

8

Lưu ý:

• Phép so sánh mặc định của hàm sort là

  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]);  
  

  }

  7, do đó nếu muốn sắp xếp tăng dần ta không cần thêm từ khóa

  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]);  
  

  }
  7 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

  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);  
  

  }

  7, hàm sắp xếp sẽ tự động sắp xếp ưu tiên theo trường giá trị

  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);  
  

  }

  8, nếu như hai phần tử trước sau có trường

  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);  
  

  }

  8 bằng nhau thì mới xét tới trường

  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};  
  

  }

  0. Cụ thể, phép toán

  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]);  
  

  }

  7 sẽ ưu tiên sắp xếp các phần tử tăng dần theo trường giá trị

  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);  
  

  }

  8, nếu trường

  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);  
  

  }

  8 bằng nhau thì sẽ sắp xếp tăng dần theo trường giá trị

  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};  
  

  }

  0; tương tự với phép toán

  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]);  
  

  }
  8.

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

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]);
}

5 dùng làm tham số thứ ba cho hàm

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};
}

7. Cú pháp như sau:

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]);
}

9

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

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]);
}

3 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:

Thuật toán sắp xếp chọn tìm kiếm thế nào?

Sắp xếp chọn là một thuật toán sắp xếp đơn giản, dựa trên việc so sánh tại chỗ. Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2.

Thế nào là thuật toán sắp xếp?

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số. Bài toán sắp xếp đã được nhiều nhà khoa học quan tâm.

Thuật toán sắp xếp một dãy các so nguyên theo thứ tự tăng dần là thuật toán gì?

Selection Sort Algorithm (sắp xếp chọn lọc): Thuật toán này sẽ liên tục chọn phần tử hay dữ liệu có giá trị nhỏ và sẽ đưa nó lên đầu, và sẽ tiếp tục lặp lại việc chọn phần tử để sắp xếp dãy số theo thứ tự tăng dần.

Tại mỗi bước sắp xếp của phương pháp sắp xếp nổi bọt đậy so được duyệt bắt đầu từ đâu?

Bắt đầu từ vị trí đầu tiên của danh sách (bên trái), so sánh các cặp số với nhau, nếu không đúng thứ tự nhỏ-lớn thì đảo vị trí. Sau khi chạy tới cuối danh sách, tiếp tục chạy lại từ vị trí đầu danh sách cho đến khi hoàn thành so sánh và đảo vị trí.