Worstsort
byorgey.wordpress.com
byorgey.wordpress.com
Then we can take any randomized algorithm and, for its random values, use mix(real_rng.random(), Ackermann(5, 5)).
This fails that criterion, as you can just throw away all the calls except badsort 0.
My criterion isn’t well defined, because what you can statically know isn’t well defined, but I know a cheater when I see one :)
Wouldn't that necessarily be slower than all other algos, and also demonstrably be sorting, and - if each other algo's termination is bounded - have a bounded termination time.
It might not terminate for all lists, in theory; you could have a watchdog to cure that I think.
It seems like the tricks from this competition would be reusable for the slowest algorithm competition.
sort ≡ head ∘ sort ∘ permutations
It creates the whole monolithic expression with all the parenthesis in pessimal positions, forcing all the comparisons in the wrong order (back to front, aka least-significant-bits first), which makes it impossible to use the short circuiting of lexicographical comparisons.
While list not sorted { Random(list) }
?
Random wouldn't have that 'advantage'.
I'd go for a consistently bad algorithm over a randomly bad algorithm, although that is subjective.
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.
Agreed theres no guaranteed bound, that's my basis for suggesting it as worst.
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.
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 ?
>My algorithm you don't know, it might be instant, it might never finish. //
If it might never finish then it's not [completely] sorting IMO. But I'm a long way off being a comp. sci..
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.
But my chances still increase. If I roll that die once, I know my chances of rolling a 6 are poor, if I roll it 10 times the odds would be better, a million times almost certain.
If my chances of success are steadily increasing, why is that not progress? (especially for an algorithm based solely on chance).
Consider an alternative algorithm based solely on chance. Pick an element uniformly at random and if it's larger than the element after it, swap them. This algorithm has progress, as the array becomes monotonically more sorted over time, decreasing the expected amount of time until the algorithm is done. This is what it looks like to make progress. Your algorithm does not have that feature.
You seem to be ignoring the fact you've just been spending a day rolling die, where if you had have rolled a 6 you wouldn't be back the next day.
That's survivorship bias.
If we're talking about practical applications like a video game, I'd still say that an algorithm that won't finish within my lifetime is strictly worse than one that might.
Agreed, that sometimes the average rate is fine. That just legitimises my disagreement over the 'worst' sort, there is no worst sort.
Ultimately its just down to semantics. The author stroked his beard and thought about the absolute slowest sort, and called it the worst. I stroked my (metaphorical) beard and found a different kind of worst. Both should be avoided in practical applications where possible.
His is cleverer yes, mine is stupid, that's probably the most relevant metric, and probably why no one submitted a sort that returns the wrong answer, which I would claim could also be 'worst'.
Then why did you bring up fps in video games?
> there is no worst sort.
Of course there is no worst sort. But some sorts are worse than others. The disagreement here is that your sorting algorithm is clearly better than Worstsort.
If all randomized algorithms with unbounded runtime are worse than worstsort, then flipping a coin until you get heads and then running a fast sort algorithm would be worse than Worstsort. If you instead take a more reasonable approach like comparing expected runtime, Worstsort is clearly worse than bogosort.
for x in 3 1 2 5 4; do (sleep $x; echo $x) & done