# Physical representation of bead sort

#### YoungPhysicist

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:
Related Programming and Computer Science News on Phys.org

#### willem2

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

#### YoungPhysicist

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.

### 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