Bead Sort | Hacker News Reader

Bead Sort

karthikkaranth.me

99 pointskkaranth41 comments

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.

1. https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

> (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.

puts on pedant’s hat

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

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.

Very interesting! Thank you for putting on your pedant hat!

"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.

Narbonic got close http://narbonic.com/wordpress/wp-content/uploads/2006/12/061...

That sounds like a quote from a Douglas Adam book.

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.

I'm taking a graduate algorithms class right now, and stumbled upon the bead sort wiki page.

These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model

> only applies when using the traditional greater/less than comparison model

What do you mean by this?

The bound is a bound on comparaison sort not a general bound on sorting.

If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.

Right, comparative and non-comparative sorting algorithms.

I'd say radix sort is the canonical example of a non-comparative sorting algorithm.

I'm surprised that this was only discovered in 2002. [0] Neat.

Reminds me of spaghetti sort [1], but bead sort is much cleverer.

[0] https://en.wikipedia.org/wiki/Bead_sort

[1] https://en.wikipedia.org/wiki/Spaghetti_sort

I love the runtime analysis of Spaghetti sort:

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

Yup, my bad. Fixed now. Random colors is the default in the matter.js renderer(and I'll admit it looks very pretty)

What if you colored each each row of beads differently? Then you'd have some idea of how each number contributes to each column once it settles.

Nice, it's a cool illustration.

> (and I'll admit it looks very pretty)

It does look better with all the colors, but it distracts from what you are showing.

Thank you sir, I only understood after reading this!

This needs a pause button, or at least some way to view the starting configuration. It's hard to think when everything is moving.

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.

[1] https://www.researchgate.net/publication/220329153_An_Optima...

Nothing better than sleep sort.

I present for your consideration, Quantum Bogosort:

http://wiki.c2.com/?QuantumBogoSort

I wasn’t familiar with the sleep sort, this is the context I’ve found: https://www.quora.com/What-is-sleep-sort

Then you haven't heard of Stalin Sort

But sorting implies just changing the order of elements not eliminating elements. Stalin sort is not a true sorting algorithm.

What about ThanosSort: just delete half the array elements until the remaining elements are sorted.

This is delightful! The actual implementation in a digital system seems to be a special case of radix sort, but it doesn't take away from the fun :)

Is it fast? I mean like, compared to QuickSort or others. Honestly asking -- I've not heard of Bead Sort before.

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).

sorry if its offtopic but does anyone here have any experience with librarysort?

https://en.wikipedia.org/wiki/Library_sort

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.

Go Utes! Loved the animation! Thanks for sharing.

Radix sort and counting sort are what ppl should be using.

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

Visual is nice though

The page does not claim that it is novel. Indeed it cites Wikipedia which in turn cites a primary source from 2002.

Reply on news.ycombinator.com