Physical representation of bead sort

In summary, the conversation discusses the concept of using a bead sorting algorithm with a time complexity of O(sqrt{n}) in the real world. The idea is to create a device that can convert numbers from a computer into analog signals, drop beads, and then return the signals to the computer as digital signals. However, it is mentioned that this would require a device with O(n^2) beads and a plate with a rectangular array of holes. It is also noted that a bubble sort could work efficiently if a time complexity of O(n) and a device size of O(n) were allowed. The conversation concludes with the acknowledgment that while this may not be practical, it is an interesting concept.
  • #1
YoungPhysicist
Insights Author
350
203
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:
Technology news on Phys.org
  • #2
Young physicist said:
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
 
  • #3
willem2 said:
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.
 

Related to Physical representation of bead sort

1. What is the physical representation of bead sort?

The physical representation of bead sort is a sorting algorithm that uses gravity and beads to sort a list of numbers in ascending order. It is also known as gravity sort or comb sort.

2. How does bead sort work?

Bead sort works by first placing the numbers to be sorted on a horizontal rod or wire. Each number is represented by a certain number of beads stacked on top of each other. The beads are then allowed to fall through a series of vertical rods, with each rod representing a digit in the numbers. As the beads fall, they are collected in sorted order, resulting in a sorted list of numbers.

3. What are the advantages of using bead sort?

One advantage of using bead sort is that it is a simple sorting algorithm that can be easily implemented without the need for specialized knowledge or tools. It also has a relatively fast average case time complexity of O(n), making it a efficient option for sorting small lists of numbers.

4. What are the limitations of bead sort?

Bead sort has a worst case time complexity of O(n^2), which makes it inefficient for sorting large lists of numbers. It also requires a physical set-up with rods and beads, making it impractical for use in digital environments.

5. Are there any variations of bead sort?

Yes, there are variations of bead sort that use different physical representations such as rods and marbles or balls. There are also digital versions of bead sort that use pixels or cells to represent the numbers being sorted. These variations may have different time complexities and efficiencies compared to traditional bead sort.

Similar threads

  • Programming and Computer Science
Replies
10
Views
3K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
29
Views
3K
Replies
2
Views
1K
  • STEM Career Guidance
Replies
2
Views
528
  • STEM Career Guidance
Replies
33
Views
2K
  • STEM Academic Advising
Replies
4
Views
885
Replies
2
Views
3K
  • Science Fiction and Fantasy Media
Replies
10
Views
2K
  • STEM Academic Advising
Replies
6
Views
2K
Back
Top