Hacker News Reader

Comment by blt | Hacker News Reader

I'm more shocked that bubble sort is used in production somewhere...

A common optimization is to use insertion sort for small arrays (less than 64) and quicksort/heapsort/introsort for larger ones. Usually because better algorithms in terms of Big O have worse constant factors.

Last time I looked at the source for Java's dual pivot quicksort implementation, it used exactly this for 7 elements or fewer

Yes, and qsort does similar (different algorithms for different array sizes but the same function interface).

For me it's that they aren't testing it. This sort of functionality is so trivial to write unit tests for, so simple that it's the fastest and easiest way to write and debug the sort method.

It'd make me question the stability of the rest of their product too.

Actually, that's a fascinating part of the story. We run the entire test262 ECMAScript Conformance Suite (https://github.com/tc39/test262) against our JS-Interpreter fork. We don't pass the whole thing yet, but it ensures we only ratchet toward conformance to the language spec.

We checked, and this particular bug was not caught by the test262 suite - the broken sort worked for enough cases to slip past the Array.prototype.sort tests there. We've added a regression test for this issue in the layer that consumes the interpreter, but I've thought about proposing more aggressive validation of sort behavior to the test262 project.

It was a great reminder to me that while tests may be necessary for quality, they are not always sufficient!

Brad, Code.org Engineering

This is in a custom interpreter (used for teaching I think)

https://github.com/code-dot-org/JS-Interpreter

I think we need to get away from this attitude, that I used to hold, that O() is everything. It isn't. It isn't even close. We should instead wonder why an algorithm was chosen without regard for the nature of the data on which it will be applied. For sorting O(n lg n) only makes sense as a selection criteria if you have absolutely no idea about what data is being sorted. Why is that?

If the answer is you just don't care about the perfromance and can say why it isn't important (at least yet) as long as you avoid the pathological then that's a good answer. It's a really bad answer to assume it when you can't. IMHO.

Others have pointed out that bubble sort is great when your data is already mostly sorted. The textbook example is check stub ids, which are sequential - probably an outdated example nowadays. The benefit is greater than a O() analysis would have you believe because running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching. Minimising cache misses /may/ dominate the number of passes of the data in performance analysis. If you don't care about performance then an O(N^2) algorithm may be also something you don't care about.

Hu. Bubble Sort. And not only that; a buggy version!

And if you believe sequential access is gonna save you from O()... you're so wrong its not even funny. Of course the curves will cross latter. But they will cross. Especially on a sort.

I'm not sure you've demonstrated anything here about the topic under discussion. You might like to try achieve a better result around here, people tend to appreciate it.

You're misidentifying the attitude. The problem is that Bubble Sort is a terrible algorithm, there's no reason not to use Insertion Sort or better instead except for some reason CS programs still inflict BS on students so that's what they remember when they just need to sort something.

http://warp.povusers.org/grrr/bubblesort_eng.html

http://warp.povusers.org/grrr/bubblesort_misconceptions.html (Bubble sort is not great when your data is almost sorted. Insertion sort is, though.)

To the second link

"Bubble sort always performs n-1 passes through the data (where n is the amount of elements), and it always performs (n-1)+(n-2)+...+1 comparisons regardless of how the data is organized to begin with."

That is just false. 1 pass and n-1 comparisons then stops for already sorted data is what you get. An implementation that doesn't show that characteristic has been either deliberately or accidentally pessimized to behave poorly. You can gimp any algo to make it look bad. Quicksort without randomization on a pathological case is O(n^2) for example and nobody cares for the overwhelming majority of practical purposes. If your definition of bubble sort is that it must be O(n^2) always then we're not using "bubble sort" to mean the same thing and it's pointless to continue the discussion.

Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? You pay for additional copies in both space and cpu cycles. 2xn space for selection usually - but maybe this can be avoided without paying a very high time overhead, (eg find the spot, ripple all data below the spot down to the hole where you selected to open a slot for insert or similar).

Count the memory operations, ie number of memory reads and number of memory writes for a given set of data comparing the two algorithms.

Suggestions: Write 50 odd lines of C code to see the actual effect in cpu cycles. Craft data to make each algorithm dominate the other, it's really interesting to see.

I'm disinclined to say "Never uses algo X, always use algo Y!" Because it's really hard for that to be sensible given all the various shapes and sizes input data takes. Know your data is always really, really good advice.

> Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible?

What about insertion sort? Which always performs fewer comparisons and swaps than bubble sort for any array, by the way.

So I made the case with evidence that it doesn't always perform fewer comparisons and it it doesn't always perform fewer swaps. While it probably does, depending on implementation details use more memory. Do feel free to actually make your case with evidence, that I would be interested in reading.

What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.

> While it probably does, depending on implementation details use more memory

Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort.

Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"

1,2,3,4,6,5,7

6 comparisons, 1 swap with bubble and it stops. I make it 7 memory reads and 2 memory writes.

Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.

Bubble sort performs 11 comparisons and 13 memory reads in this case, actually. Because on the first pass through the array it performed a swap, it has to loop through the array a second time to verify the array is completely sorted.

To avoid confusion, here's the bubble sort algorithm:

  procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
  end procedure

As you can see, after performing a swap during the first pass through the array it has to go through again (though it can skip the last element because we know the last element must contain the largest element in the array)

Insertion sort will perform 7 comparisons, 1 swap, 7 memory reads and 2 writes.

You can avoid the second pass...

No, you can't, because at the end of the first pass you have no way to know that it is in sorted order. Go ahead and try to write the pseudocode for your bubble sort implementation that avoids the second pass.

To be concrete, the array in order 1235647 has the first six comparisons go the same way as in 1234657, but it doesn't end up sorted in one pass.

Perhaps harry8 was thinking of the bubble sort implementation in the OP, which would indeed stop after one pass in these cases.

you look back and see if you will need a second swap and set your "need another pass" boolean that you named "swapped" accordingly.

The other reply thread is great and has a SmarterBubbleSort implementation -- it's important to note that the early stopping rule is an enhancement, not vanilla bubble sort (I had to learn both, maybe curricula these days jumps straight to the smarter version?), but even so it complicates the implementation and still isn't ever better than vanilla insertion sort.

Here is insertion sort

    void insertion_sort(int s[], int n) {
      int i, j;
      for (i = 1; i < n; i++) {
        for (j = i; j > 0 && s[j] < s[j-1]; j--) {
          swap(&s[j], &s[j-1]);
        }
      }
    }

You can even improve this further (some improvements have new names), however its base form is not in the class of bad algorithms to never use. Besides Bubble sort, Bogosort comes to mind. And there are of course nice algorithms to use if your data works for them, Radix sort comes to mind. Knowing your data is good advice, knowing never to use bubble sort is also good.

> Others have pointed out that bubble sort is great when your data is already mostly sorted

It really isn't, compared to insertion sort. https://users.cs.duke.edu/~ola/papers/bubble.pdf shows insertion sort performs 5x better. I also like Knuth's Quote in TAOCP: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"

> running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching

Name one sorting algorithm that doesn't involve purely running sequentially through contiguous memory.

I've seen all the O(n^2) worst case algorithms that reduce to O(n) on nearly sorted lists used, for example, in sweep and prune algorithms in computational geometry.

As a possibly more surprising example, readittwice posted this above: https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/...

I once used a bubble sort when I knew the typical array size would be 4. I think someone later replaced that code when the original assumption became outdated and we were sorting larger arrays.

For nearly sorted data, bubble sort is quite good. Simple implementation and near linear performance. Has my seal of approval.

Insertion sort is almost always better isn't it?

Bubble sort is also good for keeping a list close-enough-to-sorted with only small incremental costs. It was an old graphics engine trick to run just a few passes of bubblesort over your sorted triangles array before rendering each frame. Occasionally you'd get artifacts but generally it worked well enough and was fast.

Could be a small data set

Reply on news.ycombinator.com