Thread: Bubble Sort

Hi,
I have the following pseudo-code for Bubble Sort, the correctness of which I'd like to prove via induction.

Code:

BubbleSort(input: Array A[1…n], integer n) 
{ 
for i = n-1 to 1 
{ 
 for j = 1 to i 
 { 
if A[j] > A[j+1] 
 swap (A,j,j+1) 
 } 
 } 
}

I am not really sure how to go about it as the fact that the outer loop runs from n-1 to 1 somewhat perplexes me. Should the induction's basis still be i=1, where i denotes the number of iterations the outer loop has run?
Furthermore, would it be correct to say that at the end of the ith iteration A[i+1..n] is sorted, or would it be, rather, A[i..n]?
I'd appreciate some guidance with this.

Furthermore, would it be correct to say that at the end of the ith iteration A[i+1..n] is sorted, or would it be, rather, A[i..n]?

It is not correct to say that. The outer loop simply counts the number of times you should do the inner loop. When the outer loop is finished, the array will be sorted: the inner loop is what actually does the comparing and swapping steps, which makes the sort work. Also, be aware that the pseudocode assumes the array starts at one, but that is not how C works. C arrays start at 0.

Suppose I wished to make an assertion concerning array A at the end of the i-th iteration, in other words describe A. Would it still not be correct to say that A[i+1..n] would be sorted?
How may I go about proving the correctness of this algorithm via induction?

Originally Posted by peripatein

say that A[i+1..n] would be sorted?

Depends if you decrement i before making this statement. After the first loop, the largest value is placed a A[n], so you could consider A[n-1..n] to be sorted, although A[n-1] may not be the second largest number in A[]. After the second loop, A[n-2..n] is sorted ...