3 ms·
Quantum bogosort is probably my personal favorite. Randomly permute the input using a quantum source of entropy. If the input is not sorted, destroy the univers
by michaelmior 5y ago
Quantum bogosort is probably my personal favorite. Randomly permute the input using a quantum source of entropy. If the input is not sorted, destroy the universe. The only universe remaining is one where the input was already sorted. Runs in O(n) time.
- Sharlin 5y ago(the problem of destroying the universe left as an exercise to the reader)
- wahern 5y agoFor the operation of this algorithm, is there any meaningful difference between destroying the universe and destroying the observer(s)? https://en.wikipedia.org/wiki/Quantum_suicide_and_immortality https://en.wikipedia.org/wiki/Quantum_suicide_and_immortalit... EDIT: If you allow for the objects to spontaneously sort themselves, the runtime is O(1).
- drdeca 5y agoSurely O(n) for checking whether it is sorted?
- btheshoe 5y ago(the problem of destroying which universe is also left as an exercise to the reader)
- contravariant 5y agoYou could just destroy all universes to ensure it's sorted in the remaining reality.
- michaelmior 5y agoI'm confused. What reality is remaining if all universes are destroyed?
- contravariant 5y agoNone, but in it the list is sorted. Or rather a reality wherein it wasn't sorted doesn't exist anymore.
- michaelmior 5y agoTrue although not very helpful if you actually want to do something with the sorted list. But I suppose if you cease to exist, so does whatever problem sorting the list was intended to solve.
- contravariant 5y agoEven without destroying the universe you can sort your list with a quantum source of entropy, just use: def cosmicraysort(list): while not sorted(list): pass
- flipflip 5y agoYou can just kill the observer. Quantum immortality sort: def qisort(list): qshuffle(list) if not sorted(list): kill_observer() Only in the universe in which th the list is sorted, the user will survive. There might be no such universe, but then the user is no longer waiting on the result.
- cevi 5y agoUnfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?
- deleted 5y ago[deleted]
- michaelmior 5y agoThis is not true if you can generate a random number in constant time which is probably the more practical of the constraints to satisfy when implementing this algorithm.