6 ms·

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

• davemp 9y ago
  Could be a small data set
• nothrabannosir 9y ago
  For nearly sorted data, bubble sort is quite good. Simple implementation and near linear performance. Has my seal of approval.
  • ufo 9y ago
    Insertion sort is almost always better isn't it?
  • taneq 9y ago
    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.
• santaclaus 9y ago
  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.
• kccqzy 9y ago
  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.
  • darethas 9y ago
    Last time I looked at the source for Java's dual pivot quicksort implementation, it used exactly this for 7 elements or fewer
    • failrate 9y ago
      Yes, and qsort does similar (different algorithms for different array sizes but the same function interface).
• saas_co_de 9y ago
  This is in a custom interpreter (used for teaching I think) https://github.com/code-dot-org/JS-Interpreter https://github.com/code-dot-org/JS-Interpreter
• harry8 9y ago
  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.
  • wilun 9y ago
    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.
    • harry8 9y ago
      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.
  • Jach 9y ago
    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_eng.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html (Bubble sort is not great when your data is almost sorted. Insertion sort is, though.)
• flukus 9y ago
  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.
  • islemaster 9y ago
    Actually, that's a fascinating part of the story. We run the entire test262 ECMAScript Conformance Suite (https://github.com/tc39/test262 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
• mark-r 9y ago
  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.
• Sean1708 9y ago
  As a possibly more surprising example, readittwice posted this above: https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/BubbleSort.h#L31 https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/...