# TADM2E 1.9

**n = 1**

The single-element List is sorted.

**Assume** the algorithm is true for **n<=k**

i.e.,

for i from k to 1 for j from 1 to i − 1 if (A[j] > A[j + 1]) swap the values of A[j] and A[j + 1]

produces a sorted list[1...k].

Let **n = k+1**

for i from k+1 to 1 for j from 1 to i − 1 if (A[j] > A[j + 1]) swap the values of A[j] and A[j + 1]

Here, the inner loop (having counter j) just "bubbles out" the maximum element to the i-th position in the list.

So, in the first iteration with i = k+1 , on the completion of the inner loop, A[k+1] contains the maximum element of the list.

At this point, i = k and we are left with the task of sorting a k-element list which is already assumed to be performed correctly by the algorithm.

After the completion of all the iterations we have :

**(i)** A k-element sorted list (ascending order) :

A[1] < A[2] < A[3] <......... < A[k]

**(ii)** Also we have A[k+1] as the maximum element of the list. This implies A[k] < A[k+1]

From **(i)** and **(ii)** we get

A[1] < A[2] < A[3] <......... < A[k] < A[k+1]

which is a sorted list[1...(k+1)].

**QED**

--Aroonalok 23:29, 16 August 2013 (EDT)Aroonalok