| ▲ | amilios 18 hours ago | |||||||
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. | ||||||||
| ||||||||
| ▲ | 17 hours ago | parent | prev [-] | |||||||
| [deleted] | ||||||||