Talk:Spaghetti sort

Algorithm explanation

How is this any different from Bead Sort except you call it spaghetti? As commented already, the time complexity for this algorithm is O(n^2) if anything simply from the phase where you're trying to find the largest strand. Furthermore, the space complexity of this algorithm is O(n^2) because each spaghetti strand is said to have a length (hence lowering them to a flat surface to level them, something you cannot do with "flat" integers) and also a position amongst the other strands. In conclusion, this sorting algorithm is pure rubbish and should probably be removed. -Anon — Preceding unsigned comment added by 198.160.96.7 (talk) 19:31, 24 August 2011 (UTC)

I believe this explanation needs a bit of rewriting; it seems like it should be a fairly simple concept, but I can't follow it.

Spaghetti sort appears to be, from what I can tell so far, just a way to visualize bucket sort. Would this be accurate to say? ~ Booyabazooka 23:12, 11 May 2006 (UTC)

It definitely needs work. It's said to be an "analog" sorting algorithm, ie. if you really are trying to sort spaghetti rods this explains how to do it using your hands. It's not a computer algorithm. It might be possible to translate it into one but then it just becomes the selection sort.

The link to "AK Dewdney's homepage" doesn't seem to yield any information about this sorting method.Friendly Person 15:43, 23 May 2007 (UTC)

Spaghetti sort is described in Dewdney's book The Armchair Universe.

The real trick is that it's massively parallel. Think of the length of each stick as a bit of data, and each point where the tips of a stick contacts the table/hand as a processor. So each processor operates on one data value, in parallell. This parallelism is why it's not practical to implement it on a traditional computer. —Preceding unsigned comment added by 66.168.92.132 (talk) 01:27, 16 October 2007 (UTC)

Definitely needs rewriting, to describe it in terms of computers. 64.91.186.214 (talk) 14:02, 21 March 2008 (UTC)

Why does it have to be described in terms of computers? It's not a computer algorithm. Not every algorithm is. Cairnarvon (talk) 13:10, 23 March 2008 (UTC)

Every algorithm is an algorithm for a theoretic computer. 131.180.159.92 (talk) 14:41, 19 March 2009 (UTC)

But the interesting thing about this algorithm is that it is O(n) in time and space. If you tried to implement it on a theoretical computer (a Turing machine or similar) by simulating rods of spaghetti on a table it would no longer be O(n) time and space because 1 unit of simulated time would take perhaps O(n) units of real time. In other words, by implementing it on a theoretical computer, you remove the one interesting thing about the algorithm. 217.28.34.132 (talk) 11:22, 11 April 2009 (UTC)

This is increadibly stupid. Another completely irrelevant home-made algorithm I just came to think of is to once and for all prepare a (practically) infinitely long tray with sunken insets which fit spaghetti straws. Put all the straws on this tray, tilt it slightly towards the long side and the side with the shortest inset, and then shake for m time until they are all in order. Since m is not n and not necessarily related, this algorithm will finish regardless of n, hence it's O(1)! Now do you see a problem with this algorithm? Yes, it's plain stupid, just like this article. I would vote for removing this nonsense or have someone actually explain it in a scientific (mathematic preferably) way. Regardless, I do realize the difference, but it's like saying that to calculate a certain differential equation, you can let water flow through pipes. Yes, sometimes that works, but it's not calculus, it's a practical example. Just as much as this is not an algorithm, but a practical excercise. Am I the only one to see this difference? Or perhaps someone can explain (after all, this IS wikipedia) what an algorithm really is. According to the article on Algorithms, an algorithm is a "finite list of well-defined instructions for calculating a function". Where's the calculation in this spaghetti article? — Preceding unsigned comment added by 89.160.115.12 (talk) 21:17, 30 May 2011 (UTC)

@89.160.115.12: Algorithms are not necessarily purely mathematical concepts. An algorithm is simply a set of instructions which, if followed, is guaranteed to achieve some goal/solve some problem in finite time. Algorithms must: 1) be finite 2) be unambiguous 3) be guaranteed to give a correct result. Giving someone detailed instructions on how to drive to a bank is a good example of an algorithm. Your example has several problems with it: In order for a spaghetti strand to fall through the correct inset, the strand must not be blocked by other strands, otherwise it could ride on top of larger strands and fall through an incorrect inset (thus producing an incorrect result). This means that you must send one strand of spaghetti down the tray at a time which causes your algorithm to take O(n) time - putting it in line with the family of Counting sorts.

@Booyabazooka: This algorithm is essentially selection sort (possibly a heap sort, depending on how you argue). The difference here is that in this example, removing the largest item from the heap is done in O(1) time instead of O(log n) for the heap sort, or O(n) for the selection sort. As 66.168.92.132 mentioned, this is accomplished be being massively parallel, in a sense. As you lower your hand to find the largest strand of spaghetti, you are effectively testing all n spaghetti strands simultaneously. However, computers can only execute a single command at a time, so they can only test one integer at a time. Thus inside of a computer, this algorithm devolves to a O(n^2) sort. — Preceding unsigned comment added by 66.227.147.72 (talk) 02:30, 16 September 2011 (UTC)

This is possible on a concurrent network. While we all know that comparison sorting algorithms are bounded by O(n log n), that's assuming O(1) processors. From what I understand, this algorithm is interesting because it relaxes the assumption that the number of processors is constant, requiring O(n) processors. There could be any number of ways of "dropping the spaghetti", for instance, send two signals: "terminate", "done" to the first process. Each process should on receiving "terminate" pass "terminate" onto the next, then prepare to accept more input. If the input is less than the stored value, send it to the next process. If the input is greater than the stored value, send the stored value and store the input. If the input is "done", send the stored value and then "done". The last process outputs each value to be sorted in order, and unless I'm mistaken the time complexity is O(n). 129.67.177.114 (talk) 21:13, 11 February 2012 (UTC)

The statement, the algorithm would require multiple processors is wrong. Yes, it would run faster, but that does not mean anything. If the requirement for the multiple processors is that you only then can have your linear time complexity, the author(s) seriously misunderstood the Big O notation. At the heart of the issue is, that asymptotic time complexity does not measure the actual time a computer (or anything really executing the algorithm) would need to complete the task. It gives a measure for how many steps you need until completion of the algorithm. Also the statement, that it has a Time Complexity of O(n) can not be right, since you can show that every purely comparision based sorting algorithm is (average case bahaviour) from Omega(n*log(n)), meaning it is at best in Theta(n*log(n)) in its average case. In all honesty, this article is a joke. You don't measure space complexity -in rods of Spaghetti-. This article is false information and should be completely reworked or deleted.80.130.26.31 (talk) 21:32, 30 December 2014 (UTC)

References

finding m

Missing: finding the largest number to size your full-length spaghetti is also linear in the length of the list, assuming you have someplace to stash the best so far. If you have to mark and rewind (for big numbers when storage is scarce), you could in the worst case have to go through the list twice. Julian Morrison (talk) 00:34, 26 March 2008 (UTC)

Lowering rods is not truly O(1)

Lowering arbitrarily-many rods to the table in O(1) requires an arbitrarily-large hand. Otherwise, it must be done piecemeal, at most some constant c at a time, which would be O(n) overall. Similarly, finding the largest rod takes an arbitrarily-large hand, or must be done piecemeal. So this step would be O(n) as well. But there are n finding steps, so this is an O(n^2) algorithm, not O(n). Rmkeller (talk) 16:20, 26 April 2011 (UTC)

Through a time/space tradeoff, you can simply build a mechanical hand to match the size of your input. Anyways, this is no different than other algorithms which assume the dataset will be small enough to fit within memory. — Preceding unsigned comment added by 66.227.147.72 (talk) 02:59, 16 September 2011 (UTC)

The "large enough" mechanical hand suffers from at least one of two problems. If you've built it in advance to cover the largest problem you'll ever get, then the result is trivial. It's always possible to produce a function in O(n) time when n must be less than some given number, and the inputs come from some finite set, as they must for your "large enough" hand to work. In fact, it's only O(n) because you have to "read" the input. All that's needed is a finite state machine that outputs the sorted set from its final state. (The input will need an end marker.) On the other hand, if you don't limit the problem size in both these ways ahead of time you'll have to potentially build a new machine for each problem you get. The machine is of size at least nxm where n is the number of inputs and m is the size of the longest piece of spaghetti. As far as other algorithms requiring all the input to fit into memory, that's just false. Look up the extensive literature on sorting datasets on magnetic tape. (Knuth Volume 3 is a good reference.) External sorts can be done in n log n time with small finite memory in the machine reading/writing the tapes.

Wtyler (talk) 22:47, 20 September 2011 (UTC)

And you think that magnetic tape is not memory? — Preceding unsigned comment added by 82.211.83.9 (talk) 11:11, 7 October 2014 (UTC)

Second external link

2nd "external link" is dead. — Preceding unsigned comment added by Kwaio (talk • contribs) 22:54, 10 December 2011 (UTC)

Quantum sort?

This has nothing to do with quantum computing. It seems to be just mentioned in a quantum computing presentation? I moved it back to other sorts. Iamfscked (talk) 23:15, 5 January 2012 (UTC)

Maybe Grover's algorithm and similar algorithms that amplify a set of values until the desired one crosses a threshold, analogous to aligning strands of spaghetti until the longest is obvious.--80.192.180.160 (talk) 16:15, 6 October 2013 (UTC)

Space complexity is not O(n)

Space complexity is O(n.m) where n is number of spaghetti and m is number of different spaghetti lengths (m <= n). Required area (on the table or of the hand) is O(n) but the algorithm relies on dimension perpendicular to the table/hand for rod lengths which is O(m). Assuming m is O(n), space complexity is O(n^2). I have also some doubts that "obtaining rod of length X" is an O(1) operation but we can assume they are already prepared. 213.220.251.49 (talk) 19:27, 23 November 2012 (UTC)

Untitled

This algorithm is clearly absurd. For example it claims that it works in O(n) space but if the maximum input number is very large, and the unit length of spaghetti is set too low, the imprecision in the spaghetti snapping step will lead to numbers which are very close being swapped in their spaghetti stick representation. That is, the larger number might have a slightly shorter stick than a smaller number. So clearly the unit length of spaghetti has to scale with the size of the input to be sorted, thus making the space O(n^2). 208.75.23.46 (talk) 20:13, 28 January 2015 (UTC)Mr. 4thDimention

Computer algorithm version

If people like to see this as a computer algorithm, I think the following matches the current textual description. Assuming an array of length n of positive integers.

 input: array of length n


   // Detemine longest spaghetti rod. O(n)
   max = findMax(array)


   // Prepare all rods.
   // spaghetti[i] represents number of rods of length i. O(n)
   spaghetti = new Array[max+1]
   for (i = 0 to n - 1)
     spaghetti[array[i]]++


   // Lower hand and move values to array (back to front).
   // If we discount empty steps (i.e. lowering the hand) this is O(n).
   counter = n - 1;
   for (i = max to 0) { 
     // Take into account duplicates.
     for (rod = 0 to spaghetti[i]) {
       // These lines run exactly n times:
       array[counter] = i
       counter--
     }
   }

Leastdoors (talk) 21:07, 19 August 2015 (UTC)

The algorithm you are describing is Counting sort. I think this is a obviously made up algorithm. In my opinion, unless somebody demonstrates, how the algorithm can be implemented, it should be deleted. To people saying it doesn't have to be executable on a computer: Please don't forget, that this sorting method claims it has O(n) computational complexity. Quoting computational complexity theory: "Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems...". Additionally, you are generally not allowed to pick and choose, what actions are O(1). Any algorithm is O(1), if you take the algorithm itself to be a singular operation. This article tries to write off the need to demonstrate it's complexity by claiming that it need O(n) processors. In that case, please produce the pseudo-code for O(n) threads, that would somehow optimize the sort. --85.140.172.44 (talk) 18:33, 15 May 2018 (UTC)

Content addressable memory

It seems that the process of using physics to place the rods on a table is very similar to using Content-addressable memory. The purpose of content addressable memory is to use hardware to perform a search. Should the article link to that page? 184.146.224.196 (talk) 12:43, 9 May 2021 (UTC)