O(n) Sorting Algorithm: Quantum Bogosort

I remember reading into this topic a while ago. Here is a relevant Wikipedia article. I, for one, look forward to the day when we all can have all our problems solved by destroying the universe.

[]http://en.wikipedia.org/wiki/Quantum_suicide_and_immortality

Re: O(n) Sorting Algorithm: Quantum Bogosort

#5

Post by xxbondsxx » Sat, Jul 06, 2013, 6:59 PM UTC

Some programmers on 4chan came up with a "Sleep sort" algorithm and then proceeded to optimize it, complete with example code:

http://dis.4chan.org/read/prog/1295544154

It essentially spawns a new thread for every item in the array, sleeps for an amount of time that scales with the item's value, and then prints out that item. So it's O(n + timeScale * $biggest_input)

Pretty funny / entertaining if taken lightly :P

Re: O(n) Sorting Algorithm: Quantum Bogosort

#6

Post by Whitespace » Sat, Jul 06, 2013, 7:09 PM UTC

More information about bogosort: https://en.wikipedia.org/wiki/Bogosort

Re: O(n) Sorting Algorithm: Quantum Bogosort

#7

Post by [deleted] » Sat, Jul 06, 2013, 7:09 PM UTC

coherentpony wrote: post #3

tantalor wrote: post #2

What's the time-space complexity of destroying the universe?

Time O(1). Space O(n).

[deleted]

Re: O(n) Sorting Algorithm: Quantum Bogosort

#8

Post by cldr » Sat, Jul 06, 2013, 7:11 PM UTC

I coded up a quick implementation of this in python, but in testing I found that after the algorithm was done I actually wanted a shuffled list.

Re: O(n) Sorting Algorithm: Quantum Bogosort

#9

Post by McUsr » Sat, Jul 06, 2013, 7:19 PM UTC

djent wrote: post #4

I remember reading into this topic a while ago. Here is a relevant Wikipedia article. I, for one, look forward to the day when we all can have all our problems solved by destroying the universe. [] http://en.wikipedia.org/wiki/Quantum_suicide_and_immortality

Hahahaha.

Re: O(n) Sorting Algorithm: Quantum Bogosort

#10

Post by groundshop » Sat, Jul 06, 2013, 7:27 PM UTC

xxbondsxx wrote: post #5

Some programmers on 4chan came up with a "Sleep sort" algorithm and then proceeded to optimize it, complete with example code: http://dis.4chan.org/read/prog/1295544154 It essentially spawns a new thread for every item in the array, sleeps for an amount of time that scales with the item's value, and then prints out that item. So it's O(n + timeScale * $biggest_input) Pretty funny / entertaining if taken lightly :P

I wish I'd seen some of this before I took a discrete optimization course. I would have loved to submit some of this.