News for hackers. Stuff that matters.
Re:Programmers can’t write algorithms without help by Gunax on Monday November 04, 2019 @11:48AM (#21443452)
I've been a developer for almost 2 years (I know not that long) but I have never even heard of bubble sort. Looking it up, it is O(n^2). Is there a reason this is a common interview question? It doesn't seem like a sort one would ever really use, or at least it has very obscure uses.

I always thought merge/quick sorts accounted for 99.9% of use cases and only ever really learned about those.

Re:Programmers can’t write algorithms without help by cinnamonheart on Monday November 04, 2019 @11:59AM (#21443605)
The logic of bubble sort is so simple that just the description is enough for an implementation. It's a common interview question for the same reason Fizzbuzz is used -- any programmer worth their salt should be able to just write it down.

Insertion and selection sort are also O(N^2), but sorts like merge and quick will use them to sort small sublists in their recursive cases because they are fast when input is small enough.

Re:Programmers can’t write algorithms without help by Gunax on Monday November 04, 2019 @02:16PM (#21445287)
I see. I would hope one would give a description of what bubble sort is during the question.

It's definitely easy to implement, it just had me worried because I had never heard of it!

Re:Programmers can’t write algorithms without help by brozaman on Monday November 04, 2019 @04:20PM (#21446630)
I guess it's a common question because it's usually taught in college because it's probably the simplest after select sort.

Personally I've never found this case myself, but regarding why it's used some times, the O(n²) is the worst case scenario. The best case scenario is O(2n) which is really good, so for lists that are sorted or almost sorted it works well.

Other algorithms like timsort have O(n) for the best case scenario, but O(n) only tells you how many times you go through the loop. Without actually measuring it, I would expect each iteration of timsort to be at more than twice as expensive as bubble sort, so in this case O(2n) would be cheaper than O(n).

When you know with a certain degree of certainty how is the data you expect in most cases, some times it's kinda easy to make a more efficient algorithm than the one that is the best for the average scenario.

Re:Programmers can’t write algorithms without help by tzs on Monday November 04, 2019 @12:41PM (#21444085)
Keep in mind that big-O notation describes how something behaves as the problem size goes up. Something O(n^2) will be slower than something that is O(n log(n)) for large enough n. For smaller n, it is quite possible that an O(n^2) algorithm can beat an O(n log(n)) one.

If you have an application that only has to sort small lists, but has to sort a lot of them, it is quite possible that an O(n^2) sort like bubble, insertion, or selection sort will be better than merge/quick sort.

Among the O(n^2) sorts, insertion almost always will be faster than bubble, so you probably wouldn't actually choose bubble sort.

Re:Programmers can’t write algorithms without help by Gunax on Monday November 04, 2019 @02:19PM (#21445324)
I understand. In a sense merge/quick are 'galactic algorithms' at the size.

It's more just that I am concerned I would be cornered trying to remember what 'bubble sort' is. It's not difficult to write the algorithm per se--just hard to remember what 'bubble sort' means.

Re:Programmers can’t write algorithms without help by kadoban on Monday November 04, 2019 @12:06PM (#21443709)
It's not one you'd ever use in practice (I know of no use at least). It's pretty simple to implement given a short description though, so it can be seen as kind of an "advanced" fizzbuzz.

If someone just says "hey, implement bubblesort", that's pretty awful though. Then it's just testing your memory and/or gating by people that studied a particular algorithms curriculum. (Though _many_ intro algorithms courses go through sorting and most of those mention bubble sort probably)

Re:Programmers can’t write algorithms without help by mark-r on Monday November 04, 2019 @12:02PM (#21443643)
Bubble sort is good for two reasons. First, it's so easy that anybody should be able to remember how to do it. Second, it's slow and everybody should know that and be able to point it out.

It's actually usable for small enough n. I once coded it when I expected n to be 4 or less, and I'm sure the person who replaced it cursed my name when that expectation turned out to be false.

Re:Programmers can’t write algorithms without help by kadoban on Monday November 04, 2019 @12:09PM (#21443731)
For a simple sort you can use for small N, I'd suggest insertion sort. Its constants are better, it performs well on almost-sorted input, and I think it's even easier to implement, personally.
Re:Programmers can’t write algorithms without help by mark-r on Monday November 04, 2019 @12:11PM (#21443763)
Yes, I've heard that suggestion many times since then. I wasn't well versed on the different sorts at the time.
Re:Programmers can’t write algorithms without help by mordechai9000 on Monday November 04, 2019 @12:37PM (#21444045)
I think bubble sort is used in beginner CS classes because it's easy to understand the operation and the complexity. It makes a good prologue before moving on to more efficient sorting algorithms.

I only remember it because a machine language book for the Motorola 6809 used it as an introductory program.

Re:Programmers can’t write algorithms without help by MatekCopatek on Monday November 04, 2019 @11:58AM (#21443602)
I think it's just the simplest sort to describe/implement on a whiteboard.