# Prove that the two loops in this sorting algorithm will terminate

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 A[i+1] with A[i].

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

They both terminate simply because the length of $$A$$ is finite, so the algorithm goes through the outer loop exactly $$length$$ many times, while during each pass of the outer loop, the algorithm passes through the inner loop between $$1$$ and $$length -1$$ times ... which is therefore finite as well.
Of course, proving that when the algorithm is done, the array is sorted, is a little more difficult. But you're right: use induction to show that after $$i$$ passes of the outer loop, the elements $$A[1]$$ through $$A[i]$$ are sorted in increasing order, while the elements in $$A[i+1]$$ are all greater or equal to $$A[i]$$
• A possibly simpler argument is: the outer loop executes exactly length times, and each time the inner loop executes at most length times each. So the inner loop cannot possibly execute more than length ${}^2$ times, hence it will terminate. – obscurans Dec 15 '18 at 3:19