The article, and many of the responses, are hinting at the fact that bubblesort is an example of an anytime algorithm. This is a wide class of algorithms which provide a correct answer after some amount of time, but provide an increasingly good answer in increasing amounts of time short of the completion time. This is a super valuable property for real time systems (and many of the comments about games and animations discuss that). The paper that introduced me to the category is "Anytime Dynamic A*" [0], and I think it's both a good paper and a good algorithm to know.

[0] https://cdn.aaai.org/ICAPS/2005/ICAPS05-027.pdf

▲

jononor 10 hours ago | parent | next [-]

Anytime algorithms are great for robotics planning, for example. A plan does not have to be perfect to be useful, especially when it can be refined further in the next timestep. And the robot cannot act out the plan instantaneously, so by the time one is close to the point where a non-ideal segment would be, one has had many timesteps to refine/optimize it. But robot could start moving right away.

▲

hwayne 17 hours ago | parent | prev | next [-]

Thanks for sharing the general term! I didn't know about it.

▲

amilios 18 hours ago | parent | prev [-]

Am I missing something? If the algorithm is interrupted, the list will not be sorted. How exactly does it fit the criteria of an anytime algo?

▲

addaon 18 hours ago | parent | next [-]

An anytime algorithm monotonically improves some evaluation metric. For a sort, the evaluation metric is usually the number of inversions in the list. At completion, there will be zero inversions. If at time 0 there are N inversions, then at time 0 < t < completion time there will be ≤ N inversions; that is, the list is "more sorted" than it was before. As the various examples about games and animation elsewhere in the comments show, this can be interpreted as "somewhat smoothly moving towards sorted over time," which is an (occasionally) ((rarely)) useful property.

▲

Pannoniae 18 hours ago | parent | prev | next [-]

Okay, but it gives you a mostly good answer! Unlike many other sorts where if you interrupt it before the last step, you get total nonsense.

It's basically asymptotically approacting the correct (sorted) list instead of shuffling the list in weird ways until it's all magically correct in the end.

	▲	NooneAtAll3 13 hours ago \| parent [-]
		> Unlike many other sorts where if you interrupt it before the last step, you get total nonsense. which ones you have in mind? and doesn't "nonsense" depend on scoring criteria? selection sort would give you sorted beginning, cocktail shaker would have sorted both ends quick sort would give vast ranges separation ("small values on one side, big on the other"), and block-merge algorithms create sorted subarrays in my view those qualities are much more useful for partial state than "number of pairs of elements out of order" metric which smells of CS-complexity talk

▲

17 hours ago | parent | prev [-]

[deleted]