6 ms·
Worstsort
- tluyben2 8y agoAre there competitions for this? If not, I think there should be; designing the worst possible, but provably terminating and finite and non cheating (as in the author his definition which I think is a good one) versions of algorithms. The proof has to be provided by the author ofcourse.
- praptak 8y agoThere's the mathematical competition to define the largest precisely defined number, i.e. "largest number defined by humans so far, plus one" is not ok, but "largest finite number of cells visited by Turing machines of 7 states on an initially zeroed tape" is ok. It's obviously about finding new tricks rather than rehashing the existing ones. It seems like the tricks from this competition would be reusable for the slowest algorithm competition.
- kccqzy 8y agoThat seems like, in many cases, reducible to finding the biggest number, and then using that number in some way in the algorithm.
- grenoire 8y agoLike GCP computing pi this year, they can brag about the immense amounts of hardware they throw into it but still take a year to sort a 5-element list.
- pbhjpbhj 8y agoIterate once with each other worst algo, compare the lists, consider matching moved locations to be sorted and choose that as the input for the next iteration. 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.
- ddebernardy 8y agoWhen wondering what's the point in trying to find bad sort algorithms, I shed a few tears thinking about a few StackOverflow questions in its early days where a programming beginner would ask for basic algorithm implementations and a few mischievous answerers would suggest things like boggle sort.
- quickthrower2 8y agoA bad sort algorithm makes you look like a hero when you do some “performance improvements” later on.
- nicoburns 8y agohttps://gkoberger.github.io/stacksort/ https://gkoberger.github.io/stacksort/
- kccqzy 8y agoI'll give it a try at defining the author's intuition of "doesn’t cheat" in the sense that it is always "making real progress". I'll define it as every intermediate value that is generated in the computation is eventually consumed. If a function, say, computes Ackermann(5,5) and throws away the result and then starts the actual sorting process, then the Ackermann(5,5) is unused and would be considered cheating. In a sense we can draw a data-flow diagram of the computation and everything has at least one outgoing edge, except perhaps the final output.
- XMPPwocky 8y agoProblem is we can define a function mix(a, b) which intermingles two arguments and produces a new value dependent on both- for example, sha256(a.concat(b)). Then we can take any randomized algorithm and, for its random values, use mix(real_rng.random(), Ackermann(5, 5)).
- sometimesijust 8y agoThe use of "foldr insert []" makes this redundant nonsense.
- Hackbraten 8y agoI disagree. The scientifically interesting thing is that we can have such exploding complexity, while at the same time every step of the algorithm still actively works towards a solution.
- benj111 8y agoSurely 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.
- ginko 8y agoWould a Haskell implementation of the second step (recursively call badsort and pick the first) actually exhaust all permutations of permutations before picking the first item, or would this have O(n) (or at least less than O(n!)) complexity due to lazy evaluation?
- majewsky 8y agoThe foldl in `badSort 0` has to evaluate its entire argument list. As far as I can see, this behavior propagates through to all functions shown in the article since they all call `badSort 0` eventually.
- gowld 8y agoIt's foldr, not fold. That's what makes it consume absurd stack space, creating a stack of thunks of length (n-factorial-iterated-k-times, including the nested towers of folders inside each element) before it can use any laziness to shortcut the actual comparisons applied by `insert`. 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.
- lelf 8y agoSo sort ≡ head ∘ sort ∘ permutations I wonder if there is some neat (and totally useless) algorithm for sort using that info.
- conistonwater 8y agoReminds me a little of reluctant search from Pessimal Algorithms and Simplexity Analysis (http://www.bowdoin.edu/~ltoma/teaching/cs231/fall13/Material/broder86pessimal.pdf http://www.bowdoin.edu/~ltoma/teaching/cs231/fall13/Material...)
- hyperpape 8y agoAnother “don’t cheat” intuition is “you can’t statically know that a function call prior to the final result produces the correct answer”. 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 :)