Re:I can’t believe that I can prove that it can sort
by Izkata on Monday July 04, 2022 @03:39PM
(#31980921)
Yeah, this sorting algorithm is something you can come up with by accident if you do bubble sort wrong. I wouldn't be surprised if a lot of beginners came up with this one in intro courses. I think I saw it around 2006-2008 when I was a TA and one of my students couldn't figure out why his array got sorted in the wrong order (don't remember for sure though).
For example, from 2016, here's someone not getting the difference between the two: https://stackoverflow.com/questions/40786409/whats-the-diffe...
Re:I can’t believe that I can prove that it can sort
by yannickmoy on Monday July 04, 2022 @02:06PM
(#31980087)
For a related eye-opening result, with both practical application and interesting research backing it, see this talk on "Quicksorts of the 21st century" at Newton Institute on Verified Software last year: https://www.newton.ac.uk/seminar/30504/
TLDR; practical complexity computation needs to take into account things like memory access latency on different architectures.
Honestly, I always thought it is a common knowledge and it is just too simple and for this reason gets omitted from books.
People in CS/IT tend to not spend a lot of time on algorithms with bad complexity and so I am used to people discounting algorithms with useful properties just because there is another that is a bit more efficient when n goes to infinity.