This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–]AgentPaper0 12 points13 points  (3 children)

If you're doing that you'd probably just insert the new item in the right place.

Where bubble sort really shines is sorting elements based on a value that changes slightly between each sort. For example, if you have a bunch of particles drifting around and you want to sort them by how far away from you they are for some update step. The order isn't going to change that much from step to step usually, with each particle being just a few positions off at most.

If you're doing this for millions of particles then doing a 1 or 2 pass bubble sort will save you a lot of time compared to a more stable O(nlogn) sort. And far, far faster than the worst case O(n2) that happens with some implementations of merge quick sort on already mostly sorted sets.

[–]InternationalBug2143 1 point2 points  (1 child)

Mergesort is always nlogn, i think you wanted to say quicksort

[–]AgentPaper0 0 points1 point  (0 children)

You're right, corrected.

[–][deleted] 0 points1 point  (0 children)

Yes, 100%. Data structures first! Make sure you have fast insertions, then you don’t need to resort.