Thuật toán sắp xếp chèn (Insertion Sort)

1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.

2. Ý tưởng
- Giả sử có sẵn một đoạn X[1],...,X[i] trong dãy đã được sắp xếp không giảm. Trong mọi trường hợp có thể coi dãy có duy nhất 1 phần từ X[1] là đã được sắp xếp.
- Xét phần từ X[i+1], tìm cách chèn nó vào đúng vị trí trong X[1],...,X[i] để được dãy X1,...,X[i+1] đã được sắp xếp.
- Lặp lại bước trên cho đến phần từ X[n].

3. Giải thuật
a. Sắp xếp
- Bước 1: i = 1, dãy X[1] đã được sắp xếp
- Bước 2: i=i+1, chèn X[i] vào dãy X[1], ..., X[i-1]
- Bước 3:
* Nếu i <= n, quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đung vị trí.

b. Chèn X[i] vào dãy X[1],...,X[i-1]
- Bước 1: key=X[i]
- Bước 2: Xét dãy X[1],...,X[i-1] theo chiều từ phải sang trái:
* Nếu các phần từ được xét lớn hơn hoặc bằng key thì dịch sang phải 1 vị trí để chuẩn bị chỗ chèn X[i]
* Nếu gặp phần từ nhỏ hơn key thì chèn X[i] vào vị trí bên phải phần tử đó.

4. Mã thực thi (tựa C)

Code:


void InsertSort (int X[], int n) {
    int k := 2;// Bắt đầu chèn từ phần tử thứ hai đến cuối dãy
    while (k <= n) {
        insert(X, k, X[k]);
        k := k + 1;
    }
 }
void insert (int a[], int k, value) {
      int i := k-1;
    while (i > 0 and a[i] > value) {
        a[i+1] := a[i]; // dịch sang phải một vị trí
        i := i - 1;
    }
    a[i+1] := value; / chèn value vào bên phải
 }



5. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
k=2, insert(X,k,2 ), ta có 2, 7, 5, 4, 1, 3, 8, 6
k=3, insert(X,k,5 ), ta có 2, 5, 7, 4, 1, 3, 8, 6
k=4, insert(X,k,4 ), ta có 2, 4, 5, 7, 1, 3, 8, 6
k=5, insert(X,k,1 ), ta có 1, 2, 4, 5, 7, 3, 8, 6
k=6, insert(X,k,3 ), ta có 1, 2, 3, 4, 5, 7, 8, 6
k=7, insert(X,k,8 ), ta có 1, 2, 3, 4, 5, 7, 8, 6
k=8, insert(X,k,6 ), ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.

Hiệu quả của thuật toán sắp xếp chèn:

Thuật toán sử dụng trung bình n^2/4 phép so sánh và n2/4 lần đổi chỗ, n^2/2 phép so sánh và n^2/2 lần hoán vị trong trường hợp xấu nhất, n-1 phép so sánh và 0 lần hoán vị trong trường hợp tốt nhất.
Thuật toán này chỉ sử dụng tốt khi mảng nhỏ và được sắp xếp một phần.
Đánh giá:
- Tốt hơn thuật toán bubble sort
- Nhưng không tốt hơn thuật toán heap sort