21–30 of 60 posts
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.
My favorite is still slowsort. https://en.wikipedia.org/wiki/Slowsort > It is a reluctant algorithm based on the principle of multiply and surrender. It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis. https://www.mipmip.org/tidbits/pasa.pdf > The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the…
Earlier quoted context omitted.
It is if you ignore how the underlying OS implements multitasking and sleep() in particular. And the kernel-side implementation usually involves some kind of priority queue of sleeping threads. So taken as a whole sleep-sort is just an convoluted implementation of heap-sort that outsources the actual sorting to OS.
I really like sleep sort because it trades (fundamentally) cycles and memory for time. In theory you could do this in hardware. Hardware timers are pretty trivial, you could imagine a hardware chip that accepts a number, then writes the value to the next free slot in an array when the time has elapsed. As timers go off, the array fills up. Obviously you need to handle collisions and whatnot but nothing in this scream…
Isn't 'sleep sort' linear with respect to array size? O(n) sort achieved?
It's perversely linear with respect to the largest element in the array, if that's greater than the runtime of the underlying heapsort. Good luck with negative entries. Response to dead comment: > Couldn't this be solved by scaling everything by the largest entry. Of course that requires first a pass to find the largest entry but that's not as expensive? One presumes that we don't have infinite precision timers, so y…
Isn't 'sleep sort' linear with respect to array size? O(n) sort achieved?
I recently found a fun linear-time systolic sorting algorithm. I'd describe the serial implementation as unconventionally obvious. It's like insertion sort, without all the bother of swapping. def index_sort(a): n = len(a) output = [None] * n for i in range(n): #can run in parallel, damn the GIL index = 0 for j in range(n): if a[j]
> linear-time But... there are two nested `range(n)` for loops. Typo?
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.
(the problem of destroying the universe left as an exercise to the reader)
EDIT: If you allow for the objects to spontaneously sort themselves, the runtime is O(1).
I wonder what the author, "hilariously" making one sorting function print " sent to gulag" and calling it "stalin-sort", would think of "hitler-sort" which prints " burned in oven"?
Please don't normalize mass-murderers, even for memes.
Earlier quoted context omitted.
(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).