Ah, my error. If you want to see what I was thinking, imagine I'd pulled the "fuller" quote 'insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life'.
The point of my comment was just that the complexity of an algorithm as analyzed under one set of primitive operations doesn't automatically translate into another set of operations, even when at a high level it's the same algorithm. It is dangerous to study CS, learn that selection sort (on arrays, on a computer well described by a C-like language) is O(n^2), and then conclude that selection sort (in any context) is inherently O(n^2). That may be true of selection sort in specific -- it's difficult to avoid concluding that the selection step is roughly ϴ(n), and must always run n times -- but the reasoning is faulty, and won't transfer to other algorithms.
This makes more sense now. The full relevant part of my comment:
> GP's description is selection sort, not insertion sort, which still requires
The double-comma construction is meant to be read as an aside. Probably would've been clearer using parens:
> GP's description is selection sort (not insertion sort), which still requires
I often use the commas though because I'm mentally verbalizing what I type and commas have a pause that makes the aside work even aloud, while it's not clear how you'd verbalize parens.
The point of my comment was just that the complexity of an algorithm as analyzed under one set of primitive operations doesn't automatically translate into another set of operations, even when at a high level it's the same algorithm. It is dangerous to study CS, learn that selection sort (on arrays, on a computer well described by a C-like language) is O(n^2), and then conclude that selection sort (in any context) is inherently O(n^2). That may be true of selection sort in specific -- it's difficult to avoid concluding that the selection step is roughly ϴ(n), and must always run n times -- but the reasoning is faulty, and won't transfer to other algorithms.