• Industrial Automation Engineer (unregistered)

    Premature optimization is the programmer's worst enemy. There may exist a few valid circumstances under which it is reasonable to implement a bubble sort algorithm.

  • LZ79LRU (unregistered)

    This looks like the work of an expert beginner.

  • Sole Purpose Of Visit (unregistered)

    It doesn't seem to implement tail recursion, so, no, this isn't even a feasible bubble sort for lists of more than 255 elements.

  • (nodebb)

    This code comes from a senior web developer, who somehow never learned that JavaScript has a built-in sort function, that you can pass functions to it, that it's far more efficient than a bubble sort, and also why are you implementing a bubble sort.

    Far more to the point, why did this person implement a recursive bubble sort? (The standard bubble sort is two nested loops...)

  • TAR86 (unregistered) in reply to Steve_The_Cynic

    Exactly, they somehow made the space requirements worse ...

  • TAR86 (unregistered) in reply to Industrial Automation Engineer

    Not-invented-here is not one of them.

  • (nodebb)

    Something that irks me here:

    var cmp = (direction == 'ASC' ? function(a,b){return a < b;} : function(a,b){return a > b;});

    No handling of invalid input. Someone is going to write 'asc' and be surprised by the results. That someone most likely being the original developer, since hopefully nobody else uses this code.

    But assuming the function itself to be useful, better would be

    const cmp = direction == 'ASC'  ? function(a, b){ return a < b; }
          : direction == 'DESC' ? function(a, b){ return a > b; }
          : throw_invalid_value(direction);

    Ternaries add insult to injury, as raise / throw constructs are usually statements, and thus cannot be used inside ternaries. Hence the throw_invalid_value auxiliary function. By contrast, block-level conditionals have the issue, that they don't guarantee that a value is assigned. Which is pretty much the main reason I use ternaries at all.

    Handling of invalid values is especially important for making the implementation robust with regard to future implementations. Let's say the actually useful function is such, that extending it to allow

    direction == 'SIDEWAYS'

    makes sense. If somewhere in the logic the form

    direction == 'ASC' ? A : B;

    was used, and the expression is missed during extending, the function will silently do the wrong thing instead of reporting an error. Thorough testing would catch this still, but the likeliness of missing the bug is increased.

  • WTFGuy (unregistered)

    Look at the bright side. After the first pass through the loop when the dev interrogates mods to decide whether to recurse, they eschewed the clearer formulation of if((mods % 1 != 0) == !false) and they even put brackets around the 'true' branch even though it was just one statement. Talk about careful future-proofing!

    In a slightly more serious vein, I think every bubble sort I've ever seen coded compared the current indexed entry with the one immediately below. This one chooses start at the second entry and compare with the one above. Which triggers my spidy-sense (without actually having penciled it out) that the sense of their comparison operators is backwards versus the indices it's being applied to. With the result that "ASC" gives a descending sort & vice versa. Again I haven't actually checked, but this is a formulation that at first glance makes my head go "yeah, no, yeah?, no? , yeah!, no!, Yeah??, No!!". That is not a good feeling to trigger in your maintenance team.

    The bit R3D3 objects to with the text "ASC" as the error-prone direction switch totally makes me think this code is reading the attributes of some HTML element. And generated HTML at that.

  • (nodebb)

    I remember my amazement when I finally learned about quicksort as a freshman undergrad.

  • Bill Sorensen (github) in reply to LZ79LRU

    For anyone who hasn't read it: https://daedtech.com/how-developers-stop-learning-rise-of-the-expert-beginner/

  • holy shit now I'm actually commenting here... (unregistered)

    I've actually implemented a bubble sort from scratch once. For generating a diff. To be sent in an email. In PL/SQL 🤮

    I'd have gone for a quicksort, but the language doesn't have recursion, among other things. It was an internal tool I maintained as an intern about 10 years ago and I'm like 99% sure they're still running that atrocity.

  • Jonathan (unregistered)

    Must be my Perl experience, where cmp is the string comparison function, which returns the usual -1/0/1 for less than / equals / greater than. So I missed that they decided to name their boolean-returning "is less/greater that" function cmp. So I thought that this function would spend eternity switching the first two non-equal value back and forth.

  • (nodebb)

    I will second the comment about there being reasons to implement it--I've done so when dealing with single-digit values of n with data not in a structure that could be passed to the built-in sort as is. Those are very, very rare cases, though.

  • NoLand (unregistered)

    At this point in all things JS, I pretty much assumed that I must have missed out on the next amazing ES2024 feature when reading

    list[i].column

    The universe be thanked, this is still an error. But I pretty much expect something like this to emerge soon.

    Maybe better (as in more distinctively) expressed as a back-arrow property?

    list[i]<-column

    No, no, Living Standards, you haven't read this! ;-)

  • MRAB (unregistered) in reply to WTFGuy

    'cmp' will be checking whether list[i] < list[i - 1] when direction == 'ASC', so it'll swap them if list[i] < list[i - 1], which is correct, although it is confusing, IMHO.

  • JimL (unregistered)

    I once implemented a bubble sort because it was literally 2 orders of magnitude faster than the built-in sort. Special case, a large list of transactions that was all alreadt sorted except for a few transcations added at the end that typically would not move very far. Bubble sort ran up the list of already sorted transactions in linear time, then did an inefficient sort on a very small set.

    Choose your algorithms wisely

  • Andrew Klossner (unregistered)

    This isn't even a proper bubble sort. The first iteration should look at all elements; the second looks at all but the last; the third looks at all but the last two. This code takes twice as long as necessary.

    In the first three examples from a quick Google of "bubble sort", each has this same problem. Nobody reads Knuth anymore.

  • Worf (unregistered) in reply to JimL

    If you have a mostly sorted list and you want to insert something to it, you should use insertion sort. Adding items becomes linear time.

    There is no real reason to do bubble sort, unless you have a well controlled list with small n. I mean, if you're sorting say, a list of 10 items, using bubble sort is probably easier if you just need to do it right then and there. But that's only if n cannot change.

  • TCOZ (unregistered)

    Nobody mentions selection sort, which is even simpler to code and more efficient than bubble sort

  • MaxiTB (unregistered) in reply to Steve_The_Cynic

    Boredom or avoid meaningful tasks like fixing bugs or doing code reviews. You'd be surprised how often people pretend being busy just to avoid being productive. Must be a human thing.

  • (nodebb)

    I always found writing any sort algorithm an extremely dull and boring task. Even and particularly in CS. I'd rather read the doc of whatever toolkit/language I'm using to find their built-in sort rather than implement one myself. Built-in one not good enough? Time to find a better library to import, there's gotta be one somewhere. Anything but write the dull thing.

  • LZ79LRU (unregistered)

    There is an easy fix for these situations. And one that I've sadly yet to convince any manager to allow me to implement.

    When ever someone rolls their own version of a built in function have them prove mathematically that their version is superior to the builtin. And no, testing does not count. I want a formal proof on paper.

  • (nodebb)

    I coded up a bubble sort once, when I was a mathematics postgrad and didn't know better (having not done any CS past first year uni, which was really just an intro to programming and didn't contain much that was new to me). My advisor pulled me up on it and explained mergesort to me (I was dealing with large linked lists) and I coded that up instead, with very noticeable results.

    No built ins here, this was Turbo Pascal. Hand rolled everything :)

  • Dariusz Jackowski (unregistered)
    Comment held for moderation.

Leave a comment on “Bubbled to the Top”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article