4 ms·
Bogosort is pretty simple, too. while not is_sorted(a) do shuffle(a) However the shuffle function hides a surprising amount of complexity. It is nontri
by antognini 5y ago
Bogosort is pretty simple, too.
while not is_sorted(a) do
shuffle(a)
However the shuffle function hides a surprising amount of complexity. It is nontrivial to write a correct shuffle function. [1]
But Bogosort isn't even the worst sorting algorithm out there! There is also Worstsort [2].
[1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
[2]: https://arxiv.org/abs/1406.1077 https://arxiv.org/abs/1406.1077
- CaptainNegative 5y agoShuffling is even less tricky if you're not trying to do it in place, if you're not trying to do it in linear(ithmic) time, or if you're not trying to induce a uniform distribution over all permutations (but rather just want some positive probability for all of them). Relaxing any combination of these conditions works just fine for Bogosort.
- infinisil 5y agoIt would even suffice to just swap two random elements every iteration!
- innocenat 5y agoI think most C++ implementation of bogosort use std::next_permutation
- 6510 5y agoMy gut says that combining that with other sort cycles in some magic ratio could do magical things. I'm quite wrong quite often ofc but the adventure is out there!
- a1369209993 5y agoFun fact: Fisher-Yates samples a uniform distribution over permutations and is therefor capable of producing any permutation, so you can sort any array in linear time using Fisher-Yates with its RNG replaced by a appropriate oracle. (So the complexity of sorting a array mostly reduces to the complexity of determining which permutation it's in relative to a sorted version.)
- j16sdiz 5y agoa good (even) shuffle is not easy.
- deleted 5y ago[deleted]
- jtolmar 5y agoYou can turn a sort into a shuffle by replacing the comparator with a random coin flip, and you already have defined a sort algorithm, so there's no added code complexity. fn bogosort(a, comparator): while not is_sorted(a, comparator) do bogosort(a, rand)
- aidenn0 5y agoYou can't turn all sorts (not even all comparison sorts!) into a shuffle by replacing the comparator with a random coin flip. In fact your code post is a demonstration of that fact.