Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Spaghetti Sort (2018)

advent.morr.cc

Post reply on HN
Print view View original

41–50 of 55 posts

Re: Spaghetti Sort (2018)

#41

Post by jansan »

c3534l wrote: post #28
mooshmoosh wrote: post #6

Linear time O(n) means that as you keep adding numbers to sort, the time taken is bounded by a linear function of how many numbers you have. Since there is an upper bound on the number of spaghetti strands you can hold in your hand, eventually you need to "Slam their lower sides on the table" in batches, and then merge sort the results. However because unlike in merge sort there is an upper bound on the size of the s…

It is an ideal hand on an ideal table.

Totally OT, but that reminds me of the first iPhone advertisements where they used exceptionally large hands to make the iPhone appear small. Quite funny if you think how smartphone sizes have developed since.

This 2007 blog article is hilarious from today's view: https://nwinton.wordpress.com/2007/06/24/the-iphones-bigger-...

Re: Spaghetti Sort (2018)

#42

Post by chronial »

mooshmoosh wrote: post #6

Linear time O(n) means that as you keep adding numbers to sort, the time taken is bounded by a linear function of how many numbers you have. Since there is an upper bound on the number of spaghetti strands you can hold in your hand, eventually you need to "Slam their lower sides on the table" in batches, and then merge sort the results. However because unlike in merge sort there is an upper bound on the size of the s…

Asymptotic times usually have assumptions on the problem size. On computers, you assume that memory access is constant time, which violates the laws of physics for arbitrarily large N.

Re: Spaghetti Sort (2018)

#43

Post by random_savv »

madmax96 wrote: post #20
mooshmoosh wrote: post #6

Linear time O(n) means that as you keep adding numbers to sort, the time taken is bounded by a linear function of how many numbers you have. Since there is an upper bound on the number of spaghetti strands you can hold in your hand, eventually you need to "Slam their lower sides on the table" in batches, and then merge sort the results. However because unlike in merge sort there is an upper bound on the size of the s…

You can replace the hand with any device that holds the spaghetti. This really is an O(n) algorithm. Spaghetti sort seems to be an analogue variant of radix sort.

I came here to write this comment. Glad somebody beat me to it! +1

Re: Spaghetti Sort (2018)

#44

Post by krajzeg »

wiz21c wrote: post #39

This reminds me of an algo to find the 2 points farthest away in a graph. 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 tw…

Your algorithm doesn't really work for graphs - it actually treats the vertices as a set of points (the edges are not taken into account, you're just looking for the largest Euclidean distance between two points).

Unforunately, it is not correct even then. Here is a counterexample:

    A
    |
  B-C-D
You have points laid out like this, and: AC > CD=BC, AD=AB Was fun to think about, though!

Re: Spaghetti Sort (2018)

#45

Post by krajzeg »

fenomas wrote: post #30
jakear wrote: post #18

Earlier quoted context omitted.

They are linear in order – from the top. The final step is simply reformatting the results.

They're not in order, they're just in a data structure where the largest remaining element can be extracted in O(1) time. One can't say anything useful about any other elements of the list.

It's fun to think about: you have a structure which allows you to iterate all elements in order in O(n) time. Isn't this in many ways equivalent to the structure being "sorted", even if it doesn't have all the properties of a sorted array (like being able to get the nth element in O(1))?

For example, a sorted linked list behaves almost exactly like this spaghetti column.

Re: Spaghetti Sort (2018)

#46

Post by rjmunro »

krajzeg wrote: post #44
wiz21c wrote: post #39

This reminds me of an algo to find the 2 points farthest away in a graph. 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 tw…

Your algorithm doesn't really work for graphs - it actually treats the vertices as a set of points (the edges are not taken into account, you're just looking for the largest Euclidean distance between two points). Unforunately, it is not correct even then. Here is a counterexample: A | B-C-D You have points laid out like this, and: AC > CD=BC, AD=AB Was fun to think about, though!

Are you supposed to keep going until you go back to the same pair? So you would go C, A, B, D, B?

Re: Spaghetti Sort (2018)

#47

Post by magicalhippo »

Ecco wrote: post #15
war1025 wrote: post #14

Related: One of my favorite realizations back in college was that insertion sort in real life is an optimal sort. The inefficiency in computers is that you need to slide all of the values down a place one by one as you insert numbers. In real life, the values just get shoved down in parallel. Helped me understand why people default to such an inefficient algorithm when learning about sorting.

Sorry mate but that’s just plain wrong... What takes quadratic time in insertion sort is not the insertions but all the comparisons. Otherwise we’d have linear time sort using linked lists.

But if the list of numbers is small enough, our brains essentially finds the insertion position in a single operation.

One could imagine making a CPU which has a similar single-cycle instruction, ie in a list of nYeah that's kind of cheating, but it would be close to how we do it.

Re: Spaghetti Sort (2018)

#48

Post by wubblebubble »

c3534l wrote: post #29
ziofill wrote: post #2

This is silly. The linear parts are just I/O, and the actual sorting happens in constant time by magic.

> This is silly. 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.

i've actually implemented a similar spatial-sort method used within an analog computer for some industrial controllers. so it does have some real life applications.

Re: Spaghetti Sort (2018)

#49

Post by Enginerrrd »

c3534l wrote: post #28
mooshmoosh wrote: post #6

Linear time O(n) means that as you keep adding numbers to sort, the time taken is bounded by a linear function of how many numbers you have. Since there is an upper bound on the number of spaghetti strands you can hold in your hand, eventually you need to "Slam their lower sides on the table" in batches, and then merge sort the results. However because unlike in merge sort there is an upper bound on the size of the s…

It is an ideal hand on an ideal table.

Yeah, and IMO it's not even a good theoretical way to look at an analog computer. The hard part that will eat up time is differentiating the small differences between spaghetti to arbitrary precision. Analog systems still have to deal with signal to noise ratio issues, which affects the decision criteria here as in, "which one of these is the next longest?".

Re: Spaghetti Sort (2018)

#50

Post by madmax96 »

FartyMcFarter wrote: post #33
madmax96 wrote: post #20

Earlier quoted context omitted.

You can replace the hand with any device that holds the spaghetti. This really is an O(n) algorithm. Spaghetti sort seems to be an analogue variant of radix sort.

I suppose one could add a step 0 to the algorithm: 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?

Does it take O(n) time to manufacture computer memory? I don’t know, but it doesn’t affect the runtime of algorithms.
Post reply on HN