(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 < A < A <......... < 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 < A < A <......... < A[k] < A[k+1]

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

QED

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