Proof of the Bubblesort algorithm

Question

I'm studying The Algorithm Design Manual and I was having some difficulty in the proof exercises, so I asked a question here. Based on the answer I got in that question(which was not the a complete proof),I came up with a proof.

Prove the correctness of the following sorting algorithm.
    Bubblesort (A)
        for i from n 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]

1.Base case:
    An array of length 1 which is by definition sorted.

2.Inductive hypothesis:
    We'll assume that for all arrays of length (0 <= m) one iteraion of the outer loop with "n" being the length of the array,
    the array gets permutated in such a was  that the last element in the array is the biggest.

3.Inductive step:
    We want to prove that if our assumption is true for lists of length (0 <= m), then it is also true for lists of length (m)

    Let A = a[0], a[1], ..., a[m] (of length m+1)
    After (m-1) iterations of the inner loop based on our assumption, in the list A[0:m-1], a[m-1] is the biggest element.
    At this point,as (j < m),we have one more iteration to perform.
    Before this, j was equal to m-2 and j+1 was equal to m-1. After this loop, j will be equal to m-1 and j+1 will be equal to m.
    If A[m-1] and A[m] satisfy the if statement, that is, A[m-1] > A[m], they will swap.If not, then that would mean that A[m] is 
    the biggest element in the list.
    In either case, the last element of the list will be the biggest after one iteration of the outer loop, which was what we were
    trying to prove.  ▮

I'm not really sure of it's correctness,so I would really appreciate if you could review it and tell me whether its correct or not. Also please note any inadequacies it may have or things I could've done better as I'm quite new to inductive proofs.

Answer 1

Your induction hypothesis is insufficient. In the hypothesis, you are just proving that the last element of the array has the maximum value. However, you have to prove that the resulting array is sorted. Therefore, your induction hypothesis should be the following:

Hypothesis: At the end of 't' iterations of the outer "for" loop, the "n-t" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t+1' to 'n'.

Base case: For 't = 1', the induction hypothesis says that at the end of the first iteration of the outer "for" loop, the algorithm gives the highest element at the index 'n'. And, you can easily prove this statement.

Induction Step: At the end of 't+1' iterations of the outer "for" loop, the "n-t+1" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t' to 'n'. Again, you have to prove this step using the earlier mentioned hypothesis -- for 't' iterations.

This proves the induction hypothesis. And, now you can simply say that at the end of 'n' iterations of the outer "for" loop, all elements of the array are in the sorted order and they occupy the indexes from '1' to 'n'.