Cấu trúc dữ liệu và giải thuật: Giải thuật sắp xếp chèn (Insert sort)

Quoc_Khanh_Tran · June 15, 2022, 12:25pm

Giải thuật sắp xếp chèn (Insert sort)

1. Nhận xét ban đầu

Trong 1 dãy bất kì, ta luôn thấy 1 đoạn con của dãy đã có trật tự (tăng hoặc giảm).
Nếu dãy hoặc 1 đoạn con của dãy chỉ có 1 phần tử duy nhất thì xem như đã có trật tự.

2. Ý tưởng thuật toán

Ban đầu coi như phần tử đầu tiên đã sắp xếp.
So sánh phần tử thứ 2 với phần tử đầu tiên để đổi chỗ nếu cần để sao cho 2 phần tử này được sắp xếp theo thứ tự chỉ định.
Tìm vị trí để chèn phần tử thứ 3 của dãy hiện hành vào dãy 2 phần tử đầu đã được sắp xếp ở trên sao cho dãy vẫn được sắp xếp đúng thứ tự.
Lặp lại liên tục các quá trình trên cho tới khi hết dãy.

3. Cơ chế hoạt động (sơ đồ dò vết)

Cho dãy số: | 5 | 2 | 3 | 1 | 4 |. Sắp xếp dãy số tăng dần.

Bước 1:
Xét dãy a[0] hiện hành là | 5 | đã có trật tự, số 2 sai vị trí, dịch số 5 sang phải một ô, đặt 2 vào vị trí i = 0, ta có “vết” thứ nhất:
| 2 | 5 | 3 | 1 | 4 |
Bước 2:
Xét dãy con | 2 | 5 | đã có trật tự tăng; 5 và 3 sai vị trí, làm như bước 1: chèn 3 vào vị trí i=1, ta có “vết” thứ hai:
| 2 | 3 | 5 | 1 | 4 |
Bước 3:
Số 5 và 1 sai vị trí, chèn 1 vào vị trí i=2, dịch 5 sang vị trí i=3 ta có “vết” thứ ba:
| 2 | 3 | 1 | 5 | 4 |
Bước 4:
Số 3 và 1 sai vị trí, chèn 1 vào vị trí i=1, dịch 3 sang vị trí i=2 ta có “vết” thứ tư:
| 2 | 1 | 3 | 5 | 4 |
Bước 5: Xét dãy hiện hành: | 5 |
Số 2 và 1 sai vị trí, chèn 1 vào vị trí i=0, dịch 2 sang vị trí i=1 ta có “vết” thứ năm:
| 1 | 2 | 3 | 5 | 4 |
Bước 5: Xét dãy hiện hành: | 5 |
Số 5 và 4 sai vị trí, chèn 4 vào vị trí i=3, dịch 5 sang vị trí i=4 ta có dãy trật tự tăng:
| 1 | 2 | 3 | 4 | 5 |

4. Các bước của thuật toán

Dùng hai vòng lặp:

Vòng lặp ngoài: Duyệt từ a[1] (i = 1) đến cuối dãy (i = n) để tìm vị trí chèn thích hợp cho x.
Bước 1: pos = i - 1; //pos là vị trí chèn, khi i = 1 thì pos = 0, nghĩa là coi đoạn con a[0] đã được sắp.
Bước 2: x = a[i]; //x là phần tử cần chèn.

Vòng lặp trong: Thực hiện lặp lại các việc khi pos >= 0 và x < a[pos]:
Bước a: Đẩy các phần tử sang phải một vị trí để tìm chỗ chèn thích hợp cho x vào đoạn con đã có trật tự:
a[pos + 1] = a[pos];
Bước b: Sau mỗi lần thực hiện Bước a, giảm vị trí chèn xuống 1 đơn vị:
pos--;

Bước 3: a[pos + 1] = x; //Chèn x vào vị trí thích hợp tìm được.
Bước 4: Vòng lặp trong kết thúc khi pos vượt khỏi phạm vi dãy và x = a[pos].

Vòng lặp ngoài kết thúc khi i = n.

5. Cài đặt (C++)

void insertSort(int a[], int n) {
    int pos, i, x;
    for(i = 1; i < n; i++) {
        pos = i - 1;
        x = a[i];
        while((pos >= 0) && (x < a[pos])) {
            a[pos + 1] = a[pos];
            pos--;
        }
        a[pos + 1] = x;
    }
}