3 ms·

I would trust myself more to implement bubble sort than to implement insertion sort. Not that I couldn't implement insertion sort, I've done it before, but if I

• kragen 3y ago
  my subjective experience writing the above comment as documented in https://news.ycombinator.com/item?id=37206998 https://news.ycombinator.com/item?id=37206998 may be a relevant data point; note that the insertion-sort code is subtly buggy, and the bubble-sort code isn't
• arthur2e5 3y ago
  Personally I find insertion easier to reason about once you internalized the idea of a memmove.
  • mort96 3y ago
    To me, it seems like bubble sort is almost inherently easier to reason about. One iteration of bubble sort is: find two elements in the wrong order and swap them. One iteration of insertion sort is: find an element out of order, then find the location in the array where it should've been, then move all the items between those two slots one slot ahead, then insert the out-of-order element into the now free slot where it belongs. Admittedly, insertion sort is pretty intuitive, since it reflects more or less how a human would instinctively try to sort a list; take an out-of-order element and move it to where it belongs. But when translated to code, I think it's very hard to beat "find two items in the wrong order and swap them".
    • hasmanean 3y ago
      A lot of people look at sorting algorithms with the mental model of a 1970s era PDP-8. They analyze scalar instructions as if they are being executed sequentially. Once you admit superscalar execution (multiple loadstore pipes), out of order execution and caches into the picture ( as well as the possibility of almost sorted arrays as input) the picture is never as simple. That said, I’m curious whether insertion sort is categorically better than bubble sort. I thought they might have been equivalent for the almost sorted case. I’ve heard both sides argued on this thread.
      • masklinn 3y ago
        Per the wiki: > Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position In fact it’s often a sub-sort of hybrid sorts, like timsort: > If a run is smaller than this minimum run size, insertion sort is used to add more elements to the run until the minimum run size is reached.
        • kragen 3y ago
          i think that adaptive time complexity bound holds for both bubble sort with early exit and insertion sort
      • kragen 3y ago
        the vast majority of computers still aren't superscalar, much less ooo; for every i7 there are 100 cortex-m0+s, which don't even have caches. gpus aren't superscalar or ooo either, just heavily multithreaded, simt, and simd even if insertion sort reliably beats bubble sort on your ssd ftl chip and your wristwatch, though, it seems like there are cases on modern high-performance hardware where insertion sort is worse than bubble sort (cf. https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html#fallback-for-sorting-short-arrays https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...) which is very surprising to me
• scythe 3y ago
  Pratt–Shell is only mildly more complex than insertion sort and gives a good worst-case performance O(n log(n)^2). It may have a place sometimes.
• eru 3y ago
  If you find yourself having to re-implement a sorting algorithm ad-hoc, you are probably using the wrong language. (Especially these days.)
  • kstrauser 3y ago
    ...or you're implementing a kernel and don't have full access to a libc.
    • eru 3y ago
      Who says you have to use libc? Eg Rust has no-std crates that you can use even if you can't use the standard library.
  • mort96 3y ago
    What language should they have used instead of C? And given that C's stdlib has a quicksort function, how would using a different language have helped?
    • eru 3y ago
      Back then C might have been the best bet.
  • kragen 3y ago
    i think it's pretty common for a specialized reimplementation of a standard library type or function to outperform it by an order of magnitude or so in some particular case. chris wellons gave an excellent example of this with hashing in golang in https://nullprogram.com/blog/2023/06/26/ https://nullprogram.com/blog/2023/06/26/ commonly (as in wellons's post about the two-sum problem) there's a variation on the standard algorithm that can help significantly, but which the standard library function doesn't have an option for also i think the cost of reimplementing simple 'algorithms from the book' like insertion sort or even quicksort is pretty low; as you saw in my comment above, insertion sort is six lines of code and only moderately bug-prone. we aren't talking about fibonacci heaps or red-black trees or fm-indexes or rader's algorithm or something. the cost is low enough that it's easy to justify in a lot of cases
• donkeybeer 3y ago
  I trust myself most to implement selection sort, its the most intuitive to me: just keep finding the next smallest element in the array and place it in its position. I can never remember the loop bounds of bubble sort, always have to look it up.
• Gibbon1 3y ago
  I just remember something from basic math. Exponential curve < linear for small values. That said a lot of time I have small arrays of objects. Instead of keeping them sorted I just grind through them to find the next largest value. That tends to be hard to get wrong.
  • Thiez 3y ago
    Exponential can be better than linear for small n depending on your constant factors, but it's never a given. E.g. `2n` < `10^n + 5` for all n.