Bài 13.2. Thuật toán Insertion Sort và ứng dụng

Chào mừng quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau khám phá một thuật toán sắp xếp kinh điển khác: Insertion Sort (Sắp xếp Chèn). Nếu bạn đã từng sắp xếp một bộ bài trong tay hoặc sắp xếp các cuốn sách trên kệ theo thứ tự, bạn có thể đã vô thức sử dụng tư duy tương tự như Insertion Sort rồi đấy!

Insertion Sort nổi bật bởi sự đơn giản và trực quan của nó. 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, nó lại tỏa sáng trong những trường hợp cụ thể. Hãy cùng tìm hiểu sâu hơn về cách nó hoạt động nhé!

Ý Tưởng Chính: Sắp Xếp "Tại Chỗ" Bằng Cách Chèn

Hãy tưởng tượng bạn đang sắp xếp một bộ bài. Bạn cầm một lá bài và đặt nó vào vị trí đúng trong tay bạn, nơi các lá bài trước đó đã được sắp xếp. Rồi bạn cầm lá tiếp theo, tìm vị trí đúng của nó trong tất cả các lá bài bạn đã cầm và sắp xếp, và chèn nó vào đó. Bạn cứ tiếp tục như vậy cho đến khi hết bài.

Đó chính là cách Insertion Sort hoạt động! Thuật toán chia mảng thành hai phần:

Phần đã được sắp xếp (ban đầu chỉ chứa phần tử đầu tiên).
Phần chưa được sắp xếp (chứa các phần tử còn lại).

Nó lặp đi lặp lại việc lấy phần tử đầu tiên của phần chưa được sắp xếp, tìm vị trí thích hợp của nó trong phần đã được sắp xếp và chèn nó vào đó. Quá trình này làm cho phần đã được sắp xếp ngày càng lớn hơn cho đến khi toàn bộ mảng được sắp xếp.

Cách Thức Hoạt Động (Từng Bước Một)

Chi tiết hơn, thuật toán Insertion Sort làm như sau:

Coi phần tử đầu tiên của mảng (arr[0]) là phần tử duy nhất trong mảng con đã được sắp xếp.
Lặp qua các phần tử còn lại của mảng, bắt đầu từ phần tử thứ hai (arr[1]) cho đến hết (arr[n-1]). Với mỗi phần tử hiện tại arr[i] (với i chạy từ 1 đến n-1):
- Lấy giá trị của arr[i] và lưu tạm vào một biến, gọi là key. Đây chính là phần tử chúng ta cần chèn vào mảng con đã sắp xếp.
- So sánh key với các phần tử trong mảng con đã sắp xếp (các phần tử từ arr[0] đến arr[i-1]), bắt đầu từ phần tử cuối cùng của mảng con đã sắp xếp (arr[i-1]) trở về trước.
- Nếu một phần tử trong mảng con đã sắp xếp (arr[j], với j chạy từ i-1 trở về 0) lớn hơn key, thì dịch chuyển phần tử đó sang phải một vị trí (arr[j+1] = arr[j]).
- Tiếp tục dịch chuyển các phần tử lớn hơn key sang phải cho đến khi gặp một phần tử nhỏ hơn hoặc bằng key, hoặc đến khi duyệt hết mảng con đã sắp xếp (đến index 0).
- Chèn key vào vị trí sau phần tử cuối cùng đã dịch chuyển (vào vị trí arr[j+1]).

Quá trình này đảm bảo rằng sau khi xử lý phần tử arr[i], mảng con từ arr[0] đến arr[i] luôn được sắp xếp.

Minh Họa Trực Quan Bằng Một Ví Dụ

Hãy xem xét mảng [12, 11, 13, 5, 6] và xem Insertion Sort sắp xếp nó như thế nào.

Mảng ban đầu: [12, 11, 13, 5, 6]

Bước 1 (i = 1):
- Phần đã sắp xếp: [12]
- Phần chưa sắp xếp: [11, 13, 5, 6]
- key = arr[1] = 11.
- So sánh key (11) với phần tử trước nó (12). 12 > 11, nên dịch chuyển 12 sang phải.
- Mảng tạm thời: [_, 12, 13, 5, 6] (dấu _ là vị trí trống để chèn)
- Đến đầu mảng. Chèn key (11) vào vị trí trống.
- Mảng sau bước 1: [11, 12, 13, 5, 6]
Bước 2 (i = 2):
- Phần đã sắp xếp: [11, 12]
- Phần chưa sắp xếp: [13, 5, 6]
- key = arr[2] = 13.
- So sánh key (13) với phần tử trước nó (12). 12 không lớn hơn 13. Dừng lại.
- Chèn key (13) vào vị trí hiện tại của nó (sau 12).
- Mảng sau bước 2: [11, 12, 13, 5, 6]
Bước 3 (i = 3):
- Phần đã sắp xếp: [11, 12, 13]
- Phần chưa sắp xếp: [5, 6]
- key = arr[3] = 5.
- So sánh key (5) với 13. 13 > 5, dịch 13 sang phải. Mảng tạm: [11, 12, _, 13, 6]
- So sánh key (5) với 12. 12 > 5, dịch 12 sang phải. Mảng tạm: [11, _, 12, 13, 6]
- So sánh key (5) với 11. 11 > 5, dịch 11 sang phải. Mảng tạm: [_, 11, 12, 13, 6]
- Đến đầu mảng. Chèn key (5) vào vị trí trống.
- Mảng sau bước 3: [5, 11, 12, 13, 6]
Bước 4 (i = 4):
- Phần đã sắp xếp: [5, 11, 12, 13]
- Phần chưa sắp xếp: [6]
- key = arr[4] = 6.
- So sánh key (6) với 13. 13 > 6, dịch 13 sang phải. Mảng tạm: [5, 11, 12, _, 13]
- So sánh key (6) với 12. 12 > 6, dịch 12 sang phải. Mảng tạm: [5, 11, _, 12, 13]
- So sánh key (6) với 11. 11 > 6, dịch 11 sang phải. Mảng tạm: [5, _, 11, 12, 13]
- So sánh key (6) với 5. 5 không lớn hơn 6. Dừng lại.
- Chèn key (6) vào vị trí sau 5.
- Mảng sau bước 4: [5, 6, 11, 12, 13]

Quá trình hoàn tất, mảng đã được sắp xếp!

C++ Implementation

Bây giờ, hãy cùng hiện thực thuật toán Insertion Sort bằng C++.

#include <iostream> // Bao gồm thư viện để nhập/xuất dữ liệu (như cout)

// Hàm để thực hiện Insertion Sort trên mảng
void insertionSort(int arr[], int n) {
    // Lặp từ phần tử thứ hai (index 1) đến hết mảng
    for (int i = 1; i < n; i++) {
        // Lưu giá trị của phần tử hiện tại vào biến key
        int key = arr[i];
        // Bắt đầu từ phần tử cuối cùng của mảng con đã sắp xếp (trước phần tử key)
        int j = i - 1;

        // Di chuyển các phần tử của mảng con đã sắp xếp (arr[0..i-1])
        // lớn hơn key sang phải một vị trí so với vị trí hiện tại của chúng
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // Dịch phần tử sang phải
            j = j - 1;           // Giảm j để xét phần tử tiếp theo về phía đầu mảng
        }
        // Chèn key vào vị trí đúng của nó (sau phần tử cuối cùng đã dịch chuyển)
        arr[j + 1] = key;
    }
}

// Hàm tiện ích để in mảng
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// Hàm main để kiểm thử
int main() {
    int arr[] = {12, 11, 13, 5, 6}; // Mảng ví dụ
    int n = sizeof(arr) / sizeof(arr[0]); // Tính kích thước mảng

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

    insertionSort(arr, n); // Gọi hàm sắp xếp

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

    // Thêm một ví dụ khác
    int arr2[] = {5, 4, 3, 2, 1};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    std::cout << "\nMang truoc khi sap xep (vi du 2): ";
    printArray(arr2, n2);

    insertionSort(arr2, n2);

    std::cout << "Mang sau khi sap xep (vi du 2): ";
    printArray(arr2, n2);

    // Ví dụ với mảng đã sắp xếp
    int arr3[] = {1, 2, 3, 4, 5};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);

    std::cout << "\nMang truoc khi sap xep (vi du da sap xep): ";
    printArray(arr3, n3);

    insertionSort(arr3, n3);

    std::cout << "Mang sau khi sap xep (vi du da sap xep): ";
    printArray(arr3, n3);


    return 0; // Kết thúc chương trình thành công
}

Giải Thích Code C++

Hãy cùng phân tích từng phần của đoạn mã trên:

#include <iostream>: Dòng này bao gồm thư viện iostream, cần thiết để sử dụng các hàm nhập/xuất như std::cout (để in ra màn hình).
void insertionSort(int arr[], int n): Đây là hàm chính thực hiện thuật toán. Nó nhận vào một mảng số nguyên arr và kích thước của mảng n.
for (int i = 1; i < n; i++): Đây là vòng lặp ngoài. Nó bắt đầu từ i = 1 bởi vì phần tử arr[0] (phần tử đầu tiên) được coi là đã nằm trong mảng con đã sắp xếp ban đầu. Vòng lặp này đi qua từng phần tử trong phần chưa được sắp xếp, lấy mỗi phần tử làm key để chèn.
int key = arr[i];: Gán giá trị của phần tử hiện tại (arr[i]) vào biến key. Chúng ta cần biến key để giữ giá trị này, 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.
int j = i - 1;: Biến j được khởi tạo là chỉ mục của phần tử cuối cùng trong mảng con đã sắp xếp (ngay trước key). Vòng lặp bên trong sẽ dùng j để duyệt ngược từ đây về đầu mảng.
while (j >= 0 && arr[j] > key): Đây là vòng lặp trong.
- j >= 0: Đảm bảo chúng ta không duyệt ra ngoài giới hạn mảng (về phía đầu mảng).
- arr[j] > key: Đây là điều kiện chính. Nếu phần tử hiện tại trong mảng con đã sắp xếp (arr[j]) lớn hơn key, chúng ta cần dịch chuyển nó để nhường chỗ cho key.
arr[j + 1] = arr[j];: Nếu điều kiện while đúng, dòng này dịch chuyển phần tử arr[j] sang vị trí bên phải của nó (arr[j+1]).
j = j - 1;: Giảm j để tiếp tục so sánh key với phần tử tiếp theo về phía đầu mảng con đã sắp xếp.
arr[j + 1] = key;: Khi vòng lặp while kết thúc (hoặc là j < 0 hoặc arr[j] <= key), chúng ta đã tìm được vị trí đúng để chèn key. Vị trí này là j + 1, ngay sau phần tử cuối cùng mà key không lớn hơn (hoặc ở vị trí 0 nếu key là nhỏ nhất trong mảng con đã sắp xếp).
void printArray(...) và main(): Đây là các hàm phụ trợ. printArray giúp hiển thị nội dung mảng. main tạo mảng ví dụ, gọi insertionSort và in kết quả để bạn có thể thấy thuật toán hoạt động. Các ví dụ khác trong main cho thấy Insertion Sort trên mảng đảo ngược và mảng đã sắp xếp.

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

Hiệu suất của Insertion Sort phụ thuộc vào trạng thái ban đầu của mảng.

Độ phức tạp thời gian (Time Complexity):
- Trường hợp Tốt nhất (Best Case): Khi mảng đã gần như sắp xếp hoặc đã sắp xếp hoàn toàn. Vòng lặp while bên trong chỉ chạy 1 lần duy nhất cho mỗi lần lặp của vòng lặp for bên ngoài (vì điều kiện arr[j] > key sẽ sai ngay lập tức). Tổng số phép so sánh là khoảng n-1. Độ phức tạp thời gian là O(n).
- Trường hợp Xấu nhất (Worst Case): Khi mảng được sắp xếp theo thứ tự ngược lại (giảm dần cho sắp xếp tăng dần). Với mỗi phần tử arr[i], vòng lặp while phải duyệt và dịch chuyển toàn bộ i phần tử trước nó. Tổng số phép so sánh/dịch chuyển là khoảng 1 + 2 + ... + (n-1) = n*(n-1)/2. Độ phức tạp thời gian là O(n^2).
- Trường hợp Trung bình (Average Case): Khi các phần tử ở vị trí ngẫu nhiên. Trung bình, chúng ta sẽ phải dịch chuyển khoảng i/2 phần tử cho mỗi arr[i]. Tổng số phép so sánh/dịch chuyển cũng xấp xỉ n^2/4. Độ phức tạp thời gian là O(n^2).
Độ phức tạp không gian (Space Complexity): Insertion Sort là một thuật toán sắp xếp tại chỗ (in-place). Nó chỉ yêu cầu một lượng không gian bộ nhớ bổ sung cố định (cho biến key, i, j). Độ phức tạp không gian là O(1).

Nhìn chung, Insertion Sort có độ phức tạp thời gian là O(n^2) ở trường hợp trung bình và xấu nhất, điều này làm cho nó không hiệu quả cho các tập dữ liệu lớn so với các thuật toán O(n log n) như Merge Sort hay Quick Sort. Tuy nhiên, nó lại rất hiệu quả ở trường hợp tốt nhất (O(n)).

Ứng Dụng Của Insertion Sort

Mặc dù có độ phức tạp O(n^2), Insertion Sort vẫn có những ứng dụng thực tế:

Sắp xếp các tập dữ liệu nhỏ: Với các mảng có kích thước nhỏ (khoảng dưới 50 phần tử), chi phí hằng số (constant factor) thấp của Insertion Sort có thể làm cho nó nhanh hơn các thuật toán O(n log n) phức tạp hơn do chi phí khởi tạo và quản lý đệ quy/phân chia.
Sắp xếp các tập dữ liệu gần như đã sắp xếp: Đây là trường hợp tốt nhất của Insertion Sort. Nếu mảng chỉ có một vài phần tử lệch khỏi vị trí đúng, thuật toán sẽ chạy rất nhanh (gần O(n)). Điều này hữu ích khi bạn biết dữ liệu đầu vào có tính chất này.
Sắp xếp trực tuyến (Online Sorting): Insertion Sort có thể sắp xếp một luồng dữ liệu khi nó đến, từng phần tử một. Tại bất kỳ thời điểm nào, mảng con các phần tử đã xử lý luôn được sắp xếp.
Là một phần của các thuật toán lai (Hybrid Algorithms): Một số thuật toán sắp xếp nâng cao như Timsort (được dùng trong Python và Java) và Introsort sử dụng Insertion Sort làm thuật toán sắp xếp cho các mảng con nhỏ hoặc các mảng con đã gần sắp xếp, nhằm tận dụng hiệu quả O(n) của nó trong các trường hợp này.

Ưu Điểm và Nhược Điểm

Ưu điểm:

Đơn giản và dễ hiện thực: Cực kỳ dễ hiểu và viết mã.
Hiệu quả cho tập dữ liệu nhỏ: Tốt hơn các thuật toán O(n log n) cho n nhỏ.
Hiệu quả cho dữ liệu gần sắp xếp: Chạy gần như tuyến tính (O(n)).
Sắp xếp tại chỗ (In-place): Chỉ cần không gian bộ nhớ O(1).
Ổn định (Stable): Duy trì thứ tự tương đối của các phần tử có giá trị bằng nhau. Điều này quan trọng trong một số ứng dụng cụ thể.

Nhược điểm:

Kém hiệu quả cho tập dữ liệu lớn: Độ phức tạp O(n^2) khiến nó chậm đi đáng kể khi kích thước mảng tăng lên.

Bài tập ví dụ:

Dễ Dàng

Trong một buổi họp nhóm, quản lý của FullHouse Dev đã đưa ra một bài toán đơn giản để kiểm tra kỹ năng xử lý mảng của các lập trình viên. Mặc dù đây là một bài toán cơ bản, nhưng nó sẽ giúp đội ngũ rèn luyện tư duy logic và kỹ năng lập trình.

Bài toán

FullHouse Dev được cung cấp một mảng có kích thước \(N\) và một số nguyên \(M\). Nhiệm vụ của họ là tính toán sự chênh lệch giữa tổng lớn nhất và tổng nhỏ nhất của \(N-M\) phần tử trong mảng đã cho.

INPUT FORMAT:

Dòng đầu tiên chứa một số nguyên \(T\) biểu thị số lượng test case.
Dòng đầu tiên của mỗi test case chứa hai số nguyên \(N\) và \(M\).
Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu thị các phần tử của mảng.

OUTPUT FORMAT:

Với mỗi test case, in ra kết quả trên một dòng mới.

Ràng buộc:

\(1 \leq T \leq 10\)
\(1 \leq N \leq 1000\)
\(1 \leq a[i] \leq 1000\)

Ví dụ

INPUT

1
5 1
1 2 3 4 5

OUTPUT

Giải thích

Trong ví dụ này, \(M\) là 1 và \(N\) là 5, nên FullHouse Dev cần tính toán tổng lớn nhất và nhỏ nhất sử dụng \(5-1 = 4\) phần tử.

Tổng lớn nhất sử dụng 4 phần tử sẽ là \(2+3+4+5 = 14\).
Tổng nhỏ nhất sử dụng 4 phần tử sẽ là \(1+2+3+4 = 10\).
Chênh lệch sẽ là \(14 - 10 = 4\).

Thông qua bài toán này, quản lý muốn đánh giá khả năng xử lý mảng và tính toán của các thành viên FullHouse Dev, đồng thời giúp họ rèn luyện kỹ năng giải quyết vấn đề một cách hiệu quả. Tuyệt vời, đây là hướng dẫn ngắn gọn để giải bài toán "Dễ Dàng" bằng C++ mà không cung cấp code hoàn chỉnh:

Đọc Input: Đọc số lượng test case T. Sau đó, lặp lại T lần:
- Đọc hai số nguyên N và M.
- Đọc N số nguyên tiếp theo vào một mảng (ví dụ: dùng std::vector).
Sắp xếp: Sắp xếp mảng vừa đọc theo thứ tự tăng dần. Việc này giúp dễ dàng xác định các phần tử nhỏ nhất và lớn nhất.
Tính Tổng Nhỏ Nhất: Để có tổng nhỏ nhất của N-M phần tử, ta cần chọn N-M phần tử nhỏ nhất. Sau khi sắp xếp, đây chính là N-M phần tử đầu tiên của mảng. Tính tổng của các phần tử từ chỉ số 0 đến N-M-1. Sử dụng kiểu dữ liệu long long cho tổng để tránh tràn số.
Tính Tổng Lớn Nhất: Để có tổng lớn nhất của N-M phần tử, ta cần chọn N-M phần tử lớn nhất. Sau khi sắp xếp, đây chính là N-M phần tử cuối cùng của mảng. Tính tổng của các phần tử từ chỉ số M đến N-1. Sử dụng kiểu dữ liệu long long.
Tính Hiệu và In Kết Quả: Hiệu cần tìm chính là (Tổng lớn nhất) - (Tổng nhỏ nhất). In kết quả này cho mỗi test case trên một dòng mới.

Tóm lại:

Đọc N, M và mảng.
Sắp xếp mảng tăng dần.
Tổng nhỏ nhất = tổng các phần tử đầu tiên (từ index 0 đến N-M-1).
Tổng lớn nhất = tổng các phần tử cuối cùng (từ index M đến N-1).
Kết quả = Tổng lớn nhất - Tổng nhỏ nhất.

Lưu ý: Có thể tính hiệu một cách hiệu quả hơn bằng cách nhận ra rằng hiệu giữa tổng N-M phần tử cuối cùng và tổng N-M phần tử đầu tiên sau khi sắp xếp chính là hiệu giữa tổng M phần tử cuối cùng và tổng M phần tử đầu tiên. Tức là: (a[N-M] + ... + a[N-1]) - (a[0] + ... + a[M-1]). Bạn có thể tính tổng M phần tử đầu và M phần tử cuối rồi trừ đi.

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

Comments

There are no comments at the moment.