Spaghetti Sort (2018)
advent.morr.cc
advent.morr.cc
Start by holding the broom horizontally (so that the shaft is parallel to the floor) and support it between the thumb and fingers of each hand with your hands held about a meter apart. The palms of your hands should be facing each other, fingers and thumb flat in vertical plane, with the thumbs sticking out to make cradles for the broomstick.
side view
////
/\o////
\ /
\ /
As you draw your hands together there will be an unequal amount of friction between the broomstick and each hand. The side that is further from the center of mass of the broom will have less friction. The side with less friction will slide. This changes the weight distribution between your two hands until the friction on the sliding hand has increased [enough] past the friction on the non-sliding hand. When that happens, the sliding hand stops sliding and the non-sliding hand starts sliding. The process alternates from hand to hand until, at the end, your hands are touching and the center of mass of the broomstick is [close enough to exactly] between them.
- - - -
Derp, it's on the youtube: https://www.youtube.com/watch?v=B4axmjVFsK8
Stephen Fry...
#!/bin/bash
for int in $@; do # input must be a list of positive integers
(sleep $int; echo $int) &
done; wait
[0] https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
If it is scheduled by the kernel then the complexity is hidden in the scheduling algorithm.
For sleep sort, the time taken is a constant function of the size of the list; it only depends on the value of the maximum element of the list. T = max(list) + smaller terms associated with scheduling timeouts. So, it's O(max(list)). Although, the "smaller terms" I'm ignoring blow up when the size of the list exceeds your computer's resources. I'd guess that spaghetti-sort is O(sum(list)).
> The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003-2007), at which point it was superseded by the Completely Fair Scheduler.
https://en.wikipedia.org/wiki/Completely_Fair_Scheduler
> The fair queuing CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the runqueue is implemented as a red-black tree.
If you ignore the usual meaning of linear time and restrict yourself to sorting lists of numbers that will fit in your hand, then spaghetti sort always runs in less time that however long it takes to sort the maximum amount of spaghetti you can hold in your hand. i.e. constant time.
Spaghetti sort seems to be an analogue variant of radix sort.
0: Manufacture a pair of hands big enough to hold all the spaghetti you'll need in the later steps.
Does this step take linear time as well?
When algorithms do require extra memory, they state this requirement as the space complexity.
This 2007 blog article is hilarious from today's view: https://nwinton.wordpress.com/2007/06/24/the-iphones-bigger-...
As others have mentioned, your hand can only hold so much pasta (about 10^2). For n=10^2, a computer will easily win. So I'll need to abuse logic a bit...
Let's assume - The hand is large enough to hold all the pasta. - The linear time operations take about 1 second total (breaking, removing, transcribing).
Benchmarks[1] for sorting show TencentSort (which looks like it's based on a O(nlog(n)) merge sort[2]?) can sort 100TB in 100 seconds, for 100 byte records. So about 10^12 records/minute.
c*(n*log(n))=time
n=10^12
time=1min
c~=1/10^12 minute
Solving:
(1/10^12)*n*log(n)=n
(1/10^12)*log(n)=1
log(n)=10^12
log(n)=1,000,000,000,000
n=2^1,000,000,000,000
A piece of spaghetti is about 1 gram. 2^1,000,000,000,000 grams is significantly larger than the mass of the observable universe. (10^56 grams, or 2^186 grams).
How long is that?
2^56 seconds is the age of the universe.
Intuitively, this sort of makes sense. For extremely large values of n, log(n) is dwarfed by n so much that it looks like just n. A computer performing a single step of the sort operation is several orders of magnitude faster than any of the human operations. It takes insanely long, and an insanely large n for spaghetti sort to catch up.
[1] https://sortbenchmark.org/ [2] http://sortbenchmark.org/TencentSort2016.pdf
Also, if you have lots of tiny pieces, and some longer pieces, the bundle won't form a nice column. You'd have to have a minimum length to help form the bundle, then add your number to that minimum length.
It seems so strange to me that there are so many algorithms that our brains use, that we don't fully understand yet. I self reflect all the time about my own decision making, and the way I see, hear, think, and remember. We all do these things, but what are the underlying algorithms? What data is being stored, how is it represented, and how is it being compared, manipulated, and updated?
EDIT: I thought couldn't remember the name, turns out it's actually bead sort aka gravity sort. Sometimes things are as simple as they seem.
The algorithm works for any input list, so I will pick a hard class of inputs: The list shall be some permutation of [1, 2, 3, ..., n].
The sum of the spaghetti lengths is 1+2+3+...+n, which is in O(n^2). You need to spend O(n^2) effort to gather the flour to make the spaghetti. Hence this sets a lower bound on the overall algorithm.
I think you could take the sort values, use them as memory addresses (or array offsets), and write the original index of each value into its corresponding pointer, then go back and iterate through that entire chunk of memory to find each of them. That might technically be linear time? Really N + M, where N is the number of values and M is their full range. It would have hilariously inefficient usage of memory and a pretty low cap on the range of possible sort values, but still.
I think you can also use a large bitmap if all you want is sorted values.
BTW, Bloom filters work on a quite similar idea, and they come in handy in database setups.
Imagine the graph is drawn on an handkerchief. Pick any vertex of the graph and let the handkerchief "fall" around it.
Now, with your other hand, pick the point which is the lowest (farthest away from the one in your hand). The handkerchief falls again around that new point.
Again, with your other hand pick the point which is the lowest. The two points in your hands are those farthest away.
(didn't find the reference of this algo, so it may be wrong; just correct me if it is)
Unforunately, it is not correct even then. Here is a counterexample:
A
|
B-C-D
Was fun to think about, though!
For example, a sorted linked list behaves almost exactly like this spaghetti column.
So, under the assumtions, the overall algorithm does complete in constant time.
We know. No one is proposing this be used to actually sort. It's funny because it is a linear time algorithm, but incredibly inefficient and impractical in real life.
Found one: http://www.softouch.on.ca/kb/data/Scan-130202-0003.pdf
Helped me understand why people default to such an inefficient algorithm when learning about sorting.
One could imagine making a CPU which has a similar single-cycle instruction, ie in a list of n<8 numbers find the insertion point of x. Similar to single-cycle adders and multipliers.
Yeah that's kind of cheating, but it would be close to how we do it.
You don't need to do this if you use a doubly-linked list, yet the algorithm is still quadratic, so this cannot possibly be the reason why it is quadratic. It is quadratic because you are (in the worst case) comparing every element in the list with every other element in the list.