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

21–30 of 55 posts

Re: Spaghetti Sort (2018)

#21

Post by lann »

bashinator wrote: post #17

This reminds me of my favorite joke algorithm, sleepsort[0]. A trivial implementation looks like this: #!/bin/bash for int in $@; do # input must be a list of positive integers (sleep $int; echo $int) & done; wait I'm not quite sure how to describe it in terms of big O notation. [0] https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

If the sleep is some kind of busy wait then I think it is something like O(m*n) where m=max number.

If it is scheduled by the kernel then the complexity is hidden in the scheduling algorithm.

Re: Spaghetti Sort (2018)

#22

Post by nayuki »

I believe the worst-case asymptotic time complexity of spaghetti sort is O(n^2).

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.

Re: Spaghetti Sort (2018)

#23

Post by anonytrary »

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.

> The inefficiency in computers is that you need to slide all of the values down a place one by one as you insert numbers.

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.

Re: Spaghetti Sort (2018)

#24

Post by anonytrary »

bashinator wrote: post #17

This reminds me of my favorite joke algorithm, sleepsort[0]. A trivial implementation looks like this: #!/bin/bash for int in $@; do # input must be a list of positive integers (sleep $int; echo $int) & done; wait I'm not quite sure how to describe it in terms of big O notation. [0] https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

It should remind you of sleep sort, because spaghetti sort is the spatial version of sleep sort.

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)).

Re: Spaghetti Sort (2018)

#25

Post by pontifier »

Sometimes it might not be possible to easily determine which is the longest piece. For inctance if the pieces are on opposite sides ov the bundle, and are very close in height.

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?

Re: Spaghetti Sort (2018)

#27

Post by bashinator »

anonytrary wrote: post #24
bashinator wrote: post #17

This reminds me of my favorite joke algorithm, sleepsort[0]. A trivial implementation looks like this: #!/bin/bash for int in $@; do # input must be a list of positive integers (sleep $int; echo $int) & done; wait I'm not quite sure how to describe it in terms of big O notation. [0] https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

It should remind you of sleep sort, because spaghetti sort is the spatial version of sleep sort. 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…

Aha so a sleep sort is translating the operation into the time domain In essentially the same way that spaghetti sort translates into the spatial domain! Thank you.

Re: Spaghetti Sort (2018)

#28

Post by c3534l »

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.

Re: Spaghetti Sort (2018)

#29

Post by c3534l »

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.

Re: Spaghetti Sort (2018)

#30

Post by fenomas »

jakear wrote: post #18
empath75 wrote: post #5

Earlier quoted context omitted.

The sorting doesn’t happen in constant time. The actual sort happens by hand as you take out the largest pieces first. Until you do that, they aren’t in linear order.

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.
Post reply on HN