12

Why would you choose bubble sort over other sorting algorithms?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Neel
  • 9,913
  • 16
  • 52
  • 74

14 Answers14

21

You wouldn't.

Owen Astrachan of Duke University once wrote a research paper tracing the history of bubble sort (Bubble Sort: An Archaeological Algorithmic Analysis) and quotes CS legend Don Knuth as saying

In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.

The paper concludes with

In this paper we have investigated the origins of bubble sort and its enduring popularity despite warnings against its use by many experts. We confirm the warnings by analyzing its complexity both in coding and runtime.

Bubble sort is slower than the other O(n2) sorts; it's about four times as slow as insertion sort and twice as slow as selection sort. It does have good best-case behavior (if you include a check for no swaps), but so does Insertion Sort: just one pass over an already-sorted array.

Bubble Sort is impractically slow on almost all real data sets. Any good implementation of quicksort, heapsort, or mergesort is likely to outperform it by a wide margin. Recursive sorts that use a simpler sorting algorithm for small-enough base-cases use Insertion Sort, not Bubble Sort.

Also, the President of the United States says you shouldn't use it.

Related: Why bubble sort is not efficient? has some more details.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • I disagreed. You answered the question: Why would you use bubble sort in a production environment? That may not be what the interviewer wanted to know. You might use bubble sort in a development or prototyping environment where you wanted to quickly try something. – Vagrant Mar 20 '11 at 20:04
  • 1
    I would contend that you should never use bubble sort. If you want to learn a new language, it's better to learn to use its native sorting functionality than it is to try to write your own sort, and if you were going to write your own sort, writing a good heapsort or insertion sort is probably only marginally more difficult. – templatetypedef Mar 20 '11 at 20:05
  • But the question isn't really about sorting. It's about interviewer questions. And there are environments where there is no native sorting ability. Embedded systems, for instance. Also, heapsort or even insertion sort are not marginally more difficult. It's easy to make a fencepost error. And in a situation where you are sorting a short list, bubble sort is easy to get right without thinking. I assumed that the question was more oriented towards demonstrating the answers lateral thinking ability. – Vagrant Mar 20 '11 at 20:22
  • Ah, I see what you're saying. I think we're approaching this from different perspectives. Some interviewers would think that it's great that you can identify scenarios where you actually would want to use bubble sort (as you've pointed out, in areas where you absolutely must get something working), and would see the fact that you knew that as evidence of critical thinking. Other interviewers would see the fact that you were even thinking about writing your own sort and were considering using bubble sort as evidence that you aren't willing to learn to use existing tools (continued...) – templatetypedef Mar 20 '11 at 20:33
  • 1
    and that you like reinventing the wheel unnecessarily. Most of the interviews I've had have been in the second category, since the interview has focused on "**at this particular job**, what would you do?" instead of "**in some other circumstance**, what would you do?" So I actually agree that you have a valid point. I think that the *actual* best answer would be some combination of the two - "if you're time pressured and don't have a sort available, bubble sort will work in a fix. If you do have time, try investing in something else that has better performance." – templatetypedef Mar 20 '11 at 20:36
  • I see what you're saying about not using the tools available. It would be a dark day when I wrote my own sort instead of using the optimized one provided by the platform. Yes, it would be important to make clear the circumstances. – Vagrant Mar 20 '11 at 20:49
  • 1
    100% agree with templatetypede : NEVER use bubblesort!! – Mitch Wheat Nov 05 '15 at 02:24
9

There's one circumstance in which bubble sort is optimal, but it's one that can only really occur with ancient hardware (basically, something like a drum memory with two heads, where you can only read through the data in order, and only work with two data items that are directly next to each other on the drum).

Other than that, it's utterly useless, IMO. Even the excuse of getting something up and running quickly is nonsense, at least in my opinion. A selection sort or insertion sort is easier to write and/or understand.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • +1 for one interesting example where bubble sort would be optimal - even if the majority including me was probably born years after the last hardware of that kind died ;) – Voo Mar 20 '11 at 22:07
9

You would implement bubble sort if you needed to create a web page showing an animation of bubble sort in action.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
8

When all of the following conditions are true

  • Implementing speed is way more important than execution speed (probability <1%)
  • Bubble sort is the only sorting algorithm you remember from university class (probability 99%)
  • You have no sorting library at hand (probability <1%)
  • You don't have access to Google (probability <1%)

That would be less than 0,000099 % chance that you need to implement bubble sort, that is less than one in a million.

Albin Sunnanbo
  • 46,430
  • 8
  • 69
  • 108
  • +1 for adapting the Drake equation to sorting algorithms. :-) – templatetypedef Mar 20 '11 at 20:04
  • 1
    But then merge sort is easier to implement (it can hardly get easier than a recursive function with a trivial base case), shorter and a whole lot faster, so better add "no recursion allowed" (probability? some embedded systems would have problems with it) to the list ;) – Voo Mar 20 '11 at 21:58
  • I hope that 99% estimate is wrong on probability of remembering only Bubble Sort! Yikes. Insertion and Selection sort both make more intuitive sense and are easy to reconstruct from first principles. – Peter Cordes Jan 14 '23 at 01:52
5

If your data is on a tape that is fast to read forward, slow to seek backward, and fast to rewind (or is a loop so it doesn't need rewinding), then bubblesort will perform quite well.

aaz
  • 5,136
  • 22
  • 18
3

I suspect a trick question. No one would choose bubble sort over other sorting algorithms in the general case. The only time it really makes any sense is when you're virtually certain that the input is (nearly) sorted already.

tvanfosson
  • 524,688
  • 99
  • 697
  • 795
3

I suppose you would choose bubble sort if you needed a sorting algorithm which was guaranteed to be stable and had a very small memory footprint. Basically, if memory is really scarce in the system (and performance isn't a concern) then it would work, and would be easily understood by anybody supporting the code. It also helps if you know ahead of time that the values are mostly sorted already.

Even in that case, insertion sort would probably be better.

And if it's a trick question, next time suggest Bogosort as an alternative. After all, if they're looking for bad sorting, that's the way to go.

Brock Adams
  • 90,639
  • 22
  • 233
  • 295
David
  • 208,112
  • 36
  • 198
  • 279
  • Following up on Bogosort on Wikipedia, I came across this wonderful quote: "H. Gruber's analysis of perversely awful randomized sorting algorithms." – Chris Walton Mar 20 '11 at 19:34
  • 1
    @Chris Walton: I still like my crowd-source idea in the comments above. I'm going to have to suggest that at my job at some point just to see if anybody's actually listening or just looking for buzz words :) – David Mar 20 '11 at 19:36
  • 1
    There are a whole lot of in-place sorting algorithms so that's really no good reason. But +1 for suggesting Bogosort :D – Voo Mar 20 '11 at 21:59
  • @Voo: Agreed. I'd still go with insertion sort under those circumstances. But, all other considerations being roughly equal, at the very least other (entry level) developers would easily understand and be able to support a bubble sort implementation, since they're probably familiar with it. – David Mar 20 '11 at 22:02
3

Bubble sort is easy to implement. While the 'standard' implementation has poor performance, there is a very simple optimization which makes it a strong contender compared to many other simple algorithms. Google 'combsort', and see the magic of a few well placed lines. Quicksort still outperforms this, but is less obvious to implement and needs a language that supports recursive implementations.

BertV
  • 81
  • 1
3

I can think of a few reasons for bubble sort:

  1. It's a basic elementary sort. They're great for beginner programmers learning the if, for, and while statements.

  2. I can picture some free time for a programmer to experiment on how all the sorts work. What better to start with at the top with than the bubble sort (yes, this does demean its rank, but who doesn't think 'bubble sort' if someone says 'sorting algorithms').

  3. Very easy to remember and work with for any algorithm.

  4. When I was starting on linked lists, bubble sort helped me understand how all the nodes worked well with each other.

  5. Now I'm feeling like a lame commercial advertising about bubble sort so I'll be quiet now.

Jason A.
  • 71
  • 1
  • 6
2

It's useful for "Baby's First Sort" types of exercises in school because it's easy to explain how it works and it's easy to implement. Once you've written it, and maybe run it once, delete it and never think of it again.

Paul Tomblin
  • 179,021
  • 58
  • 319
  • 408
2

You might use Bubblesort if you just wanted to try something quickly. If, for instance, you are in a new environment and you are playing around with a new idea, you can quickly throw in a bubble sort in very little time. It might take you much longer to remember and write a different sort and debug it and you still might not get it right. If your experiment works out and you need to use the code for something real, then you can spend the time to get it right.

No sense putting a lot of effort into the sort algorithm if you are just prototyping.

Vagrant
  • 1,696
  • 12
  • 19
2

When demonstrating with a concrete example how not to implement a sort routine.

David Heffernan
  • 601,492
  • 42
  • 1,072
  • 1,490
1

Because your other sorting algorithm is Monkey Sort? ;)

Seriously though, bubble sort is mainly a sorting algorithm for educational reasons and has no practical value.

Janick Bernet
  • 20,544
  • 2
  • 29
  • 55
0

When the array is already "almost" sorted or you have few additions into an already sorted-list, you can use bubble sort to resort it. Bubble sort usually works for small data-sets.

madCode
  • 3,733
  • 5
  • 26
  • 31
  • If an element has to move far in the "wrong" direction, it takes N^2 work to sort. If the inner loop bubble direction matches the direction the element has to move, the outer loop might only run twice to insert a new element. So it's usable, but still slower than Insertion Sort which can basically do a `memmove` while finding the place to store the new element. No pointless storing and reloading of the element as it bubbles along. Insertion Sort is literally designed around having the last `k` elements not yet sorted, so it's a perfect fit for appending and sorting. – Peter Cordes Jan 14 '23 at 01:59
  • https://en.wikipedia.org/wiki/Bubble_sort#Rabbits_and_turtles – Peter Cordes Jan 14 '23 at 02:06