Difference between revisions of "TADM2E 1.9"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Replaced content with "''")
Line 1: Line 1:
'''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'''
 
 
 
--[[User:Aroonalok|Aroonalok]] 23:29, 16 August 2013 (EDT)Aroonalok
 

Revision as of 02:00, 14 July 2020