   Stupid sorting algorithms (really)
  I came across a few really stupid sorting algorithms looking around on http://www.nist.gov/dads/. Some of which I am not even sure if they ever finish.I noticed a bogo sort, bozo sort, perm sort, and stooge sort. I've only see stooge sort actually finish. You can see some of these sorting algorithms here.Why would someone make these, and more importantly do some of these ever even finish?   
Quote:Why would someone make theseTo give professors something to set questions about without students being able to find all the answers on Google.That, or for fun.   ;  I've been thinking a long time that there should be random_sort() -algorithm in standard c++ library just like there is random_shuffle(). These are very different things. random_shuffle SHUFFLES objects in random order, but random_sort SORTS objects in random order. What do you think guys? :)   ;Quote:Original post by KimeliI've been thinking a long time that there should be random_sort() -algorithm in standard c++ library just like there is random_shuffle(). These are very different things. random_shuffle SHUFFLES objects in random order, but random_sort SORTS objects in random order. What do you think guys? :)I wouldn't see the point of doing such a thing. Using something that is inherrently random to try and produce sorted data is not an ideal solution to say the least. I'm sure it would work if you let it run through enough iterations, but it would hardly be very efficient.;Quote:Original post by GDKnightWhy would someone make these...FunQuote:Original post by GDKnight...and more importantly do some of these ever even finish?If based on a true RNG, yes.  If not, possibly.CM   ;  They're usually used as examples of truly bad algorithms or to make a point about odd computer science theories. For example, while bogosort is O(something stupidly large) quatum bogosort is an O(n) sorting algorithm (given an O(1) method of destroying the universe).   ;Quote:Original post by SiCranequatum bogosort is an O(n) sorting algorithmSo when quantum computers come out, it might be more useful?   ;  Um. Did you catch the part about O(1) method of destroying the universe? Quantum bogosort falls in the "to make a point about odd computer science theories" category.   ;Quote:Original post by GDKnightI came across a few really stupid sorting algorithms looking around on http://www.nist.gov/dads/. Some of which I am not even sure if they ever finish.Actually, they're all guaranteed to terminate eventually. In general, variants on the "shuffle the cards, then see if they're sorted" strategies like the ones you linked to are guaranteed to terminate. Come to think of it, I'm not sure how you'd write a correct sorting algorithm that isn't guaranteed to terminate.   ;  "shuffle the cards, then see if they're sorted" isn't guarenteed to terminate - the probablity of them terminating tends towards 1 as the number of shuffles approaches infinity. At least when you use genuinely random numbers to shuffle with.   