When would you ever want bubblesort?
buttondown.email
When would you ever want bubblesort?
1–10 of 70 posts
Re: When would you ever want bubblesort?
#2I've written a sort perhaps a handful of times in the last 40 years. Each of those was a bubble sort. I was nearly-always sorting These were rare cases where I didn't have a sort algorithm in a library -- perhaps because I needed to pass in a comparator that wasn't easily supported in the language. So I banged out whatever was easiest to get me moving on to the actual problem. If the sort became a noticeable part of the running time, I'd deal with that when I had performance numbers.
Bubble sort was easy to remember and quick to bang out. For all I know I really was writing an insertion sort; all O(n^2) sorts look pretty much the same.
I haven't written any sorts at all in well over a decade, since all languages have substantial support. If I'm writing a sort, something has gone very wrong.
Re: When would you ever want bubblesort?
#3Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted.
You do the compare-and-swap when you're iterating over the objects to do some other render pass, so it adds almost nothing to the CPU time.
Re: When would you ever want bubblesort?
#4Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
Re: When would you ever want bubblesort?
#5Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted. You do the compare-and-swap when you're iterating over the objects to do some other render pass, so it adds almost nothing to the CPU time.
> so it adds almost nothing to the CPU time.
If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant?
Re: When would you ever want bubblesort?
#6It would likely be handy during your exams in CS 101.
Re: When would you ever want bubblesort?
#7Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted. You do the compare-and-swap when you're iterating over the objects to do some other render pass, so it adds almost nothing to the CPU time.
> so it adds almost nothing to the CPU time. If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad . I'm assuming that's not what you meant?
> > so it adds almost nothing to the CPU time.
> If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant?
I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
Re: When would you ever want bubblesort?
#8Earlier quoted context omitted.
> so it adds almost nothing to the CPU time. If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad . I'm assuming that's not what you meant?
> > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
>> You do the compare-and-swap when you're iterating over the objects to do some other render pass
OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness.
The idea of two threads concurrently bubblesorting the same array with CAS is hilarious and intriguing. On x86 the double-wide CAS requires double wide alignment so I guess it couldn't actually work without extra trouble...
Re: When would you ever want bubblesort?
#9It would likely be handy during your exams in CS 101.
This blog post would make a fantastic addition to the sorting part of a CS101.
Re: When would you ever want bubblesort?
#10Earlier quoted context omitted.
> > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
>> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two th…
No, there was no mention of concurrency. As I understsand it, OP was describing a "render pass" that looked like this:
for (int i = 0; i for (int i = 0; i obj[i+1]) swap(&obj[i], &obj[i+1])
// do some rendering or something
}