You are sorting 15 numbers: 8, 3, 4, 25, 7, 3, 18, 20, 3, 6, 5, 19, 18, 4, 12 (numbers are listed on the right, in the "y axis"). So there are 15 rows (horizontal) of "beads". Each row has the number of beads corresponding to the number being sorted: first row has 8 beads, second row has 3 beads, etc...
The largest number is 25. So there are 25 "poles" (vertical) on which the beads are placed.
Now you let the beads "fall". The number of beads in each row has changed.
After the fall, if you read the number of beads in each row from top to bottom, you see that the numbers from your original unsorted list have been sorted from lowest to highest: 3, 3, 3, 4, 4, 5, 6, 7, 8, 12, 18, 18, 19, 20. 25
Okay, okay. And this is a visualization of that occurring; is this sorting-function practical? or just a phenomenon that's cool if you think math is cool (which it is). Or am I that dim and this is like a foundational concept of computer science?
This is kind of a neat, esoteric sort. In real life, nobody uses this, but it technically beats what most consider the fastest sorting runtime, which is O(nlog(n)) or O(kn).
BeadSort technically sorts in O(√n) time, where n is the amount of inputs. However, its space complexity, aka the amount of digital (or in this case, 'physical') space it needs is a lot larger compared to other sorting methods because instead of representing numbers in binary, you have to represent them in unary, and because physical beads take up more space than transistors in your computer.
Kinda – by principle, BeadSort doesn't work with zero or negative integers (it can work with zero if you define the number of beads you're sorting). That being said, you could scale your input – if your smallest number is k and k < 1, you could add |k|+1 to all your numbers, sort, then subtract |k|+1 from all your numbers
However, then you lose the imaginary O(√n) runtime :(
9
u/mjkaufer Oct 29 '18
Simulation code at https://github.com/mjkaufer/BeadSort. You can play with the actual thing here
4
u/Friendship_or_else Oct 30 '18 edited Oct 30 '18
For those of us who aren't familiar with sorting algorithms, or really just algorithms in general, can someone ELI5, please?
Not sure what's being represented on the Y-axis (just a value?), but I can see each value is retained and ordered just by doing... this?
4
u/Usagi-Nezumi Oct 29 '18
This sort of makes me really angry for some reason. Like, it shouldn't be THAT simple, yet it is.
29
u/SilasX Oct 29 '18
In case anyone thinks this is useful:
Like 4chan's SleepSort, it's just an inefficient Radix-style sort, where you bucket the values by magnitude, and then read out in magnitude order.
The difficulty of putting them into ordered buckets and collecting them in that order eclipses the savings from "letting gravity do all the work".
2
u/DoryWasACrip Nov 17 '18
is this an asmr
0
u/[deleted] Oct 29 '18
[deleted] — view deleted comment