Given is the Bubble sort algorithm
Bubblesort(A) for i=1 to A.length for j=A.length downto i+1 if A[j] < A[j-1] exchange A[j] with A[j-1]
How do you prove that both these
for loops will terminate?
I'm not sure how to prove that, I can only tell that the inner loop will terminate if
j=j+1 and if you reach that, the length of the subarray will be increased by $1$ and the first element of the subarray will be its smallest because you swap
The outer loop will terminate if
i=A.length because there A[1...n] will include all elements in sorted order.
But how could this be proven? I think it should work with induction because you start at $1$ and walk step by step through the array till you reach its end, swap adjacent elements if condition is met but how would that look like? Or maybe there is a different way than induction too? :S