Hacker News Reader

Comment by michaelmior | Hacker News Reader

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.

View on HN

Even 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

You 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.

(the problem of destroying the universe left as an exercise to the reader)

For 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_immortalit...

EDIT: If you allow for the objects to spontaneously sort themselves, the runtime is O(1).

Surely O(n) for checking whether it is sorted?

(the problem of destroying which universe is also left as an exercise to the reader)

You could just destroy all universes to ensure it's sorted in the remaining reality.

I'm confused. What reality is remaining if all universes are destroyed?

None, but in it the list is sorted.

Or rather a reality wherein it wasn't sorted doesn't exist anymore.

True 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.

Unfortunately, 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?

This 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.

Reply on news.ycombinator.com