0
$\begingroup$

I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction.

Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for induction step: remove one element out of $n+1$ elements array, which makes array with $n$ elements. According to hypothesis algorithm will sort this array. Now add back the element you removed before and run the algorithm for just one iteration of outer-loop which makes array sorted.

I know this proof is not valid for correctness, but i am not able to see the mistake. I would really appreciate if you could review it and tell me the mistake.

$\endgroup$

2 Answers 2

0
$\begingroup$

BubbleSort can be expressed in a few different ways, I'm assuming you're referring to something similar to wikipedias formulation.

The mistake in your proof is that you assume that sorting an $n + 1$ element list is the same as sorting an $n$ element list, adding one element and sorting again. But that isn't the case, the inner loop always iterates over all elements of the list⁺. So sorting a list of length $n$ and sorting the first $n$ elements of a list of length $n + 1$ is not the same procedure (for example, try sorting [3; 1] and [3; 1; 2] by hand).

The idea behind your argument can be adapted though, instead of using induction over the length of the list use it over the number of iterations of the outer loop, i.e. prove that:

A list of length $m > n$ is sorted up to the $n + 1$th element after $n$ iterations of BubbleSort's outer loop.

The correctness of BubbleSort is a direct result of the above.


(+) There are some formulation of BubbleSort in which the inner loop doesn't iterate over the whole list except for in the first iteration of the outer loop. For a list A = [a_1; a_2; ...; a_n]:

BubbleSort(A):
for j = n - 1 step -1 until 1 do
    for i = 1 step 1 until j do
        if A[i + 1] < A[i] then interchange A[i] and A[i + 1]

(taken from The Design and Analysis of Computer Algorithms, p.102)

But a similar argument as above can be made here.

$\endgroup$
0
$\begingroup$

What you have proved: You can sort an array with your “modified bubble sort” algorithm which goes like this: Sort the first n elements using “modified bubble sort”, then do one more bubble sort pass. This is a slightly different algorithm.

I figured out a small modification to the bubble sort code where your proof worked - then I looked closer and the my modified code was insertion sort!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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