What's the time-space complexity of destroying the universe?
It doesn't really matter because in the surviving universe you don't do it.
O(n) Sorting Algorithm: Quantum Bogosort
11–19 of 19 posts
Re: O(n) Sorting Algorithm: Quantum Bogosort
#12I may not understand quantum computing properly, but would not this approach require N entangled qubits? If no, can someone explain how it would function on less than N qubits, for example 1? If it does require N qubits...I can imagine a classical solution with O(n) and slightly less ridiculous hardware requirements.
Re: O(n) Sorting Algorithm: Quantum Bogosort
#13I may not understand quantum computing properly, but would not this approach require N entangled qubits? If no, can someone explain how it would function on less than N qubits, for example 1? If it does require N qubits...I can imagine a classical solution with O(n) and slightly less ridiculous hardware requirements.
I think it requires N*log N un-entangled randomly initialized qubits. Please correct me if I'm wrong...
Re: O(n) Sorting Algorithm: Quantum Bogosort
#14Some 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
That seems like a ridiculous implementation of a quite reasonable algorithm. Instead of spreading them out through time, you can spread the values out through space. Assume you know that you elements are all positive integers less than 100 (or can be mapped to such). Allocate an array of length 100. In O(n) time, you can read through your unsorted list, and copy each element to the appropriate location in the array. Then you can read through the array and print out the values in order.
Re: O(n) Sorting Algorithm: Quantum Bogosort
#15What's the time-space complexity of destroying the universe?
There is only one universe, so it must be a constant, O(1)
Re: O(n) Sorting Algorithm: Quantum Bogosort
#16Some 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
That seems like a ridiculous implementation of a quite reasonable algorithm. Instead of spreading them out through time, you can spread the values out through space. Assume you know that you elements are all positive integers less than 100 (or can be mapped to such). Allocate an array of length 100. In O(n) time, you can read through your unsorted list, and copy each element to the appropriate location in the array.…
That sounds suspiciously like an insert sort.
Re: O(n) Sorting Algorithm: Quantum Bogosort
#17[deleted]
Re: O(n) Sorting Algorithm: Quantum Bogosort
#18Some 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
That seems like a ridiculous implementation of a quite reasonable algorithm. Instead of spreading them out through time, you can spread the values out through space. Assume you know that you elements are all positive integers less than 100 (or can be mapped to such). Allocate an array of length 100. In O(n) time, you can read through your unsorted list, and copy each element to the appropriate location in the array.…
Re: O(n) Sorting Algorithm: Quantum Bogosort
#19Earlier quoted context omitted.
That seems like a ridiculous implementation of a quite reasonable algorithm. Instead of spreading them out through time, you can spread the values out through space. Assume you know that you elements are all positive integers less than 100 (or can be mapped to such). Allocate an array of length 100. In O(n) time, you can read through your unsorted list, and copy each element to the appropriate location in the array.…
That sounds suspiciously like an insert sort. http://en.wikipedia.org/wiki/Insertion_sort
Similar but asymptotically different. In insertion sort, if your partialy sorted list is [1,5], and the next element to insert is a two, you would scan the list until you arrive at the five, which. In the system I described the partialy sorted list would be represented as [1,_,_,_,5], and you would update the second element so it would be [1,2,_,_,5].
EDIT: After thinking about it, you could do the insertion step in O(1) time if you use a linked list instead of an array. The part where insertion sort gets its log(n) factor is in scanning the list, which can take (on average) no less than log(n) time.
tantalor is correct in identifying this algorithm as pigeonhole sort.