4 ms·
Surely worstsort would be While list not sorted { Random(list) } ?
by benj111 8y ago
Surely worstsort would be
While list not sorted {
Random(list)
}
?
- yarg 8y agoSee kccqzy's comment.
- benj111 8y agoThat would be consistent for a consistent input though? (I'll admit the maths is beyond me) Random wouldn't have that 'advantage'. I'd go for a consistently bad algorithm over a randomly bad algorithm, although that is subjective.
- Sohcahtoa82 8y agoThat's Bogosort. https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
- deleted 8y ago[deleted]
- rocqua 8y agoThat has expected running time N! loops. Far from horrible unless you make the 'is sorted' or 'randomize' calls horrible. The great thing about this algorithm is that the same piece of code does all these things. There isn't a separate bodge for checking whether something is sorted.
- pbhjpbhj 8y agoIt's not sorting though, you don't get closer to the desired order and there's no guaranteed bound on termination.
- benj111 8y agoYou kind of do get closer, every roll of the dice increases your chance of getting a 6. Agreed theres no guaranteed bound, that's my basis for suggesting it as worst.
- daveFNbuck 8y agoYour expected number of rolls until a 6 doesn't decrease with each roll. The same is true for this algorithm. If you run this algorithm and it has an expected 10 days runtime, you still have an expected 10 days left after 5 days of failure. The worstsort in the post has a much worse expected runtime than the sort you described. You could make the bound not guaranteed by randomly deciding whether to throw out the result and start over at the end.
- benj111 8y agoIf I roll a die the chances are 1 in 6 yes, but every throw is another bite of the cherry. If I throw the die 10 times, the chances of one of those throws being a 6 is greater than 1 in 6. The same with this 'sorting' algorithm. Yes you could add a random element to any sorting algorithm to make it slower. I suppose you could argue with my algorithm, the primary purpose of the random wasn't to slow the algorithm down, the algorithm would totally break! I'm not sure it even matters though. My primary point was that a random algorithm can be worse than just a slow algorithm. With Worstsort, you can be fairly certain that the heat death of the universe will interupt you. My algorithm you don't know, it might be instant, it might never finish. More concretely, do you want a game that runs at a steady 30fps, or a game that goes from 5fps to 30000fps, with an average of 60fps ?
- zbentley 8y agoThat's not accurate: https://en.wikipedia.org/wiki/Gambler%27s_fallacy https://en.wikipedia.org/wiki/Gambler%27s_fallacy
- benj111 8y agoGamblers fallacy is me rolling a die 10 times and so expecting the 11th time to be anything other than a 1 in 6 chance. That isn't what I'm saying. I'm saying if you roll a die 10 times, the chance of any one of those rolls being 6 is greater than 1 in 6. It is statistically likely if you roll a die 10 times, that you will roll a 6 at least once.
- lelf 8y agofor x in 3 1 2 5 4; do (sleep $x; echo $x) & done
- xaedes 8y agoI think that is equivalent to selection sort: You put all numbers into the scheduler which periodically checks all scheduled threads and selects the one which timer elapsed, i.e. it sequentially selects the scheduled tasks with increasing timer duration value.
- Retra 8y agoEven then, you could do worse by actively avoiding the sorted state with a bad distribution.