Insertion Sort (Sắp Xếp Chèn)

Insertion là một trong những thuật toán sắp xếp đơn giản và dễ hiểu nhất, ý tưởng tính của nó giống như cách ta sắp xếp bài tây, mỗi lần lấy một phần tử và chèn nó vào đúng vị trí trong dãy đã được sắp xếp trước đó.

Nguyên lý hoạt động

- Bắt đầu tử phần tử thứ hai trong mảng (vì phần tử đầu tiên coi như đã được sắp xếp).

- Lấy phần tử hiện tại (gọi là key) và so sánh với các phần tử đứng trước nó.

- Dịch chuyển các phần tử lớn hơn key sang bên phải.

- Chèn key vào đúng vị trí.

- Lặp lại cho đến hết mảng.

Code Python

def insertion_sort(arr):
	for i in ranger(1, len(arr)):
    	key = arr[i]
        j = i - 1
        # Dịch chuyển phần tử lớn hơn sang phải
        While j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j-=1
        # Chèn key vào vị trí đúng
        arr[j+1] = key
   	return arr

Giải thích

- Vòng lặp ngoài key là phần tử hiện tại cần chèn vào đúng vị trí (key=arr[i]), j là phần tử đứng ngay trước key (j = i-1).

- Vòng lặp trong:
+ So sánh key với các phần tử trước nó.
+ Nếu phần tử trước nó (arr[j]) lớn hơn key, thì dịch nó sang phải (arr[j+1] = arr[j]).
+ Giảm j để tiếp tục so sánh với phần tử trước nửa.
+ Vòng lặp dừng khi gặp phần tử nhỏ hơn hoặc bằng key, hoặc đã duyệt hết mảng.

- sau khi dịch chuyển xong, vị trí trống chính là j+1, chèn key vào đúng vị trí trống đó.

- trả về mảng đã sắp xếp return arr.

Code C++

#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
    // Duyệt từ phần tử thứ hai đến cuối mảng
    for (int i = 1; i < n; i++){
    	int key = arr[i];	// Phần tử cần chèn
        int j = i - 1;
        
        // Dịch chuyển các phần tử lớn hơn key sang phải
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr [j];
            j--;
        }
        
        // Chèn key vào vị trí đúng
        arr[j+1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    insertionSort(arr, n);
    
    cout << "Mảng sau khi sắp xếp: ";
    for (int i = 0; i < n; i++)
    	cout << arr[i] << " ";
    cout << endl;
    
    return 0;
}

Ưu và nhược điểm

- Ưu điểm:
+ Đơn giản, dễ hiểu: Cấu trúc ngắn gọn, dễ cài đặt.
+ Ổn định: Giữ nguyên thứ tự của các phần tử bằng nhau.
+ Tại chổ (in-place): Không cần thêm bộ nhớ phụ ngoài mảng ban đầu.
+ Hiệu quả với mảng nhỏ hoặc gần như đã sắp xếp: Trong trường hợp tốt nhất, độ phức tạp chỉ là O(n).

- Nhược điểm:
+ Hiệu suất kém với dữ liệu lớn: Trường hợp trung bình và xấu nhất có độ phức tạp o(n2).
+ Không thích hợp cho mảng có kích thước lớn: Vì số lần so sánh và dịch chuyển tăng nhanh theo số phần tử.
+ Chỉ phù hợp cho dữ liệu trong bộ nhớ: Không tối ưu cho xử lý dữ liệu ngoài (external sorting).

Ứng dụng

- Sắp xếp mảng nhỏ: Thường dùng cho mảng có kích thước nhỏ (ví dụ < 20 phần tử).

- Dữ liệu gần như đã sắp xếp: Khi mảng chỉ có vài phần tử sai vị trí, Insertion Sort rất nhanh.

- Kết hợp với thuật toán khác: Một số thuật toán nâng cao (như Quick Sort hoặc Merge Sort) có thể chuyển sang Insertion Sort khi xử lý các đoạn mảng nhỏ để tăng hiệu quả.

- Học thuật: Thường dùng để giảng dạy vì dễ minh họa nguyên lý sắp xếp.