Unconventional Sorting Algorithms

Re:Unconventional Sorting Algorithms by michaelmior on Thursday October 21, 2021 @01:53PM (#28948338)

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.

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by contravariant on Thursday October 21, 2021 @06:22PM (#28951533)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by flipflip on Thursday October 21, 2021 @07:55PM (#28952296)

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.

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by Sharlin on Thursday October 21, 2021 @02:26PM (#28948877)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by wahern on Thursday October 21, 2021 @03:13PM (#28949515)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by drdeca on Thursday October 21, 2021 @03:34PM (#28949784)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by contravariant on Thursday October 21, 2021 @06:20PM (#28951523)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by michaelmior on Thursday October 21, 2021 @06:48PM (#28951759)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by contravariant on Thursday October 21, 2021 @07:33PM (#28952133)

None, but in it the list is sorted.

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by michaelmior on Thursday October 21, 2021 @07:52PM (#28952273)

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.

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by btheshoe on Thursday October 21, 2021 @06:03PM (#28951381)

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

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by cevi on Thursday October 21, 2021 @08:17PM (#28952436)

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?

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by michaelmior on Friday October 22, 2021 @08:46AM (#28956570)

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.

[ Parent | on HN ]

Re:Unconventional Sorting Algorithms by AlexAndScripts on Friday October 22, 2021 @03:29AM (#28954526)

We could skip the random permutation. There will still be no universe where the list is unsorted.

[ Parent | on HN ]