Loop Invariant - a property of a program loop that is true before (and after) each iteration

From: Wikipedia - Loop invariant

# EN

## Introduction to Algorithm

In the book Introduction to Algorithm, loop invariant is included in chapter 2.1, which is in the insertion sort. Loop invariant is employed to establish the correctness of the algorithm, which is also able to be applied on other algorithms.

Three conditions must to be held true:

1. Initialization: It is true prior to the first iteration of the loop
2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

In the case of insertion sorting, the loop invariant is:

At the start of each iteration of the for loop of line 1-8, the subarray $A[1 ..j-1]$ consists of the elements originally in $A[1 ..j-1]$, but in sorted orders.

three conditions became:

1. Initialization: We start by showing that the loop invariant holds before the first loop iteration, when $j=2$. The subarray $A[i] ..j-1]$, therefore, consists of just the single element $A[1]$, which is in fact the original element in $A[1]$. Moreover, this subarray is sorted (trivially, of course), which shows that the loop invariant holds prior to the first iteration of the loop.

In plain word, this is saying, before the iteration starts, there is only one element in the sorted subarray, and therefore it’s sorted which satisfies the condition.

2. Maintenance: Next, we tackle the second property: showing that each iteration maintains the loop invariant. Informally, the body of the for loop works by moving $A[j-1], A[j-2], A[j-3]$, and so on by one position to the right until finds the proper position for $A[j]$, at which point it inserts the value of $A[j]$. The subarray $A[1..j]$ then consists of the elements originally in $A[1..j]$, but in sorted order. Incrementing $j$ for the next iteration of the for loop then preserves the loop invariant.

This is saying that, with each iteration, the values before current value are sorted.

3. Termination: Finally, we examine what happens when the loop terminates. The condition causing the for loop to terminate is that $j>A.length=n$. Because each loop iteration increases $j$ by 1, we must have $j=n+1$ at that time. Substituting $n+1$ for $j$ in the wording of loop invariant, we have that the subarray $A[1..n]$ consists of the elements originally in $A[1..n]$, but in sorted order. Observing that the subarray $A[1..n]$ is the entire array, we conclude that the entire array is sorted. Hence, the algorithm is correct.

When the loop ends, each element is iterated; the whole array is sorted. Consequently, the termination determines the correctness of the algorithm.

## Other Explanation

I found that the example from wikipedia and What is a loop invariant? is very easy to understand.

### StackOverflow

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that $i >= 0$ && $i <= 10$.

# Reference

Introduction to Algorithm

Loop invariant

What is a loop invariant?