If swaps are the only thing you are counting, selection sort is O(n).
I can't come up with a reasonable way to consider insertion sort O(n) though.
I can't come up with a reasonable way to consider insertion sort O(n) though.
And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :)
"In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm." [1] We shouldn't be confusing people that actually want to learn about this stuff.
That is an excellent phrase.
> We shouldn't be confusing people that actually want to learn about this stuff.
I definitely agree that Selection sort should definitely not be described as O(n) to beginners. I was just pointing out a subtly. In the strange case where memory writes are much more expensive than reads or comparisons, it is correct to say the Selection sort takes O(n) time.
If comparisons are a fixed, non-zero cost, and assignments are a fixed, non-zero cost, then the comparisons in your selection sort will always overwhelm the assignments, and I can tell you at exactly which input size.
https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a...
Good one, but you probably meant Satyr (or Faun as Romans called it)
https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/...
If memory writes are expensive (relative to reads and comparisons), selection sort is much better than insertion and bubble sort. Which is not something I had considered before trying to defend the post from the original comment.
> Insertion and selection require O(n^2) moves or compares respectively (or, n log(n) with use of data structures). As it stands, the page is pretty as heck but teaching a misconception.
I am definitely aware of the runtime of the sorting algorithms discussed. I have written about all of them [0]. Originally, I was going to agree and write about how it was a concerning misconception, but at least in the case of selection sort there is some (albeit small) merit to considering selection sort as O(n).
Though given that I cannot come up with a defense for insertion sort it is likely the author doesn't understand the time complexity of the sorting algorithms presented.
[0]: http://thethirdone.github.io/blog/posts/random-sorting/