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

[Demo Đồ họa] Thuật toán sắp xếp

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ã ngôn ngữ C

void InsertionSort(int a[], int N)
{
   int pos, i;
   int x; // lưu giá trị a[i] tránh bị ghi đè khi dời chổ các phần tử
   for (i = 1; i < N; i++)
   {
      x = a[i];
      pos = i - 1;
      //Tìm vị trí chèn x
      while ((pos>0) && (a[pos] > x))
      {
         //Kết hợp dời chổ các phần tử sẽ đứng sau x trong dãy mới
         a[pos + 1] = a[pos];
         pos--;
      }
      //Chèn x vào dãy
      a[pos + 1] = x;
    }
}

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.

6. Nhận xét
Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i-1], do đoạn đã được sắp xếp, nên có thể sử dụng giải thuật tìm kiếm nhị phân để thực hiện việc tìm vị trí pos, khi đó có giải thuật sắp xếp chèn nhị phân:

Mã ngôn ngữ C

void BinaryInsertionSort(int a[], int N)
{
   int l,r,m, i;
   int x; // lưu giá trị a[i] tránh bị ghi đè khi dời chổ các phần tử
   for (i = 1; i < N; i++)
   {
      x = a[i]; l = 1; r = i - 1;
      //Tìm vị trí chèn x
      while (l<=r)
      {
         m = (l + r) / 2;//tìm vịt trí thích hợp m
         if (x < a[m])
            r = m - 1;
         else
            l = m + 1;
      }
      for (int j = i-1; j >=l; j--)
         a[j + 1] = a[j];//dời các phần tử đứng sau x

         //Chèn x vào dãy
         a[l] = x;
    }
}

7. Đánh giá giải thuật

Thuật toán sử dụng trung bình n2/4 phép so sánh và n2/4 lần hoán vị, n2/2 phép so sánh và n2/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 thích hợp đối với mảng đã được sắp xếp một phần hoặc mảng có kích thước nhỏ.

Insertion Sort và Selection Sort đều có chi phí cho trường hợp xấu nhất là O(n^2).

Insertion Sort tốt hơn Selection Sort nhất là khi mảng đã có thứ tự sẵn.

Các thuật toán sắp xếp khác:

[Thuật toán sắp xếp] Selection Sort

[Thuật toán đang xem] Insertion Sort + Binary Insertion Sort

[Thuật toán sắp xếp] Interchange Sort

[Thuật toán sắp xếp] Bubble Sort

[Thuật toán sắp xếp] Quick Sort