Physical representation of bead sort

Bead sort is a not practical sorting algorithm that suppose to have a time complexity of ##O(\sqrt{n})##in the real world.

I thought it would be great if a device that can take numbers from the computer,then turn it into analog stuff that the device can read,drop the beads,and return it to the computer as digital signals.Can such thing being constructed?

Edit:For turning signal back to digital,I thought above using a series of photodiodes and lasers to read the position of the beads,but I still got no clue of how to place them in the rod.
 
Last edited:
1,860
175
I thought it would be great if a device that can take numbers from the computer,then turn it into analog stuff that the device can read,drop the beads,and return it to the computer as digital signals.Can such thing being constructed?
It will take O(n) to output the numbers from the computer to the bead-device, so you can't go faster than that.
The bead device would need O(n^2) beads. You'd need an plate with a rectangular array of holes and use O(n^2) devices that either push a bead through or don't. Light speed delay would mean you'd need O(n) time to distribute the numbers to be sorted, even if you had the numbers ready on an infinite set of registers and all available in parallel.

If you allow a time O(n) with a device of size O(n), bubble sort work just fine
 
If you allow a time O(n) with a device of size O(n), bubble sort work just fine
Yeah, I know it wouldn't be efficient if I actually made one of those devices, but I just thought it would be interesting.
 

Want to reply to this thread?

"Physical representation of bead sort" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top