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, a, ..., 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.