alt Hacker NewsThe 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.
Replies
Thanks for sharing the general term! I didn't know about it.
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?
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.