I absolutely loved learning about Bead Sort when I was in Uni. I was taking a class on algorithm design and Big-O notation and ended up reading through the sorting algorithms page on wikipedia[1] and then wandering off the garden path investigating a few.
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.
> (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)
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.
puts on hat from the second level of the pedant hierarchy
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.
"It's amazing what you can do if you're willing to sacrifice a few universes to get out of doing some addition" - probably no one ever, but it should've been said before now.
That's not how bogosort works. You just make a separate universe for each of N! possible orders, and then discard all the universes where it is not already sorted.
A universe where P=NP might not support life. Or, might not support yours. Or, only yours.
> 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).
Actually I would assume the time for removing each rod while collecting the result is quadratic because when the number of rods is high enough you can no longer see the highest one at a glance but have to scan through all possible rod positions for spotting the one that sticks out.
In spaghetti sort I think you place your hand at the top and remove the first piece to touch it. That takes it from O(n) to O(1) to remove a single piece.
Of course, your hand is then a magical device that can do a reduction in constant time.
This is one of those cases where adding extraneous information confuse the illustration. It took me 2-3 times through before I figured out that color was completely irrelevant.
The optimal complexity of a sorting network of fixed width numbers is bound by depth O(log n). [1]
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.
Runtime is proportional to g (the local gravitational constant), so if you find it's too slow, you can just run your algorithm in a centrifuge or on Jupiter to speed it up.
Preparation is the killer though. Setup time for bead sort linearly scales with the sum of the values of the array. However, depending on your implementation setup and execution can be parallelized (for example on a Connect Four board in its default vertical orientation in an environment with gravity).
The numbers being sorted in Bead Sort are base 1, which means it's never faster than O[n] where n is not the number of numbers being sorted, but the largest number being sorted.
That means it won't scale well and is impractical for sorting realistic numbers (barring a lot of special-purpose parallel hardware).
It sounds like how we used to program in BASIC. Line numbering initially by 10, leaving room for inserting lines without having to renumber. So you'd start out 10,20,30,40... and if you had to add a line between 20 and 30 you'd make it 25.
I'm almost certain this already exists under a different name, like a columnar sort or something. Can't be bothered to Google on mobile, but this is 100000% not novel
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...