5 ms·
yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort for (size_t i = 0; i < n; i++) { for (size_t j
by kragen 3y ago
yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort
for (size_t i = 0; i < n; i++) {
for (size_t j = 1; j < n - i; j++) {
if (a[j-1] > a[j]) {
item_t tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
when you could use insertion sort
for (size_t i = 1; i < n; i++) {
for (size_t j = i; j > 0; j--) {
item_t tmp = a[j];
if (tmp > a[j-1]) break;
a[j] = a[j-1];
a[j-1] = tmp;
}
}
which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases
(above code only minimally tested: https://godbolt.org/z/43dqz9Gq8 https://godbolt.org/z/43dqz9Gq8)
this is not much of a criticism of freebsd; if you polished your codebase until there was nothing stupid in it, you'd never ship anything. freebsd's code quality is quite high, but probably we can all agree that this was stupid
of course it wouldn't be nearly as fast as mergesort on large inputs, but mergesort is more complicated
(also mergesort is slower on small inputs than insertion sort or bubble sort, but in the case where you're only sorting something once at startup time, that probably isn't important. it might matter if you were sorting a million lists of ten items or something)
- SomeoneFromCA 3y agoNeither of your code snippets are working, or are an actual implementation of bubble sort. Since what insertion sort is faster that bubble sort on sorted data?
- kragen 3y agoi tested both of them on some input data and they both sorted it correctly, though of course they could contain bugs (if so i'd be grateful if you pointed them out) admittedly i probably added the godbolt link showing this after you wrote your comment perhaps you can elaborate; i couldn't understand your last sentence or why you think the bubblesort function above doesn't bubble-sort
- SomeoneFromCA 3y agoBecause it misses a crucial step, early exit if there were no swaps. This way it would be extremely efficient in case of already sorted data. You should probably check wikipedia page. Here: https://en.wikipedia.org/wiki/Bubble_sort https://en.wikipedia.org/wiki/Bubble_sort.
- jazzyjackson 3y agomeh, an optimization, hardly "not working"
- SomeoneFromCA 3y agoIt is not "an optimization", it is in the definition of Bubble Sort. What you have written is not a bubble sort, and therefore, by the fact of being not a bubble sort, is not a working bubble sort.
- thaumasiotes 3y agoThat's not part of the definition of bubble sort. It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.) The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.
- SomeoneFromCA 3y agoIt is in the definition in Wikipedia and most other sources I have checked. All the implementations I have seen so far, check if any swaps have happened, and stop if they have not.
- Closi 3y agoI think we have different definitions of stupid - the original implementation was perfectly fine for the time and requirements it was written for.
- winternewt 3y agoBut it could have been better for no additional effort. Doing something worse when the better option is just as easy suggests incompetence.
- kragen 3y agoi wouldn't go so far as to say incompetence even the best of us do stupid things sometimes
- Closi 3y agoYeah, but it was working. And maybe it wasn't 'no additional effort' because they were more confident with quickly writing a bubble sort.
- jazzyjackson 3y agoDoing something better when you already have something that works suggests a lack of time management xP
- winternewt 3y agoAt some point there was no sort, and then somebody implemented the sort. That's the point in time that I'm talking about.
- throwawaaarrgh 3y agoNever underestimate incompetence. It usually succeeds despite itself. It also could have been apathy: knowing there was a better solution and just not caring what was implemented. I feel like this is more common than incompetence, especially in larger projects or organizations. Nature tends to take the path of least resistance.
- 3y ago
- gpvos 3y ago> above code only minimally tested There you have your problem: any programmer can write a bubble sort while half asleep and inebriated at the same time, but for an insertion sort you actually have to think a little. There's much more chance of errors.
- kragen 3y agoi'm not sure; i made a few mistakes in each of them as i was writing them, but they were both working by the time i first tested them. i do feel like the insertion sort was maybe a little more challenging? edited to add: someonefromca spotted a bug in the insertion sort; where it says if (tmp > a[j-1]) break; it should say if (tmp >= a[j-1]) break; which is both a performance bug and also breaks the stability property the algorithm otherwise has this is some evidence in favor of your point that insertion sort is more error-prone; even if i could have made the same error in the bubble sort, i didn't, and possibly that was because the rest of the algorithm required less mental effort?
- abecedarius 3y agofwiw that comparison was where I went "wait, is that right?" in my reading. Maybe a fair judge of mental difficulty would say "you gotta write at least the loop invariant" (termination being too pedantically obvious) -- though admittedly I leave it out more than I used to. When I was introduced to sorting as a new programmer, via bubblesort, I thought "why that way?" and came up with selection sort as a method that made more obvious sense. It seems to me like bubblesort's alleged intuitiveness is post hoc from the shortness of the code in terms of all-ascending for-next loops -- the intuitive reason it worked was just that the inner loop did move the next max into place just like selection sort, but with extra swaps along the way.
- aristophenes 3y agoYou should edit the code in your original comment, someone is bound to copy paste the code somewhere…
- 3y ago
- mort96 3y agoI 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 was in a context where I had to implement a quick and dirty ad-hoc sorting algorithm which I thought would only ever have to sort a few items, I would probably go with bubble sort. If I suspected at all that the algorithms would have to sort a decent number of items, I wouldn't consider using an O(n^2) sort at all and would take the time to find a good implementation of (or implement) one of the O(n log(n)) algorithms.
- kragen 3y agomy 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 agoPersonally I find insertion easier to reason about once you internalized the idea of a memmove.
- mort96 3y agoTo 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 agoA 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.
- janc_ 3y agoWhen this code was written there was no "amd64" though, so you would have to compare them on the original/typical hardware from then?
- kqr 3y ago> there is never a good reason to use bubble sort I used to believe this but then a friend pointed out a real use case for bubble sort: when you have an array that is always mostly sorted, and real-time performance is more important than perfectly correct ordering. Then running one pass of bubble sort each cycle around the main loop is somewhat satisfyingly ideal. One pass of insertion sort would be too expensive, and bubble sort is guaranteed to make incremental progress each pass. This is sort of like how a linked list is never the right solution... unless it's one of those cases where intrusive linked lists are ideal. Except while intrusive linked lists intrude in space, intrusive bubble sort kind of intrudes in time.
- ramses0 3y agoI remember a website that "raced" different sorting algorithms visually but I don't remember which website, or which oddball algorithm that stood out to me as being especially good for "continuous partial ordering". Most sorts are designed to "really sort something", however I'm very interested in eg: ranking preferences of movies, and in cases like that there may never be "the one true ordering" ... however the mechanism for getting things "closer to sorted" is incredibly close to the mechanism you mentioned: multiple passes, and continual, incremental progress. My imaginary GUI for interactive sorting in this manner is something like starting with a few "A vs. B" of a generally accepted "top 10/100 vs generic v pretty bad", and then morph to a "drag this new movie in between a few other movies either above, between, or below" There are sorting algorithms for computers (eg: compare + swap), but fewer sorting algorithms for humans (eg: bucket sort / postman's sort - https://en.wikipedia.org/wiki/Bucket_sort#Postman's_sort https://en.wikipedia.org/wiki/Bucket_sort#Postman's_sort ) which can take advantage of "not just compare and swap" to get things "close to correct" quicker.
- kragen 3y agomaybe you could use a multi-pivot quicksort or an insertion sort where you drag and drop each new item into any position in an already-sorted subset
- 3y ago
- eru 3y agoI guess the bigger problem is using a language like C that's almost incapable of providing useful libraries. So everyone is re-implementing everything from scratch all the time.
- yehaaa 3y agoqsort is part of the ISO C90 standard though.
- emmelaich 3y agoWhy didn't they just use qsort, which is in libc?
- deleted 3y ago[deleted]
- erk__ 3y agoFor reference the original code was a bit more complicated than just sorting integers which may also have been a reason for the choice. /* * Perform a bubble sort of the system initialization objects by * their subsystem (primary key) and order (secondary key). * * Since some things care about execution order, this is the * operation which ensures continued function. */ for( sipp = (struct sysinit **)sysinit_set.ls_items; *sipp; sipp++) { for( xipp = sipp + 1; *xipp; xipp++) { if( (*sipp)->subsystem < (*xipp)->subsystem || ( (*sipp)->subsystem == (*xipp)->subsystem && (*sipp)->order < (*xipp)->order)) continue; /* skip*/ save = *sipp; *sipp = *xipp; *xipp = save; } } https://github.com/freebsd/freebsd-src/blob/2b14f991e64ebe31ca31a1a41237061c22a753d0/sys/kern/init_main.c#L149-L166 https://github.com/freebsd/freebsd-src/blob/2b14f991e64ebe31...
- kragen 3y agothis is actually selection sort; the comment is wrong
- erk__ 3y agoThat is a pretty interesting observation, I don't think I would have spotted that, especially given everyone have been saying it was bubblesort.
- kragen 3y agoi probably wouldn't have spotted it without trying to figure out which variant of bubblesort it was: counting up? counting down? does it adjust the inner loop size? early exit? selection sort has the potential advantage for things that are larger than your key that it can avoid copying the entire item, just doing a single swap at the end of the inner loop, but it's not implemented that way here. that would have looked like this size_t m = 0; register unsigned int subsystem = (*sipp)->subsystem; register unsigned int order = (*sipp)->order; for( xipp = sipp + 1; *xipp; xipp++) { register unsigned int newsubsystem = (*xipp)->subsystem; register unsigned int neworder = (*xipp)->order; if( subsystem < newsubsystem || (subsystem == newsubsystem && order < neworder)) continue; /* skip*/ m = xipp - sipp; subsystem = newsubsystem; order = neworder; /* enjoy the sorting */ } save = sipp[0]; sipp[0] = sipp[m]; sipp[m] = save; on the other hand if you were going to put effort into optimizing this you probably would have used mergesort or something
- dkbrk 3y ago> there is never a good reason to use bubble sort Not true. Bubble sort is excellent for sorting very small arrays. See "Hoare’s Rebuttal and Bubble Sort’s Comeback (2020)" under "Fallback for sorting short arrays" and the performance results presented therein [0]. Discussion [1]. [0]: 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... [1]: https://news.ycombinator.com/item?id=23363165 https://news.ycombinator.com/item?id=23363165
- kragen 3y agoremarkable, thank you all of the bubble sorts i tried compiling in this thread ended up being compiled to code with either conditional branches or (on arm thumb-2) a couple of conditionalized stores. but conditional stores don't require a pipeline flush, and it is of course perfectly correct that insertion sort depends on its inner loop having an unpredictable branch to get better performance on almost-sorted data, which bubble sort does not
- kragen 3y agoafter thinking about it some more, i was skeptical that this really implements bubble sort, but after trying it, it does python version of the inner loop max_ = arr[0] for j in range(1, i): y = arr[j] arr[j - 1] = min(max_, y) max_ = max(max_, y) arr[i - 1] = max_
- basementcat 3y agoIf you find yourself sorting small arrays, may I suggest a sorting network? https://en.m.wikipedia.org/wiki/Sorting_network https://en.m.wikipedia.org/wiki/Sorting_network
- michaelcampbell 3y agoOne of the truths I've come across over my years is that almost without fail whenever code is mentioned, someone will come across to show how it could be done better. I haven't seen it in this thread, yet, but generally there will be someone who will maximize how badly it could also be done, usually using Java and invoking "Enterprise coding" memes.