3 ms·
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 y
by kragen 4y ago
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
- cozzyd 4y agoI'm sure it's possible to conceive of a pathological hardware architecture where bubble sort is faster than insertion sort on small inputs.
- saagarjha 4y agoI 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.