1
$\begingroup$

In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only comparisons and no swaps in the inner loop.

But is that correct? Are comparisons not counted in the complexity ? Only swaps?

Other sources claim the reason is only because it can be optimized with a ' flag' checking if it entered the inner loop. In that case there would be ZERO swaps and n comparisons. ( If this reason is correct, can't I optimize other sorting algorithms this way? Likesay, selection sort?)

What is the correct reason? I questioned both of the reasons!

EDIT: this is what is said in the link: "In the best case, it is of order n because it just compares the elements and doesn’t swap them"

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Exactly because comparisons are counted. $\endgroup$ – John L. Nov 6 '18 at 0:46
  • $\begingroup$ If they are counted then the first link I sent is wrong! Because then... If you don't put a flag there would be n squared comparisons . So just because it doesn't swap doesn't mean it's complexity isn't n squared. So what it says is wrong. The order is n only if you put a flag. No? $\endgroup$ – bilanush Nov 6 '18 at 0:49
2
$\begingroup$

Understanding how Bubble Sort works is of course really the key here.

The main part for unraveling this is that Bubble Sort goes back to the start if it ever performs a swap. If it never performs a swap, it runs along the array once, comparing each element to the one after it, and thus performing $O(n)$ comparisons.

So both sources are correct. The comparisons are counted in the complexity, you just do more of them (and some other things) if you need to swap stuff.

The reason this doesn't work for something like Selection Sort is that Selection Sort looks for the next element to place at the end of the sorted section in each pass. It doesn't know where that element is, and moreover, it always "moves" something (even if it's a trivial move), and whether you made a trivial move doesn't affect whether you will next time either (whereas in Bubble Sort, if you don't move anything, you know you never will).

You could add a check at the start to see if the array is already sorted of course.

Other sorting algorithms can benefit from similar cases to that in Bubble Sort though; Insertion Sort for example has best case $O(n)$ behaviour as well.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank! But I do not understand what you wrote in the beginning. If comparisons are indeed counted in the complexity.... Then the first source in the link is WRONG ! Because it would only work O(n) only if you put a flag that stops the loop . If you don't put a flag then it would still make n squared comparisons. $\endgroup$ – bilanush Nov 6 '18 at 0:42
  • $\begingroup$ You wrote "If it never performs a swap, it runs along the array once, comparing each element to the one after it, and thus performing O(n) comparisons.". NOT CORRECT!! It is correct only if you put a flag. It isn't innate to bubble Sort. Then you wrote "So both sources are correct. " But you don't explain why is the first one correct. $\endgroup$ – bilanush Nov 6 '18 at 0:54
  • $\begingroup$ @bilanush It more that the first reference just doesn't give you the full story, it's not wrong, it just hasn't bothered to give you the code for a reasonable implementation. I guess if your actual question is "can you implement Bubble Sort badly?", then sure, the first one makes the false assumption that you wouldn't. $\endgroup$ – Luke Mathieson Nov 6 '18 at 9:59
  • $\begingroup$ Why it isn't wrong? I think it is WRONG. Because it says the reason bubble sort is lower order of n is because if it's sorted it would just perform comparisons and no swaps. This is WRONG since swaps take more time as well. The only reason is better is because you can put a flag nothing less nothing more $\endgroup$ – bilanush Nov 6 '18 at 13:08
  • $\begingroup$ @bilanush You're right that you need some mechanism to check if it's sorted, but seeing as the standard lecture on Bubble Sort is "here's Bubble Sort without any checks, this is a dumb way of doing it, never bother to do that, here's the proper way" they're just starting from there. $\endgroup$ – Luke Mathieson Nov 7 '18 at 0:39
0
$\begingroup$

Note that The linked article says,

After each iteration, the number of comparisons decreases and at last iteration only one comparison takes place.

If we take the statement, "at last iteration only one comparison takes place" literally, it implies the version of bubble sort used in that article does not use the standard optimization techinique, stopping once no swaps have happened in an iteration. That article is then wrong in its statement, "the best case complexity (when the list is in order) of the bubble sort is of order $n$ ($O(n)$)", since that version of bubble sort runs with time-complexity $O(n^2)$.

The correct statement should be all implementations of bubble sort at Wikipedia run with $O(n)$ time-complexity at best cases, when the given list of elements are sorted.

On the other hand, as Luke Mathieson pointed out, the standard lecture on bubble sort is "here's bubble sort without any checks, this is a dumb way of doing it, never bother to do that, here's the proper way". So, it is not surprising that some people just start from there implicitly sometimes, without realizing that it might be confusing in telling $O(n)$ best time-complexity for all versions of bubble sort.

The general convention is that comparisons are counted in the complexity of any sorting algorithms. Swaps might not be counted in some models of complexity analysis.

Regarding to the usage of flags, I cannot, in fact, see how one can use flags in a similar way to improve the performance of selection sort although you can always check if the input array is sorted or not beforehand for any sorting algorithm.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I agree that it's wrong. But you don't mention the other things that are wrong there . I quote "In the best case, it is of order n because it just compares the elements and doesn’t swap them" the reason itself which they mentioned is wrong $\endgroup$ – bilanush Nov 8 '18 at 15:49
  • $\begingroup$ Now I see how you might have understood the original article, which was indeed very confusing. You might have understood it as "it is of order $n$ because it just compares elements $n(n-1)/2$ times and doesn't swap them". That reasoning is, indeed and of course, so obviously wrong that it can only understood to be a typo. In general, most of experience users (or at least me) understood that statement as referring to the optimized bubble sort, in which case, that statement is fully correct. $\endgroup$ – John L. Nov 8 '18 at 16:34

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.