[quantum] quantum bogosort

[Korny Sietsma]

A friend sent me this very special sort algorithm...

Quantum bogosort

An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. The list is then inspected, and if it is not in order, the universe is destroyed. By the many-worlds interpretation of quantum physics, the quantum randomization spawns 2^N (where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.

http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort

--
Kornelis Sietsma  korny at my surname dot com http://korny.info
"Every jumbled pile of person has a thinking part
that wonders what the part that isn't thinking
isn't thinking of"

[Paul Cowan]

On 16 June 2011 15:51, Korny Sietsma <ko...@sietsma.com> wrote:

A friend sent me this very special sort algorithm...

Quantum bogosort

There's another entertaining sort algorithm that's been doing the rounds of late - sleepsort:

while [ -n "$1" ]; do (sleep $1; echo $1) & shift; done; wait

(for the non-shell-script-familiar: to sort a list of (say) 5 numbers, spawns off 5 processes, gives a number n to each one. Each process waits n seconds, then prints n. Net results: numbers emerge in sorted order (assuming a perfect scheduler and no contention)

Paul

 

[Noon Silk]

On Thu, Jun 16, 2011 at 3:51 PM, Korny Sietsma <ko...@sietsma.com> wrote:
> A friend sent me this very special sort algorithm...
>
> Quantum bogosort
>
> An in-joke among some computer scientists is that quantum computing could be
> used to effectively implement a bogosort with a time complexity of O(n). It
> uses true quantum randomness to randomly permute the list. The list is then
> inspected, and if it is not in order, the universe is destroyed. By
> the many-worlds interpretation of quantum physics, the quantum randomization
> spawns 2N (where N is the number of random bits) universes and one of these
> will be such that this single shuffle had produced the list in sorted order.

Similar idea: Quantum Suicide:
<http://en.wikipedia.org/wiki/Quantum_suicide_and_immortality>

> http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort
>
> --
> Kornelis Sietsma  korny at my surname dot com http://korny.info
> "Every jumbled pile of person has a thinking part
> that wonders what the part that isn't thinking
> isn't thinking of"

--
Noon Silk | http://dnoondt.wordpress.com/ >

Fancy a quantum lunch? http://groups.google.com/group/quantum-lunch?hl=en

"Every morning when I wake up, I experience an exquisite joy — the joy
of being this signature."

[Sam Watkins]

Korny Sietsma wrote:
> The list is then inspected, and if it is not in order, the universe is
> destroyed.

The 'destroy_universe' function might be challenging to implement,
and especially to alpha-test.

I like the idea of the sleep sort, nice one :) It might even be reasonably
efficient with a decent scheduler. I suppose the scheduler might be using a
heap data structure and will sort the tasks efficiently. Typical unix won't
cope well with millions of processes, but my coro scheduler could handle it
happily, as there are only two words of overhead per process / sort item.
bawhahaa can't believe I'm taking this seriously :p

Sam

[Sam Watkins]

On Fri, Jun 17, 2011 at 12:09:01PM +1000, Sam Watkins wrote:
> I like the idea of the sleep sort, nice one :) It might even be reasonably
> efficient with a decent scheduler.

lol I'm an idiot. It might be efficient on CPU usage, but very slow!

Sam