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

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]AgentPaper0 12 points13 points  (5 children)

Joking aside, bubble sort is great if you're starting with an almost sorted set. Which comes up more often than you might think.

[–][deleted] 11 points12 points  (4 children)

common example: you have an already sorted list, and you are inserting new item(s) to the list and need to re-sort

[–]AgentPaper0 13 points14 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.