|
|
| 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
| |
