Decreasing the Number of Memory Accesses 1/2

Re:Decreasing the Number of Memory Accesses 1/2 by kragen on Friday March 31, 2023 @09:02AM (#35386496)

bubble sort is never as good as insertion sort, not even for almost-sorted data or for six elements

bubble sort is never the way to go

generally in the case you're describing, where you have a few thousand elements that need to stay sorted in the face of insertions, a b-tree would be a better choice, or failing that, merge in a batch of updates whenever the update file gets big enough

either of these can beat bubble sort or insertion sort in this situation by more than an order of magnitude

[ Parent | on HN ]

Re:Decreasing the Number of Memory Accesses 1/2 by cozzyd on Friday March 31, 2023 @11:25AM (#35388522)

I'm sure it's possible to conceive of a pathological hardware architecture where bubble sort is faster than insertion sort on small inputs.

[ Parent | on HN ]

Re:Decreasing the Number of Memory Accesses 1/2 by saagarjha on Friday March 31, 2023 @11:55AM (#35389004)

I mean sure, you can always come up with a processor that tries to detect insertion sort and makes it slow while it has hardware acceleration for bubble sort. That doesn't make it a very useful model, though.

[ Parent | on HN ]