7 ms·
It would even suffice to just swap two random elements every iteration!
by infinisil 5y ago
It 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.)