Một số giải thuật cơ bản Phần 2 _Insertion Sort

Tiếp theo giải thuật SelectionSort chúng tar bàn tiếp đến giải thuật Sắp xếp chèn trực tiếp – Insertion Sort.
Băt đầu nhé các bạn:

 Ý tưởng: Giả sử có 1 dãy a1 , a 2,…,an trong đó (i – 1) phần tử đầu tiên a1 , a 2,…, a(i-1) đã có thứ tự. Ý tưởng của giải thuật là tìm cách chèn phần tử a vào vị trí thích hợp của đoạn đã sắp xếp để có dãy mới a1 , a 2,…, ai đã có thứ tự. Cứ như thế các phần tử tiếp theo cho đến hết dãy. Vậy ta được 1 dãy sắp xếp.
Minh họa ví dụ Insertion sort 

 Cho dãy số a

 Bước 1: Dãy a0 -a0 đã có thứ tự. Cần chèn a1 vào dãy này để dãy vẩn có thứ tự

Bước 2: Dãy a1-a 0 đã có thứ tự. Cần chèn a2 vào dãy này để dãy vẫn có thứ tự

Bước 3: Dãy a2 -a0 đã có thứ tự. Cần chèn a3 vào dãy này để dãy vẫn có thứ tự

Bước 4: Dãy a3 -a0 đã có thứ tự. Cần chèn a 4 vào dãy này để dãy vẫn có thứ tự

Bước 5: Dãy a4 -a0 đã có thứ tự. Cần chèn a5 vào dãy này để dãy vẫn có thứ tự

Bước 6: Dãy a5 -a0 đã có thứ tự. Cần chèn a6 vào dãy này để dãy vẫn có thứ tự

Bước 7: Dãy a6 -a0 đã có thứ tự. Cần chèn a7 vào dãy này để dãy vẫn có thứ tự

Cài đặt 

Mã nguồn PHP:

 void InsertionSort(int a[],int n)
{
for(int i=1;i<n;i++)
{
int x=a[i];
for(int j=i- 1;j>=0;j- -)
{
if(a[j]>x) a[j+1]=a[j];
else  break;
}
a[j+1]=x;
}
}


Một số bài làm lý thuyết để chúng tar làm quen với giải thuật này.

 Minh họa thao tác sắp xếp dữ liệu theo phương pháp

Insertion Sort cho các dãy dữ liệu sau:

 Sắp xếp tăng:

 13 8 12 6 9 10 12 7

 A H K R E C Z G

 Sắp xếp giảm

 13 8 12 6 9 10 12 7

 A H K R E C Z G

Một số bài tập cho chúng tar cài đặt làm quen trên máy

 Viết bổ sung các hàm vào chương trình xử lý mảng 1 chiều

các hàm thực hiện những yêu cầu sau:

1. Viết hàm sắp xếp tăng theo PP insertion sort cho dữ liệu số

nguyên/số thực/ký tự/ chuỗi ký tự.

2. Viết hàm sắp xếp tăng theo PP interchange sort cho dữ liệu

số nguyên/số thực/ký tự/ chuỗi ký tự.

Tác giả : Trần Thanh Nhã