9 ms·
Bead Sort
- adenozine 6y agoI'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
- Sharlin 6y agoThe page does not claim that it is novel. Indeed it cites Wikipedia which in turn cites a primary source from 2002.
- MaxBarraclough 6y agoI'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 https://en.wikipedia.org/wiki/Bead_sort [1] https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.org/wiki/Spaghetti_sort
- kkaranth 6y agoI 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).
- laszlokorte 6y agoActually 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.
- ladberg 6y agoIn 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.
- 29athrowaway 6y agoNothing better than sleep sort.
- nvader 6y agoI present for your consideration, Quantum Bogosort: http://wiki.c2.com/?QuantumBogoSort http://wiki.c2.com/?QuantumBogoSort
- li4ick 6y agoThen you haven't heard of Stalin Sort
- 29athrowaway 6y agoBut sorting implies just changing the order of elements not eliminating elements. Stalin sort is not a true sorting algorithm.
- cratermoon 6y agoWhat about ThanosSort: just delete half the array elements until the remaining elements are sorted.
- thih9 6y agoI wasn’t familiar with the sleep sort, this is the context I’ve found: https://www.quora.com/What-is-sleep-sort https://www.quora.com/What-is-sleep-sort
- rmelhem 6y agosorry if its offtopic but does anyone here have any experience with librarysort? https://en.wikipedia.org/wiki/Library_sort https://en.wikipedia.org/wiki/Library_sort
- cratermoon 6y agoIt 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.
- munk-a 6y agoI 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_of_algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...
- kkaranth 6y agoI'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
- MaxBarraclough 6y ago> only applies when using the traditional greater/less than comparison model What do you mean by this?
- brmgb 6y agoThe 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.
- MaxBarraclough 6y agoRight, comparative and non-comparative sorting algorithms. I'd say radix sort is the canonical example of a non-comparative sorting algorithm.
- ogre_codes 6y agoThis 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.
- kkaranth 6y agoYup, my bad. Fixed now. Random colors is the default in the matter.js renderer(and I'll admit it looks very pretty)
- ogre_codes 6y agoNice, 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.
- kmill 6y agoWhat 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.
- ismayilzadan 6y agoThank you sir, I only understood after reading this!
- deleted 6y ago[deleted]
- p1mrx 6y agoThis needs a pause button, or at least some way to view the starting configuration. It's hard to think when everything is moving.
- google234123 6y agoGo Utes! Loved the animation! Thanks for sharing.
- vimax 6y agoThe 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_Optimal_Hardware-Algorithm_for_Sorting_Using_a_Fixed-Size_Parallel_Sorting_Device https://www.researchgate.net/publication/220329153_An_Optima...
- cgijoe 6y agoIs it fast? I mean like, compared to QuickSort or others. Honestly asking -- I've not heard of Bead Sort before.
- nimih 6y agoRuntime 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.
- t0astbread 6y agoPreparation 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).
- dreamcompiler 6y agoThe 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).
- xiaodai 6y agoRadix sort and counting sort are what ppl should be using.
- plasticchris 6y agoThis 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 :)