Difference between revisions of "TADM2E 1.9"

From Algorithm Wiki
Jump to: navigation, search
(Replaced content with "''")
(Undo revision 1060 by FuckMatt (talk))
 
(2 intermediate revisions by 2 users not shown)
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

Latest revision as of 01:02, 1 August 2020

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