[deleted]
When would you ever want bubblesort?
51–60 of 70 posts
Re: When would you ever want bubblesort?
#52> On some very particular hardwares bubblesort stills ends up better, like in this NVIDIA study, but you probably don't have that hardware. The author might have misunderstood the hardware in question and the reasons why bubble sort works well here. You probably do have applicable hardware; it’s any GPU. The bubble sort wasn’t running on ray tracing hardware, it was just CUDA code. The reason bubble sort works well i…
In the other words, you are sorting lots of equally-sized slabs at once, and you can do the same operation to each slab efficiently. Algorithms with no data-dependent control flow would be optimal in this situation, and bubblesort is one of them. But there are even better algorithms, I think shellsort with a fixed gap sequence (since the slab size is known in advance) could've been a good alternative. On the other hands, if you are sorting a single huge list, you need a parallel sorting algorithm like bitonic sort.
Re: When would you ever want bubblesort?
#53Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
Unless you have a thousand of sorting routines it wouldn't matter much. And compilers generally produce a much larger code than actually possible, you can implement bubblesort in 16 bytes of x86-32 assembly [1] for example. [1] https://gist.github.com/jibsen/8afc36995aadb896b649
It matters a great deal if you have 1KB of flash to fit the whole firmware in :)
Re: When would you ever want bubblesort?
#54Earlier quoted context omitted.
Unless you have a thousand of sorting routines it wouldn't matter much. And compilers generally produce a much larger code than actually possible, you can implement bubblesort in 16 bytes of x86-32 assembly [1] for example. [1] https://gist.github.com/jibsen/8afc36995aadb896b649
It matters a great deal if you have 1KB of flash to fit the whole firmware in :)
Oh, if you are already writing an assembly my comment doesn't apply ;-)
Re: When would you ever want bubblesort?
#55The game dev example is really cool. I've never encountered a situation where "more sorted" is better for performance but completely sorted doesn't really matter (or maybe I have, but didn't know it).
When you read Knuth's The Art of Computer Programming he challenges you to come up with your own sorting algorithm. I feel really fortunate that I was able to do this without knowing any algorithms already. I came up with bubblesort. I think it was the intuition of thinking about it becoming "more sorted" on each pass that led me there.
Re: When would you ever want bubblesort?
#56Bubble sort's true complexity is O(n+d) where d is the number of inversions in the array. So if an array is almost sorted better to use bubble sort.
Re: When would you ever want bubblesort?
#57Bubble 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…
> Most objects aren't moving that much.
There are certainly simulations where this approach is fine (if you can be absolutely confident that no object ever "skips" around, like when you're running a simulation that is configured with an explicit upper bound on velocity), but I think that this still requires this warning label.
Re: When would you ever want bubblesort?
#58I'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.
For <4 elements, a pure "if" / "else" implementation would probably be optimal.
Re: When would you ever want bubblesort?
#59[dead]
Re: When would you ever want bubblesort?
#60I used bubble sort for sorting an HTML table, because, as others say, it is easy to write quickly. It stayed that way until I asked gpt to rewrite it for me.