Why is the sentence true?

Question

I am looking at the algorithm of the insertion sort:

Input: A[1 ... n]


for j <- 2 to n 
key <- A[j]
i <- j-1
while (i>0 and A[i]>key)
      A[i+1] <- A[i]
      i <- i-1
end
A[i+1] <- key
end

According to my textbook,the proof of the following sentence:

At the beginning of each iteration "for" ,the subsequence $ A[1 \dots j-1]$ consists of the elements that are from the beginning at these positions, but sorted with the desired way.

is the following:

• Initial control, when $j=2:$ The sentence is true,because the subsequence $A[1]$ is sorted in a trivial way.

• Preservation control : The algorithm moves the elements $ A[j-1], A[j-2], \dots $ to the right side,till the right position for $ A[j] $ is found.

• Verification of the result : When the loop "for" ends, $j$ has the value $n+1$. The subsequence is now $ A[1 \dots n]$, which is now sorted.

Could you explain me why we prove the sentence like that? Also,is there an other way to prove it?

Answer 1

Your textbooks gives you a proof by induction for this sentence.

• Initial control gives you a first value $j$ for which the claim holds.
• Preservation control uses the induction hypothesis (claim holds for $j-1$) to perform the induction step (claim holds for $j$).

The idea of proof by induction is the following: You show the claim for one specific value and given that the claim holds for a specific value you give a recipe how to show the claim for the next value.

In your case the claim is trivially true for $j = 2$. In the preservation control you find a recipe that shows you how to prove that the the first $j$ elements are sorted correctly given that the first $j-1$ elements are already sorted correctly.

There are probably other ways to show that this algorithm is correct. However, I think this is the cleanest and easiest way to prove the correctness.