4 ms·
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
by Animats 3y ago
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.
- phkahler 3y agoFunny, 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!
- indigo945 3y ago> Most objects aren't moving that much. [citation needed]. Even just one object moving from one end of an axis to the other end would incur catastrophic slowdown, and depending on what you are simulating, this might occur regularly (for example, consider teleporters in a video game). When that happens, you incur the full O(n^2) iterations until the axis is sorted again, even though only one object is actually out of order. 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.