2
$\begingroup$

This site already has some questions on this topic but I am confused after reading some of the answers.

Evaluating the average time complexity of a given bubblesort algorithm.

In the above link, answer by "Joe" says that number of swaps in bubble sort on average is same as number of inversions on average which is (n)(n-1) / 4.

However, https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms says that in bubble sort average number of swaps is $n^2 / 2$ and in insertion sort it is $n^2 /4$ and that's the reason for insertion sort being better than bubble sort.

Which one is correct? Can someone please help me?

$\endgroup$
2
$\begingroup$

There is a big difference between the first answer you quote, on this site, and the second answer you quote, on stackoverflow: while the answer on cs.se contains an argument, the answer on stackoverflow just states the result without any explanation. This means that you can verify the answer on cs.se: you can check whether the proof is correct, and whether the result answers your question. In contrast, there is no way to know whether the answer on stackoverflow is correct or not, apart from trusting its poster.

This highlights a general difference between programmers and computer scientists. Programmers just want to know the answer, and generally don't care whether it's correct or not. Computer scientists, in contrast, want to see some evidence: a proof if one is available, or results of experiments (or both, in some communities).

Two more proofs of the formula $\frac{n(n-1)}{4}$ can be found on math.se and on cs.se. See if any of these convince you of this formula. You have to check both the statement (whether you are counting the correct expectation) and the proof.

Another thing you can do is experimentally determine the veracity of these proofs. This would entail programming both algorithms, and running them on many different arrays of length $n$ for various values of $n$, thus estimating the number of swaps.

A user on stackoverflow did a simpler experiment which suggests that the number of swaps is the same in bubble sort and inversion sort (at least for the user's version of these algorithms, quoted in the question). This would imply, of course, that the average number of swaps is the same in both algorithms.

$\endgroup$
  • $\begingroup$ So you say that on average, both insertion and bubble sort perform equally ? If not, can you give an example where bubble sort outperforms insertion sort? $\endgroup$ – Zephyr Nov 26 '17 at 15:16
  • $\begingroup$ My answer is only about the number of swaps (or comparisons). Besides, I think I've given you enough tools to explore this question on your own. $\endgroup$ – Yuval Filmus Nov 26 '17 at 15:42
  • $\begingroup$ To be honest, the links or tools which you have given are the ones which OP had already discovered. (Regarding the no of comparisons). $\endgroup$ – Sagar P Nov 26 '17 at 15:50
  • $\begingroup$ @SagarP Are you sure? The user gave 2 links, and I gave 3 more. $\endgroup$ – Yuval Filmus Nov 26 '17 at 15:52
  • $\begingroup$ Yes, out of those 3, 2 of them show the number of comparisons which OP already knows. I think it would have been better if you could have added how is insertion sort actually better than bubble sort. $\endgroup$ – Sagar P Nov 26 '17 at 16:13

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.