6 ms·

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

by Gunax 7y ago

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.

MatekCopatek 7y ago
I think it's just the simplest sort to describe/implement on a whiteboard.
cinnamonheart 7y ago
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.
- Gunax 7y ago
  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!
mark-r 7y ago
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.
- kadoban 7y ago
  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.
  - mark-r 7y ago
    Yes, I've heard that suggestion many times since then. I wasn't well versed on the different sorts at the time.
kadoban 7y ago
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)
mordechai9000 7y ago
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.
tzs 7y ago
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.
- Gunax 7y ago
  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.
brozaman 7y ago
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.

by Gunax 7y ago

MatekCopatek 7y ago

I think it's just the simplest sort to describe/implement on a whiteboard.

cinnamonheart 7y ago

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.

Gunax 7y ago
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!

mark-r 7y ago

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.

kadoban 7y ago
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.
- mark-r 7y ago
  Yes, I've heard that suggestion many times since then. I wasn't well versed on the different sorts at the time.

kadoban 7y ago

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)

mordechai9000 7y ago

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.

tzs 7y ago

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.

Gunax 7y ago
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.

brozaman 7y ago

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.