Insertion sort

Tư Tưởng :

- Chia dãy đã xếp thành hai dãy con

+ Dãy được xếp ban đầu có 1 phần tử .

+ Dãy chưa xếp : phần còn lại

- Lấy từng phần tử của dãy chưa xếp chèn vào dãy đã xếp sao cho thỏa mãn dãy được xếp

Lượt 1: Xếp X2 vào dãy được xếp ,nếu X2<X1 thì di chuyển X1 về phía sau 1 chỗ và chèn X2 vào vị trí của X1 .

...

Lượt i: Xếp X(i+1) vào dãy đã xếp, chèn X(i+1) vào dãy đã xếp từ X1à Xi

Trong khi X(i+1) còn nhỏ hơn phần tử của dãy được xếp thì dịch chuyển

các phần tử đó về phía sau 1 chỗ và chèn X(i+1) vào đó .

- Thuật toán dừng khi xếp nốt n-1 phần tử .

Thủ tục :

void InsertionSort(int X[20],int n)

{

int i,j,T;

for(i=2;i<=n;i++)

{

T=X[i]; // T:khóa cần chèn vào dãy đã xếp

j=i-1; // vị trí của dãy đã xếp

while(T<X[j])

{

X[j+1]=X[j];

j=j-1;

}

X[j+1]=T;

}

}

Đánh giá giải thuật :

- Đơn giản ,dễ hiểu và dễ cài đặt .

- Không tối ưu : độ phức tạp hàm mũ (cỡ O(n2))

2. Việc sắp xếp phụ thuộc vào tình trạng dãy số ban đầu trường hợp thuận lợi nhất ứng với dãy khóa đã được xếp rồi .Như vậy mỗi lượt cần 1 phép so sánh .

Do đó :

Cmin=n-1

Nhưng nếu dãy khóa ban đầu có thứ tự ngược với thứ tự sắp xếp thì lượt thứ i cần có Ci=(i=1) phép so sánh

Vì vậy:

Cmax=n(n-1)/2

Nếu giả sử mọi giá trị khóa đều xuất hiện đồng khả năng thì TB ở lượt thứ i có thể coi như Ci=1/2 phép so sánh .

Suy ra : Ctb=∑(i/2)(n2+n-2)/4