0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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]$

$\endgroup$
  • $\begingroup$ Thanks for answer! :D I'm not sure if I understand it correctly though. Is your first paragraph really sufficient to prove that the loops will terminate? Or is induction required here? Because can we just say that array length is finite? $\endgroup$ – cnmesr Dec 15 '18 at 0:38
  • $\begingroup$ @cnmesr To show that the algorithm terminates you indeed just need to point out that the array is of finite length ... no induction needed. $\endgroup$ – Bram28 Dec 15 '18 at 0:58
  • 1
    $\begingroup$ 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. $\endgroup$ – obscurans Dec 15 '18 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.