Bead Sort(karthikkaranth.me) |
There are several amusing ways that standard algorithmic analysis has been subverted with creative solutions (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes) but beadsort stood out as a really fun way to turn the problem on its head - the fact that it appears to be inspired from misusing an abacus just makes it even better.
It's a great example of why having people who can think outside of the box can be a good asset - approaching problems from unexpected directions can yield valuable and novel solutions.
1. https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...
Does this same line of thinking conclude that P=NP in at least one universe, too? You can use a radioactive decay counter to generate quantum random numbers, interpret them as a answer to an NP problem, and then verify the solution in polynomial time the normal way? In at least one universe, that will always work on the first try.
That wouldn’t actually make P = NP, because P is defined mathematically from first principles rather than being based on the rules of the universe. However, it would shift the class of practically computable problems from being ‘like P’ (but with limits on the runtime and memory usage achievable), to being ‘like P^NP’, P with an NP oracle, which is surprisingly a different complexity class from NP. At least, that’s what I gather based on Wikipedia and Stack Overflow [1]; I’m not an expert on the subject so I could be mistaken.
[1] https://cs.stackexchange.com/questions/2712/does-npnp-np
A universe where P=NP might not support life. Or, might not support yours. Or, only yours.
These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model
What do you mean by this?
Reminds me of spaghetti sort [1], but bead sort is much cleverer.
> Preparing the n rods of spaghetti takes linear time. Lowering the rods on the table takes constant time, O(1). This is possible because the hand, the spaghetti rods and the table work as a fully parallel computing device. There are then n rods to remove so, assuming each contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).
> (and I'll admit it looks very pretty)
It does look better with all the colors, but it distracts from what you are showing.
I'm not sure how to go about analyzing bread sort, but it does seem bound by aligning and inserting the beads into each column which would be at least O(log n), the number of digits. But, I'd be surprised if it is optimal.
[1] https://www.researchgate.net/publication/220329153_An_Optima...
That means it won't scale well and is impractical for sorting realistic numbers (barring a lot of special-purpose parallel hardware).
Visual is nice though
Of course, your hand is then a magical device that can do a reduction in constant time.
Assuming P!=NP!=co-NP, that computational model is equivalent to either NP or co-NP depending on the multiverse semantics you are using, not P^NP. If you can send the computation through multiple universes and get back a 'YES' or 'NO' answer, depending on whether the 'YES' or 'NO' is quantified existentially or universally on the leaves of the computation tree, you get NP or co-NP. Intuitively speaking, imagine you have a 3-SAT instance; you can send one assignment of truth values to the variables to each parallel universe for computation. If the multiverse answers you 'YES' if there exists one universe that says 'YES', that solves NP problems in P-time. If the multiverse answers you 'YES' if all universes say 'YES', that solves co-NP problems in P time.
If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.
I'd say radix sort is the canonical example of a non-comparative sorting algorithm.
