7 ms·

> If swaps are the only thing you are counting, selection sort is O(n). And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :)

by mrami 7y ago

> If swaps are the only thing you are counting, selection sort is O(n). 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. [1] https://en.wikipedia.org/wiki/Time_complexity https://en.wikipedia.org/wiki/Time_complexity

thethirdone 7y ago
> And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) 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.
- mrami 7y ago
  I'm not sure what conditions you have in mind, but in the selection sort, the comparisons are O(n^2), and the assignments are O(n). 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/56d6e234f34787b8c5daf543a299a7d5 https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a...
ivanhoe 7y ago
> And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) Good one, but you probably meant Satyr (or Faun as Romans called it)
- mrami 7y ago
  Centaurs are multifaceted and live rich, complex inner lives. https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/media/File:Achilleus_Lyra.jpg https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/...

by mrami 7y ago

thethirdone 7y ago

> And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) 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.

mrami 7y ago
I'm not sure what conditions you have in mind, but in the selection sort, the comparisons are O(n^2), and the assignments are O(n). 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/56d6e234f34787b8c5daf543a299a7d5 https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a...

ivanhoe 7y ago

> And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :) Good one, but you probably meant Satyr (or Faun as Romans called it)

mrami 7y ago
Centaurs are multifaceted and live rich, complex inner lives. https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/media/File:Achilleus_Lyra.jpg https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/...