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

Chào mừng bạn đến với bài học về một trong những thuật toán sắp xếp cơ bản nhất, nhưng cũng đầy tinh tế và hữu ích trong một số trường hợp: Thuật toán sắp xếp chèn (Insertion Sort). Nếu bạn đã từng sắp xếp các quân bài trong tay khi chơi một trò chơi nào đó, bạn đã vô tình sử dụng ý tưởng cốt lõi của thuật toán này rồi đấy! Bài viết này sẽ đi sâu vào cách Insertion Sort hoạt động, cách triển khai nó bằng C++, và khi nào thì thuật toán này tỏa sáng.

Ý Tưởng Cốt Lõi Của Sắp Xếp Chèn

Hãy tưởng tượng bạn có một tập hợp các phần tử (ví dụ, các số nguyên) mà bạn muốn sắp xếp theo thứ tự tăng dần. Sắp xếp chèn hoạt động bằng cách xây dựng mảng/vector đã sắp xếp từng bước một. Nó chia mảng thành hai phần: một phần đã được sắp xếp và một phần chưa được sắp xếp.

Ban đầu, phần đã sắp xếp chỉ bao gồm phần tử đầu tiên của mảng (vì một phần tử luôn được coi là đã sắp xếp). Phần còn lại là chưa sắp xếp.

Thuật toán lặp qua từng phần tử trong phần chưa sắp xếp, lấy phần tử đó ra và chèn nó vào đúng vị trí của nó trong phần đã sắp xếp sao cho phần đã sắp xếp vẫn giữ nguyên thứ tự. Quá trình này giống như việc bạn lần lượt rút một quân bài mới từ xấp bài chưa chia và đặt nó vào đúng vị trí trong bộ bài mà bạn đang cầm trên tay đã được sắp xếp.

Quá Trình Hoạt Động Từng Bước

Để hiểu rõ hơn, hãy đi qua một ví dụ cụ thể. Giả sử chúng ta có mảng [12, 11, 13, 5, 6]. Chúng ta muốn sắp xếp nó theo thứ tự tăng dần.

Bước 1: Phần tử đầu tiên (12) được coi là đã sắp xếp. Mảng hiện tại (conceptually): [12 | 11, 13, 5, 6] (phần bên trái dấu | là đã sắp xếp).
Bước 2: Lấy phần tử đầu tiên của phần chưa sắp xếp: 11. So sánh 11 với các phần tử trong phần đã sắp xếp (12). Vì 11 < 12, chúng ta dịch chuyển 12 sang phải để tạo chỗ trống. Mảng tạm thời: [ _ , 12 | 13, 5, 6]. Chèn 11 vào chỗ trống. Mảng sau bước 2: [11, 12 | 13, 5, 6]. Phần đã sắp xếp giờ là [11, 12].
Bước 3: Lấy phần tử đầu tiên của phần chưa sắp xếp: 13. So sánh 13 với các phần tử trong phần đã sắp xếp (12, 11). 13 > 12 và 13 > 11. Vậy 13 đã ở đúng vị trí sau 12. Không cần dịch chuyển. Mảng sau bước 3: [11, 12, 13 | 5, 6]. Phần đã sắp xếp là [11, 12, 13].
Bước 4: Lấy phần tử đầu tiên của phần chưa sắp xếp: 5. So sánh 5 với các phần tử trong phần đã sắp xếp (13, 12, 11).
- 5 < 13, dịch chuyển 13 sang phải. Tạm: [11, 12, _ , 13 | 6].
- 5 < 12, dịch chuyển 12 sang phải. Tạm: [11, _ , 12, 13 | 6].
- 5 < 11, dịch chuyển 11 sang phải. Tạm: [ _ , 11, 12, 13 | 6].
- Đã đến đầu mảng hoặc gặp phần tử nhỏ hơn (ở đây là đã đến đầu). Chèn 5 vào chỗ trống. Mảng sau bước 4: [5, 11, 12, 13 | 6]. Phần đã sắp xếp là [5, 11, 12, 13].
Bước 5: Lấy phần tử đầu tiên của phần chưa sắp xếp: 6. So sánh 6 với các phần tử trong phần đã sắp xếp (13, 12, 11, 5).
- 6 < 13, dịch chuyển 13. Tạm: [5, 11, 12, _ , 13 | ].
- 6 < 12, dịch chuyển 12. Tạm: [5, 11, _ , 12, 13 | ].
- 6 < 11, dịch chuyển 11. Tạm: [5, _ , 11, 12, 13 | ].
- 6 > 5. Dừng lại. Chèn 6 vào vị trí sau 5. Mảng sau bước 5: [5, 6, 11, 12, 13 | ].

Toàn bộ mảng đã được sắp xếp: [5, 6, 11, 12, 13].

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

Bây giờ, hãy cùng xem cách chúng ta có thể viết mã C++ để thực hiện thuật toán sắp xếp chèn. Chúng ta sẽ sử dụng vector để biểu diễn mảng.

#include <iostream> // Cần cho cin/cout
#include <vector>   // Cần cho sử dụng vector
#include <iterator> // Cần cho ostream_iterator

// Hàm thực hiện thuật toán sắp xếp chèn cho vector<int>
void insertionSort(vector<int>& arr) {
    int n = arr.size(); // Lấy kích thước của vector

    // Vòng lặp ngoài: Duyệt qua các phần tử từ index 1 đến hết mảng
    // Mỗi lần lặp, phần tử arr[i] sẽ được chèn vào phần đã sắp xếp arr[0..i-1]
    for (int i = 1; i < n; ++i) {
        // key là phần tử hiện tại cần chèn
        int key = arr[i];

        // j là index của phần tử cuối cùng trong mảng đã sắp xếp tạm thời
        // Ban đầu là phần tử ngay trước arr[i]
        int j = i - 1;

        // Vòng lặp trong: So sánh key với các phần tử trong mảng đã sắp xếp (từ phải sang trái)
        // Nếu phần tử arr[j] lớn hơn key, dịch chuyển nó sang phải (arr[j+1])
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // Dịch chuyển phần tử arr[j] sang phải
            j = j - 1;           // Di chuyển con trỏ j sang trái để so sánh tiếp với phần tử trước đó
        }

        // Sau khi vòng lặp while kết thúc, j+1 là vị trí đúng để chèn key
        // Vì vòng lặp dừng lại khi j < 0 hoặc arr[j] <= key
        // Nếu arr[j] <= key, key sẽ được chèn ngay sau arr[j], tức là tại j+1
        // Nếu j < 0, key là phần tử nhỏ nhất và sẽ được chèn vào vị trí 0 (j+1)
        arr[j + 1] = key; // Chèn key vào vị trí đã tìm được
    }
}

Giải Thích Mã Nguồn Chi Tiết:

#include <iostream>, <vector>, <iterator>: Các dòng này bao gồm các thư viện chuẩn của C++ cần thiết. iostream để sử dụng cout (để in ra màn hình), vector để làm việc với vector, và iterator để sử dụng ostream_iterator giúp in vector một cách tiện lợi.
void insertionSort(vector<int>& arr): Đây là khai báo hàm thực hiện thuật toán. Hàm nhận vào một tham chiếu (&) đến vector<int>. Việc sử dụng tham chiếu rất quan trọng vì nó cho phép hàm insertionSort trực tiếp thay đổi (sắp xếp) vector gốc truyền vào, thay vì chỉ làm việc trên một bản sao.
int n = arr.size();: Lấy kích thước (số lượng phần tử) của vector và lưu vào biến n.
for (int i = 1; i < n; ++i): Đây là vòng lặp ngoài chính của thuật toán.
- Nó bắt đầu từ i = 1 vì phần tử tại index 0 (arr[0]) được coi là phần tử đầu tiên của mảng đã sắp xếp ban đầu.
- Biến i duyệt qua từng phần tử trong phần chưa sắp xếp của vector. Mỗi lần lặp, arr[i] là phần tử hiện tại mà chúng ta muốn chèn vào đúng vị trí trong phần đã sắp xếp (từ index 0 đến i-1).
- Vòng lặp tiếp tục cho đến khi i đạt đến n, tức là tất cả các phần tử đã được xem xét và chèn vào phần đã sắp xếp.
int key = arr[i];: Giá trị của phần tử hiện tại (arr[i]) được lưu vào biến key. Chúng ta lưu nó vào một biến riêng bởi vì vị trí arr[i] có thể bị ghi đè bởi các phần tử khác trong quá trình dịch chuyển bên trong vòng lặp while.
int j = i - 1;: Khởi tạo biến j. j ban đầu trỏ đến index của phần tử cuối cùng trong phần đã sắp xếp tạm thời (ngay trước arr[i]). Vòng lặp while sẽ sử dụng j để duyệt ngược từ đây về đầu mảng (index 0) để tìm vị trí chèn phù hợp cho key.
while (j >= 0 && arr[j] > key): Đây là vòng lặp trong. Nó thực hiện việc tìm vị trí và dịch chuyển các phần tử.
- j >= 0: Điều kiện này đảm bảo rằng chúng ta vẫn đang ở trong phạm vi index hợp lệ của mảng (không đi lùi quá index 0).
- arr[j] > key: Điều kiện này kiểm tra xem phần tử tại vị trí j trong mảng đã sắp xếp có lớn hơn giá trị key hay không.
- Nếu cả hai điều kiện trên đều đúng (tức là chúng ta chưa ra khỏi đầu mảng và phần tử arr[j] lớn hơn key), điều đó có nghĩa là key phải được chèn vào trước arr[j]. Để làm được điều này, chúng ta cần dịch chuyển arr[j] sang phải một vị trí để tạo chỗ trống.
- arr[j + 1] = arr[j];: Dòng này thực hiện việc dịch chuyển. Giá trị của arr[j] được gán cho vị trí ngay sau nó (arr[j+1]).
- j = j - 1;: Sau khi dịch chuyển, chúng ta giảm giá trị của j để di chuyển con trỏ sang trái, tiếp tục so sánh key với phần tử tiếp theo trong mảng đã sắp xếp (lùi về phía đầu mảng).
arr[j + 1] = key;: Vòng lặp while kết thúc khi một trong hai điều kiện sai: hoặc j trở thành -1 (có nghĩa là key nhỏ hơn tất cả các phần tử trong mảng đã sắp xếp và nên được đặt ở vị trí đầu tiên), hoặc chúng ta tìm thấy một phần tử arr[j] mà arr[j] <= key (có nghĩa là key nên được đặt ngay sau arr[j]). Trong cả hai trường hợp, vị trí đúng để chèn key chính là j + 1. Dòng này đặt giá trị của key vào vị trí đã tìm được.

Ví Dụ Minh Họa Hoàn Chỉnh

Hãy xem một ví dụ đầy đủ về cách sử dụng hàm insertionSort trong chương trình C++:

#include <iostream>
#include <vector>
#include <iterator> // Cần cho ostream_iterator
#include <algorithm> // Cần cho copy

// Hàm thực hiện thuật toán sắp xếp chèn (như đã giải thích ở trên)
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// Hàm trợ giúp để in vector ra màn hình
void printVector(const vector<int>& arr) {
    // Sử dụng copy và ostream_iterator để in các phần tử
    // cách nhau bằng dấu cách.
    copy(arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main() {
    // Khai báo và khởi tạo một vector số nguyên
    vector<int> myVector = {12, 11, 13, 5, 6};

    cout << "Mang goc truoc khi sap xep: ";
    // In vector gốc ra màn hình
    printVector(myVector);

    // Gọi hàm sap xep chen để sắp xếp vector
    insertionSort(myVector);

    cout << "Mang sau khi sap xep chen: ";
    // In vector đã sắp xếp ra màn hình
    printVector(myVector);

    // Thử với một vector khác
    vector<int> anotherVector = {5, 4, 3, 2, 1, 0};
    cout << "\nMang khac truoc khi sap xep: ";
    printVector(anotherVector);
    insertionSort(anotherVector);
    cout << "Mang khac sau khi sap xep chen: ";
    printVector(anotherVector);

    // Thử với vector đã sắp xếp sẵn
    vector<int> sortedVector = {1, 2, 3, 4, 5};
    cout << "\nMang da sap xep san truoc khi sap xep: ";
    printVector(sortedVector);
    insertionSort(sortedVector); // Algorithm should be fast here (O(n))
    cout << "Mang da sap xep san sau khi sap xep: ";
    printVector(sortedVector);


    return 0; // Trả về 0 báo hiệu chương trình kết thúc thành công
}

Giải Thích Ví Dụ:

Hàm main tạo một vector<int> có tên myVector với các giá trị ban đầu.
Hàm printVector được sử dụng để in nội dung của vector ra màn hình một cách gọn gàng. Nó sử dụng copy kết hợp với ostream_iterator. ostream_iterator<int>(cout, " ") tạo ra một iterator mà khi gán giá trị vào nó, giá trị đó sẽ được in ra cout theo sau là một dấu cách. copy sao chép các phần tử từ arr.begin() đến arr.end() (toàn bộ vector) đến iterator này, hiệu quả là in chúng ra màn hình.
Trước khi gọi insertionSort, chúng ta in vector gốc.
Sau đó, chúng ta gọi insertionSort(myVector);. Hàm này sẽ sắp xếp trực tiếp vector myVector.
Cuối cùng, chúng ta in lại vector để thấy kết quả đã được sắp xếp.
Ví dụ cũng bao gồm việc sắp xếp một vector sắp xếp ngược và một vector đã sắp xếp sẵn để minh họa cách thuật toán hoạt động với các kiểu dữ liệu đầu vào khác nhau.

Khi chạy chương trình này, output sẽ là:

Mang goc truoc khi sap xep: 12 11 13 5 6 
Mang sau khi sap xep chen: 5 6 11 12 13 

Mang khac truoc khi sap xep: 5 4 3 2 1 0 
Mang khac sau khi sap xep chen: 0 1 2 3 4 5 

Mang da sap xep san truoc khi sap xep: 1 2 3 4 5 
Mang da sap xep san sau khi sap xep: 1 2 3 4 5

Kết quả cho thấy vector đã được sắp xếp đúng như mong đợi.

Đánh Giá Hiệu Năng (Độ Phức Tạp)

Hiểu về hiệu năng của thuật toán là rất quan trọng để biết khi nào nên sử dụng nó.

Độ phức tạp thời gian (Time Complexity):
- Trường hợp tốt nhất (Best Case): Xảy ra khi mảng đầu vào đã được sắp xếp sẵn. Trong trường hợp này, vòng lặp while (j >= 0 && arr[j] > key) sẽ luôn dừng ngay sau lần kiểm tra đầu tiên (vì arr[j] > key sẽ sai khi j=i-1 và arr[i-1] <= arr[i]). Mỗi phần tử chỉ cần một số lượng thao tác cố định. Do đó, độ phức tạp thời gian là tuyến tính, O(n), trong đó n là số lượng phần tử.
- Trường hợp xấu nhất (Worst Case): Xảy ra khi mảng đầu vào được sắp xếp theo thứ tự ngược lại (ví dụ: giảm dần khi cần sắp xếp tăng dần). Mỗi phần tử arr[i] sẽ phải so sánh với tất cả i phần tử trong phần đã sắp xếp (từ i-1 về 0) và dịch chuyển chúng. Tổng số phép so sánh và dịch chuyển sẽ tỷ lệ với tổng của dãy số từ 1 đến n-1, tức là (n-1)n/2. Độ phức tạp thời gian là bậc hai, O(n^2).
- Trường hợp trung bình (Average Case): Đối với một mảng ngẫu nhiên, độ phức tạp thời gian trung bình cũng là O(n^2).
Độ phức tạp không gian (Space Complexity):
- Sắp xếp chèn là một thuật toán tại chỗ (in-place). Điều này có nghĩa là nó thực hiện sắp xếp mà không cần thêm bộ nhớ đáng kể. Nó chỉ cần một vài biến phụ (như i, j, key) để lưu trữ tạm thời trong quá trình sắp xếp, không phụ thuộc vào kích thước của mảng. Do đó, độ phức tạp không gian là O(1).

Khi Nào Nên Sử Dụng Sắp Xếp Chèn?

Mặc dù có độ phức tạp O(n^2) trong trường hợp trung bình và xấu nhất, Sắp xếp Chèn vẫn có những ưu điểm khiến nó phù hợp cho một số tình huống cụ thể:

Dữ liệu nhỏ: Với số lượng phần tử n nhỏ (thường dưới vài chục hoặc khoảng 100), hiệu suất O(n^2) là chấp nhận được và thậm chí có thể nhanh hơn các thuật toán phức tạp hơn do chi phí phụ (overhead) thấp hơn.
Dữ liệu gần như đã sắp xếp: Đây là điểm mạnh lớn nhất của Sắp xếp Chèn. Nếu mảng chỉ có một vài phần tử ở sai vị trí (gọi là độ bất thường thấp), thuật toán sẽ chạy rất nhanh, gần với trường hợp tốt nhất O(n).
Đơn giản và dễ triển khai: Đây là một trong những thuật toán sắp xếp dễ hiểu và viết code nhất, làm cho nó trở thành một lựa chọn tốt cho mục đích học tập hoặc khi cần một giải pháp sắp xếp nhanh chóng cho các bài toán nhỏ.
Tại chỗ (In-place): Nếu bộ nhớ là một hạn chế, Sắp xếp Chèn là một lựa chọn tốt vì nó chỉ cần không gian bổ sung O(1).
Ổn định (Stable): Sắp xếp chèn là một thuật toán ổn định. Điều này có nghĩa là nếu có hai phần tử có giá trị bằng nhau, thứ tự tương đối của chúng trong mảng gốc sẽ được giữ nguyên trong mảng đã sắp xếp. Điều này quan trọng trong một số ứng dụng đặc biệt.

Ngược lại, với các tập dữ liệu lớn và không có tính chất gần sắp xếp, bạn nên cân nhắc các thuật toán hiệu quả hơn về mặt thời gian như Quick Sort hoặc Merge Sort (thường có độ phức tạp O(n log n)).

Bài tập ví dụ: C++ Bài 9.B2: Sắp xếp 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ự 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ự giảm.

Ví dụ 1:

Input

6
5 1 3 2 4 8

Ouput

8 5 4 3 2 1

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

Dãy số sau khi sắp xếp theo thứ tự giảm là [8, 5, 4, 3, 2, 1].

<br>

Đọc dữ liệu vào:
- Đầu tiên, bạn cần đọc số lượng phần tử N.
- Tiếp theo, bạn cần đọc N số nguyên. Để lưu trữ N số này một cách hiệu quả và dễ sử dụng với các hàm thư viện, bạn nên sử dụng một container từ thư viện chuẩn C++. vector<int> là lựa chọn phổ biến và rất phù hợp cho trường hợp này. Bạn có thể khởi tạo vector với kích thước N và sau đó đọc các số vào từng phần tử của vector.
Sắp xếp:
- Thư viện <algorithm> của C++ cung cấp hàm sort rất mạnh mẽ và hiệu quả (thường là O(N log N)).
- sort nhận vào hai iterator chỉ định phạm vi cần sắp xếp (ví dụ: vec.begin(), vec.end() cho toàn bộ vector). Mặc định, sort sắp xếp theo thứ tự tăng dần.
- Để sắp xếp theo thứ tự giảm dần, bạn cần cung cấp một đối số thứ ba cho sort, đó là một hàm so sánh (hoặc function object/lambda) định nghĩa tiêu chí sắp xếp. Hàm so sánh này comp(a, b) sẽ trả về true nếu a được coi là "nhỏ hơn" b theo tiêu chí sắp xếp của bạn (tức là a nên đứng trước b).
- Với sắp xếp giảm dần, a nên đứng trước b nếu a > b. Do đó, hàm so sánh của bạn cần trả về a > b.
- Cách đơn giản nhất để cung cấp tiêu chí sắp xếp giảm dần là sử dụng function object greater<int>() có sẵn trong thư viện <functional>. Bạn chỉ cần truyền greater<int>() làm đối số thứ ba cho sort.
In kết quả:
- Sau khi vector đã được sắp xếp giảm dần, bạn cần duyệt qua các phần tử của nó từ đầu đến cuối.
- In mỗi phần tử ra màn hình, cách nhau bởi một dấu cách.
- Sau khi in xong tất cả các phần tử, in một ký tự xuống dòng để kết thúc output.

Tóm lại các bước chính:

Include các header cần thiết (iostream, vector, algorithm, có thể thêm functional nếu dùng greater).
Đọc N.
Tạo vector<int> có kích thước N.
Đọc N số vào vector.
Gọi sort cho phạm vi của vector với greater<int>() làm hàm so sánh.
Duyệt vector đã sắp xếp và in các phần tử ra màn hình, cách nhau bởi dấu cách.
In ký tự xuống dòng cuối cùng.

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

Comments

There are no comments at the moment.