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

31–40 of 55 posts

Re: Spaghetti Sort (2018)

#31

Post by _bxg1 »

I was thinking about how this (and other "physical sorts" mentioned by commenters) sorts instantly by using a physical property of the members, and I began to consider what the computer equivalent would be of "physical sorting".

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.

Re: Spaghetti Sort (2018)

#32

Post by ladberg »

_bxg1 wrote: post #31

I was thinking about how this (and other "physical sorts" mentioned by commenters) sorts instantly by using a physical property of the members, and I began to consider what the computer equivalent would be of "physical sorting". 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 th…

This is basically a 1-deep radix sort, where each memory location is a bucket.

Re: Spaghetti Sort (2018)

#33

Post by FartyMcFarter »

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 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?

Re: Spaghetti Sort (2018)

#35

Post by leni536 »

Reminds me of Dijkstra's algorithm explained with threads and beads. The nodes are represented by beads and the weighted edges are represented by threads between the beads with lengths equal to the weights of the corresponding edges. You put down all the beads on a table close to each other and you start lifting up one of the beads. The order the beads leaving the table is the same as the order of visited nodes in Dijkstra's algorithm.

Re: Spaghetti Sort (2018)

#36

Post by aasasd »

_bxg1 wrote: post #31

I was thinking about how this (and other "physical sorts" mentioned by commenters) sorts instantly by using a physical property of the members, and I began to consider what the computer equivalent would be of "physical sorting". 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 th…

It can really be used if the range is small, though I'm not sure I've met such a case where it would be practical. Back in the day, a notable feature of this algo was that it does zero comparisons, which were slower than straightforward crunching.

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.

Re: Spaghetti Sort (2018)

#37

Post by mirekrusin »

tlb wrote: post #12
clktmr wrote: post #7

Has someone calculated at what n I will sort faster than my PC?

Pretty big. You're comparing quicksort at O(n log n) to hand at O(n). A computer is about a billion times faster per operation, so log n = 1 billion, or n = 2^billion.

Hey, but you don't need to do it by hand, you can simulate physics of spaghetti, right? :)

Re: Spaghetti Sort (2018)

#38

Post by saagarjha »

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's psuedo-polynomial: https://en.wikipedia.org/wiki/Pseudo-polynomial_time. The Linux scheduler is O(n log(n)) if I remember correctly.

Re: Spaghetti Sort (2018)

#39

Post by wiz21c »

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

Re: Spaghetti Sort (2018)

#40

Post by piterdevries »

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

Simple optimization sleep $int / $maxIntInList
Post reply on HN