Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When would you ever want bubblesort?

buttondown.email

Post reply on HN
Print view View original

11–20 of 70 posts

Re: When would you ever want bubblesort?

#11

Post by pengaru »

jcalvinowens wrote: post #8
pengaru wrote: post #7

Earlier 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…

> OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents?

No. I'm not OP, but 99% certain this is not the case.

Re: When would you ever want bubblesort?

#12

Post by jcalvinowens »

NobodyNada wrote: post #10
jcalvinowens wrote: post #8

Earlier quoted context omitted.

>> 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 And adding a "compare and swap" to the loop: one step of a bubble sort, to keep the objects "mostly sorted": for (int i = 0; i obj[i+1]) swap(&obj[i], &obj[i+1]) // do some rendering or something } Thus, "do[ing] the compare-and-swap when you're iterating over the objects to do some…

I explained another way to interpret what OP said. Your way is boring and uninteresting: this is a forum for discussion, so I picked the more interesting way :)

Re: When would you ever want bubblesort?

#13

Post by JohnFen »

jfengel wrote: post #2

I'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…

> I was nearly-always sorting In my opinion, a bubble sort is a solid choice for that sort of use case.

Re: When would you ever want bubblesort?

#15

Post by Animats »

Bubble sorts are useful in broad-phase collision detection. Each object has an axis-aligned bounding box, and you want to sort those by X, Y, and Z values, then check for overlap in all dimensions. Only if the bounding boxes overlap in all three dimensions do you have to check the object pair's detailed geometry.

Most objects aren't moving that much. The lists are thus almost in order. So running a bubble sort on each axis to check the ordering is not much worse than O(N).

Startup has a transient. The very first sort will be O(N^2). If the number of objects is large enough it may be worthwhile to do something different at startup.

Re: When would you ever want bubblesort?

#16

Post by harry8 »

Bubble sort is just fantastic to wind up arrogant algo-nerd snobs because you can bust it out for anything that is likely to be already sorted or nearly so and it dominates. Algo-nerd snobs rarely seem to take into account that knowledge and understanding of the input is the most crucial part.

Do it in job interviews only if you've already decided you're unlikely to want to work there and be sure to be smiling and humble as you demonstrate this to their peers, noting that the pure forms of the algo, selection sort is arguably better (Knuth!) but this is unlikely to be an interesting practical concern and totally dwarfed compared to readability of the code.

Re: When would you ever want bubblesort?

#18

Post by phkahler »

aappleby wrote: post #3

Can 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.

>> bubble sort in a production game engine to keep transparent objects mostly sorted.

A single pass of bubble sort per frame is often enough to keep things in order. And if something glitches because it takes 2 passes it's just a single frame glitch!

Re: When would you ever want bubblesort?

#19

Post by phkahler »

Animats wrote: post #15

Bubble sorts are useful in broad-phase collision detection. Each object has an axis-aligned bounding box, and you want to sort those by X, Y, and Z values, then check for overlap in all dimensions. Only if the bounding boxes overlap in all three dimensions do you have to check the object pair's detailed geometry. Most objects aren't moving that much. The lists are thus almost in order. So running a bubble sort on eac…

Funny, if I were doing that I'd use a spatial index using oct-trees since I have a fairly optimized one. You find all potential overlaps in O(logN), But to check them all would be O(NlogN). So by your approach it looks like bubble sort wins!
Post reply on HN