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

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