Với thuật toán sắp xếp chèn, chứng minh rằng nếu thay toàn bộ phần Chèn A[i]

Giải Tin học 11 Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình

j=1

while j>0 and A[j]<A[j-1]:

 Đổi chỗ A[j] và A[j-1]

 j=j-1

Lời giải:

Để chứng minh tính đúng đắn của thuật toán sắp xếp chèn với các lệnh thay đổi trên, ta cần chứng minh hai điều kiện sau đây:

Điều kiện ban đầu (trước khi bắt đầu vòng lặp): Sau khi thực hiện lệnh j = 1, giá trị của j đang là 1, và dãy con A[0] chỉ gồm một phần tử là A[0] (vì j-1 là 0). Do đó, dãy con này đã được sắp xếp đúng.