Bài 16.1: Thuật toán sắp xếp chọn trong C++

Chào mừng bạn đến với một bài viết khác trong series C++ của chúng ta! Hôm nay, chúng ta sẽ cùng khám phá một trong những thuật toán sắp xếp cơ bản và dễ hiểu nhất: Thuật toán sắp xếp chọn (Selection Sort). Mặc dù không phải là thuật toán hiệu quả nhất cho các tập dữ liệu lớn, nhưng nó là viên gạch nền tảng quan trọng để hiểu về thế giới thuật toán sắp xếp.

Tại Sao Chúng Ta Cần Sắp Xếp Dữ Liệu?

Trong lập trình, việc sắp xếp dữ liệu là một thao tác vô cùng phổ biến và cần thiết. Dữ liệu được sắp xếp giúp chúng ta:

Tìm kiếm dễ dàng hơn: Các thuật toán tìm kiếm hiệu quả như tìm kiếm nhị phân chỉ hoạt động trên dữ liệu đã sắp xếp.
Phân tích dữ liệu: Dữ liệu có thứ tự giúp việc phân tích, thống kê trở nên trực quan và nhanh chóng hơn.
Thao tác trên dữ liệu: Nhiều thuật toán khác yêu cầu dữ liệu đầu vào phải được sắp xếp.

Có rất nhiều thuật toán sắp xếp khác nhau, mỗi loại có ưu và nhược điểm riêng. Selection Sort là một điểm khởi đầu tuyệt vời để tìm hiểu về cách các thuật toán này hoạt động.

Thuật Toán Sắp Xếp Chọn (Selection Sort) Hoạt Động Như Thế Nào?

Ý tưởng cốt lõi của Selection Sort cực kỳ đơn giản:

Chia mảng/danh sách thành hai phần: một phần đã được sắp xếp (ban đầu rỗng) và một phần chưa được sắp xếp (ban đầu là toàn bộ mảng).
Lặp đi lặp lại các bước sau cho đến khi phần chưa được sắp xếp rỗng:
- Tìm phần tử nhỏ nhất trong phần chưa được sắp xếp.
- Hoán đổi (swap) phần tử nhỏ nhất đó với phần tử đầu tiên của phần chưa được sắp xếp.
- Di chuyển ranh giới giữa phần đã sắp xếp và chưa sắp xếp tiến lên một vị trí.

Nói cách khác, ở mỗi bước lặp, chúng ta "chọn" phần tử nhỏ nhất còn lại và đặt nó vào đúng vị trí của nó ở đầu phần chưa sắp xếp.

Hãy minh hoạ một chút nhé. Giả sử ta có mảng [64, 25, 12, 22, 11].

Bước 1:
- Mảng chưa sắp xếp: [64, 25, 12, 22, 11]
- Phần tử nhỏ nhất trong mảng này là 11. Vị trí của nó là index 4.
- Phần tử đầu tiên của phần chưa sắp xếp (toàn bộ mảng lúc này) là 64 ở index 0.
- Hoán đổi 64 và 11.
- Mảng trở thành: [11, 25, 12, 22, 64]
- Phần đã sắp xếp: [11]. Phần chưa sắp xếp: [25, 12, 22, 64].
Bước 2:
- Mảng chưa sắp xếp: [25, 12, 22, 64] (từ index 1 trở đi).
- Phần tử nhỏ nhất trong phần này là 12. Vị trí của nó là index 2 (trong mảng gốc).
- Phần tử đầu tiên của phần chưa sắp xếp là 25 ở index 1.
- Hoán đổi 25 (ở index 1) và 12 (ở index 2).
- Mảng trở thành: [11, 12, 25, 22, 64]
- Phần đã sắp xếp: [11, 12]. Phần chưa sắp xếp: [25, 22, 64].
Bước 3:
- Mảng chưa sắp xếp: [25, 22, 64] (từ index 2 trở đi).
- Phần tử nhỏ nhất trong phần này là 22. Vị trí của nó là index 3.
- Phần tử đầu tiên của phần chưa sắp xếp là 25 ở index 2.
- Hoán đổi 25 (ở index 2) và 22 (ở index 3).
- Mảng trở thành: [11, 12, 22, 25, 64]
- Phần đã sắp xếp: [11, 12, 22]. Phần chưa sắp xếp: [25, 64].
Bước 4:
- Mảng chưa sắp xếp: [25, 64] (từ index 3 trở đi).
- Phần tử nhỏ nhất trong phần này là 25. Vị trí của nó là index 3.
- Phần tử đầu tiên của phần chưa sắp xếp là 25 ở index 3.
- Hoán đổi 25 (ở index 3) và 25 (ở index 3). (Không có gì thay đổi).
- Mảng trở thành: [11, 12, 22, 25, 64]
- Phần đã sắp xếp: [11, 12, 22, 25]. Phần chưa sắp xếp: [64].
Bước 5:
- Phần chưa sắp xếp chỉ còn [64]. Chỉ có một phần tử thì nó đã ở đúng vị trí rồi.
- Quá trình kết thúc. Mảng đã được sắp xếp hoàn chỉnh: [11, 12, 22, 25, 64].

Như bạn thấy, thuật toán này đảm bảo rằng sau mỗi bước lặp chính, một phần tử nữa sẽ được đặt vào đúng vị trí cuối cùng của nó.

Triển Khai Thuật Toán Sắp Xếp Chọn Bằng C++

Bây giờ, hãy chuyển ý tưởng này thành code C++. Chúng ta sẽ viết một hàm để thực hiện sắp xếp chọn trên một mảng các số nguyên.

#include <iostream> // Để sử dụng cout
#include <algorithm> // Để sử dụng swap (hoán đổi giá trị)
#include <vector> // Có thể sử dụng vector thay cho mảng truyền thống

// Hàm để in mảng
void printArray(const int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Hàm thực hiện thuật toán sắp xếp chọn
void selectionSort(int arr[], int n) {
    // Vòng lặp ngoài: duyệt qua mảng từ đầu đến gần cuối.
    // Biến 'i' đánh dấu ranh giới giữa phần đã sắp xếp (từ 0 đến i-1)
    // và phần chưa sắp xếp (từ i đến n-1).
    for (int i = 0; i < n - 1; ++i) {
        // Giả sử phần tử đầu tiên của phần chưa sắp xếp (arr[i]) là nhỏ nhất
        int minIndex = i;

        // Vòng lặp trong: tìm phần tử nhỏ nhất trong phần chưa sắp xếp (từ arr[i+1] đến arr[n-1])
        for (int j = i + 1; j < n; ++j) {
            // Nếu tìm thấy phần tử nhỏ hơn phần tử nhỏ nhất hiện tại
            if (arr[j] < arr[minIndex]) {
                // Cập nhật chỉ số của phần tử nhỏ nhất
                minIndex = j;
            }
        }

        // Sau khi vòng lặp trong kết thúc, minIndex là chỉ số của phần tử nhỏ nhất
        // trong phần chưa sắp xếp (arr[i] đến arr[n-1]).
        // Hoán đổi phần tử nhỏ nhất này với phần tử đầu tiên của phần chưa sắp xếp (arr[i]).
        // swap là một hàm tiện ích trong thư viện <algorithm>
        swap(arr[i], arr[minIndex]);

        // Lúc này, arr[i] đã chứa phần tử nhỏ nhất và nằm ở đúng vị trí cuối cùng của nó.
        // Vòng lặp ngoài sẽ tiếp tục với i+1, mở rộng phần đã sắp xếp.
    }
}

int main() {
    // Khởi tạo một mảng dữ liệu để sắp xếp
    int data[] = {64, 25, 12, 22, 11};
    int n = sizeof(data) / sizeof(data[0]); // Tính kích thước mảng

    cout << "Mang truoc khi sap xep: ";
    printArray(data, n);

    // Gọi hàm sắp xếp chọn để sắp xếp mảng
    selectionSort(data, n);

    cout << "Mang sau khi sap xep:  ";
    printArray(data, n);

    // Một ví dụ khác với mảng khác
    int moreData[] = {5, 4, 3, 2, 1, 10, 8};
    int m = sizeof(moreData) / sizeof(moreData[0]);

    cout << "\n---"; // Ngăn cách ví dụ
    cout << "\nMang truoc khi sap xep (vi du 2): ";
    printArray(moreData, m);

    selectionSort(moreData, m);

    cout << "Mang sau khi sap xep (vi du 2):  ";
    printArray(moreData, m);


    // Sử dụng với vector (cần thay đổi hàm sort một chút)
    // vector<int> vecData = {99, 1, 50, 5, 75};
    // cout << "\n---";
    // cout << "\nVector truoc khi sap xep: ";
    // for (int x : vecData) cout << x << " "; cout << endl;
    // // Cần viết lại hàm selectionSort nhận vector
    // // selectionSortVector(vecData);
    // // cout << "Vector sau khi sap xep:  ";
    // // for (int x : vecData) cout << x << " "; cout << endl;


    return 0;
}

Giải thích code C++

#include <iostream>: Thư viện chuẩn để làm việc với nhập/xuất dữ liệu (như cout để in ra màn hình).
#include <algorithm>: Thư viện này chứa các hàm tiện ích mạnh mẽ, trong đó có swap(), giúp chúng ta hoán đổi giá trị của hai biến một cách an toàn và hiệu quả. Việc sử dụng swap giúp code ngắn gọn và dễ đọc hơn là tự viết hàm hoán đổi.
void printArray(const int arr[], int size): Một hàm trợ giúp đơn giản để in nội dung của mảng ra màn hình. const ở đây nghĩa là hàm này sẽ không thay đổi nội dung của mảng được truyền vào.
void selectionSort(int arr[], int n): Đây là hàm chính chứa logic của thuật toán sắp xếp chọn.
- int arr[]: Mảng số nguyên cần sắp xếp.
- int n: Kích thước của mảng.
for (int i = 0; i < n - 1; ++i): Đây là vòng lặp ngoài. Nó lặp từ chỉ số 0 đến n-2.
- Biến i đánh dấu vị trí hiện tại mà chúng ta muốn đặt phần tử nhỏ nhất vào. Sau mỗi lần lặp của vòng ngoài, phần tử tại arr[i] sẽ là phần tử nhỏ nhất trong phần còn lại của mảng (từ index i đến n-1).
- Chúng ta chỉ cần lặp đến n-2 (hay i < n - 1) vì khi phần tử cuối cùng (index n-1) là phần tử duy nhất còn lại trong phần chưa sắp xếp, nó tự động đã ở đúng vị trí của nó.
int minIndex = i;: Ngay trước khi bắt đầu tìm kiếm phần tử nhỏ nhất trong phần chưa sắp xếp, chúng ta giả định rằng phần tử đầu tiên của phần chưa sắp xếp (arr[i]) là nhỏ nhất, và lưu chỉ số của nó vào biến minIndex.
for (int j = i + 1; j < n; ++j): Đây là vòng lặp trong. Nó bắt đầu từ vị trí sau i (i + 1) và duyệt đến hết mảng (n - 1).
- Vòng lặp này có nhiệm vụ tìm kiếm phần tử có giá trị nhỏ nhất trong đoạn mảng từ arr[i+1] đến arr[n-1].
if (arr[j] < arr[minIndex]): Bên trong vòng lặp trong, chúng ta so sánh phần tử hiện tại đang xét (arr[j]) với phần tử nhỏ nhất tìm được cho đến nay (arr[minIndex]).
- Nếu arr[j] nhỏ hơn arr[minIndex], điều đó có nghĩa là chúng ta đã tìm thấy một phần tử còn nhỏ hơn nữa, nên chúng ta cập nhật minIndex = j để ghi nhớ vị trí của phần tử mới này.
swap(arr[i], arr[minIndex]);: Sau khi vòng lặp trong kết thúc, minIndex sẽ chứa chỉ số của phần tử nhỏ nhất trong toàn bộ phần chưa sắp xếp (từ i đến n-1). Chúng ta sử dụng swap để hoán đổi phần tử tại vị trí i (vị trí đầu tiên của phần chưa sắp xếp) với phần tử nhỏ nhất tìm được (tại minIndex). Thao tác này đưa phần tử nhỏ nhất về đúng vị trí của nó.
Hàm main():
- Tạo một mảng số nguyên data.
- Tính kích thước mảng (n) bằng cách chia tổng kích thước mảng (đo bằng byte, sizeof(data)) cho kích thước của một phần tử (đo bằng byte, sizeof(data[0])).
- In mảng trước khi sắp xếp.
- Gọi hàm selectionSort để sắp xếp mảng.
- In mảng sau khi sắp xếp.
- Thêm một ví dụ khác với mảng moreData để minh họa.

Phân Tích Hiệu Suất

Selection Sort là một thuật toán đơn giản, nhưng hiệu suất của nó không cao đối với các tập dữ liệu lớn.

Độ phức tạp thời gian (Time Complexity):
- Vòng lặp ngoài chạy n-1 lần.
- Trong mỗi lần chạy của vòng lặp ngoài (với chỉ số i), vòng lặp trong chạy khoảng n-i-1 lần.
- Số lượng phép so sánh tổng cộng xấp xỉ: (n-1) + (n-2) + ... + 1 = n*(n-1)/2.
- Số lượng phép hoán đổi (swap) tối đa là n-1 (mỗi lần lặp ngoài thực hiện tối đa 1 swap).
- Do số lượng phép so sánh và phép hoán đổi đều tỷ lệ với n^2, nên độ phức tạp thời gian của Selection Sort là O(n^2) trong mọi trường hợp (trường hợp tốt nhất, trung bình và xấu nhất). Điều này có nghĩa là khi kích thước dữ liệu tăng lên gấp đôi, thời gian chạy sẽ tăng lên gấp bốn lần.
Độ phức tạp không gian (Space Complexity):
- Thuật toán này chỉ sử dụng một vài biến phụ trợ (như i, j, minIndex, biến tạm trong swap).
- Nó thực hiện sắp xếp ngay trên mảng ban đầu mà không cần thêm mảng phụ có kích thước đáng kể.
- Do đó, độ phức tạp không gian của Selection Sort là O(1) (không gian hằng số), tức là không gian bộ nhớ cần thiết không phụ thuộc vào kích thước dữ liệu n. Nó là một thuật toán sắp xếp tại chỗ (in-place).

Ưu điểm và Nhược điểm của Selection Sort

Ưu điểm:
- Đơn giản: Rất dễ hiểu và dễ cài đặt.
- Hiệu quả về số lần hoán đổi: Thực hiện số lượng phép hoán đổi tối thiểu (chính xác là n-1 hoán đổi trong trường hợp xấu nhất). Điều này có thể hữu ích trong những tình huống mà chi phí hoán đổi các phần tử là rất cao (ví dụ: các đối tượng lớn).
- Tại chỗ (In-place): Chỉ cần không gian bộ nhớ phụ trợ là O(1).
Nhược điểm:
- Chậm với dữ liệu lớn: Độ phức tạp O(n^2) khiến nó không phù hợp với các tập dữ liệu có kích thước hàng nghìn phần tử trở lên.
- Hiệu suất nhất quán (nhưng kém): Thời gian chạy luôn là O(n^2), ngay cả khi mảng đã gần như được sắp xếp.

Khi nào nên sử dụng Selection Sort?

Mặc dù kém hiệu quả hơn các thuật toán như Quick Sort hay Merge Sort (có độ phức tạp O(n log n)), Selection Sort vẫn có thể được cân nhắc sử dụng trong các trường hợp sau:

Tập dữ liệu rất nhỏ: Đối với mảng chỉ vài chục phần tử, sự khác biệt giữa O(n^2) và O(n log n) là không đáng kể, và sự đơn giản của Selection Sort có thể là một lợi thế.
Khi số lần hoán đổi là yếu tố cực kỳ quan trọng: Nếu việc hoán đổi phần tử tốn kém hơn nhiều so với việc so sánh, Selection Sort có thể được ưu tiên hơn các thuật toán khác thực hiện nhiều hoán đổi hơn (như Bubble Sort).

Bài tập ví dụ: C++ Bài 9.B1: Sắp xếp không giảm

Cho một dãy số \(a\) có \(N\) phần từ \(a_1, a_2, a_3,...a_n\). Hãy sắp xếp dãy \(a\) theo thứ tự không giảm và in dãy sau sắp xếp ra màn hình.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên \(N\) ( \( 1 \leq N \leq 10^5\)).

Dòng thứ hai chứa \(N\) số nguyên, mỗi số các nhau một dấu cách \((|a_i| < 10^{9})\)

OUTPUT FORMAT

In ra dãy \(a\) theo thứ tự không giảm.

Ví dụ 1:

Input

6
5 1 3 2 4 8

Ouput

1 2 3 4 5 8

Giải thích ví dụ mẫu:

Dãy số được nhập vào là [5, 1, 3, 2, 4, 8], sau khi sắp xếp ta thu được dãy [1, 2, 3, 4, 5, 8].

<br>

Hướng giải chi tiết:

Đọc dữ liệu đầu vào:
- Đầu tiên, bạn cần đọc số nguyên N từ dòng đầu tiên.
- Tiếp theo, bạn cần đọc N số nguyên trên dòng thứ hai.
Lưu trữ dữ liệu:
- Để có thể sắp xếp, bạn cần lưu trữ N số nguyên này vào một cấu trúc dữ liệu phù hợp. Trong C++, vector là lựa chọn rất tốt cho việc này. vector là một mảng động có kích thước có thể thay đổi (mặc dù ở đây ta biết trước kích thước là N), rất linh hoạt và dễ sử dụng với các thuật toán chuẩn.
- Bạn sẽ khai báo một vector chứa kiểu dữ liệu là int (vì giá trị các số a_i nằm trong khoảng |a_i| < 10^9, phù hợp với kiểu int).
- Sau khi đọc N, bạn có thể tạo vector có kích thước N ngay lập tức, hoặc tạo vector rỗng rồi dùng vòng lặp để đọc và thêm từng phần tử vào.
Sắp xếp:
- C++ Standard Library cung cấp hàm sort trong thư viện <algorithm>. Đây là hàm sắp xếp rất hiệu quả (thường sử dụng thuật toán lai như Introsort) và là cách chuẩn để sắp xếp trong C++.
- Hàm sort nhận vào hai tham số là con trỏ hoặc iterator trỏ đến điểm bắt đầu và điểm kết thúc của dãy cần sắp xếp.
- Đối với vector, bạn có thể lấy iterator đến phần tử đầu tiên bằng phương thức .begin() và iterator đến vị trí sau phần tử cuối cùng bằng phương thức .end().
- Gọi sort với hai iterator này sẽ sắp xếp toàn bộ vector theo thứ tự không giảm (đây là hành vi mặc định của sort).
In kết quả:
- Sau khi vector đã được sắp xếp, bạn cần in các phần tử ra màn hình, cách nhau bởi một dấu cách.
- Dùng một vòng lặp để duyệt qua các phần tử của vector đã sắp xếp.
- In từng phần tử.
- Cần chú ý in dấu cách giữa các phần tử. Một cách phổ biến là in phần tử đầu tiên trước, sau đó dùng vòng lặp in các phần tử còn lại, mỗi phần tử có dấu cách đứng trước. Hoặc in tất cả các phần tử với một dấu cách phía sau, ngoại trừ phần tử cuối cùng (cần xử lý trường hợp đặc biệt cho phần tử cuối). Cách đơn giản hơn trong lập trình thi đấu là in tất cả với dấu cách sau, đôi khi vẫn được chấp nhận nếu đề bài không quá khắt khe về định dạng dấu cách cuối cùng.

Các thư viện C++ cần dùng:

<iostream> để đọc dữ liệu và in kết quả.
<vector> để sử dụng vector.
<algorithm> để sử dụng sort.

Lưu ý về hiệu suất: Với N lên đến 10^5, các thuật toán sắp xếp đơn giản O(N^2) (như Selection Sort, Bubble Sort, Insertion Sort) sẽ quá chậm. sort có độ phức tạp trung bình O(N log N), rất phù hợp với giới hạn N của bài toán.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.