Difference between revisions of "TADM2E 1.9"
Revision as of 18:13, 11 September 2014
n = 1
The single-element List is sorted.
Assume the algorithm is true for n<=k
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)].
--Aroonalok 23:29, 16 August 2013 (EDT)Aroonalok