4 ms·

>you can let the world do the work for you. Reminds me of the Spaghetti Sorting algorithm. https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.o

>you can let the world do the work for you. Reminds me of the Spaghetti Sorting algorithm. https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.org/wiki/Spaghetti_sort

bravetraveler 2y ago
That's how some 'trick' card decks work, for anyone unfamiliar
marhee 2y ago
Interesting but I am not sure I understand this: >> contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n). How is the contact-and-removal operation constant time? How can that assumption ever be true? If you use a parallel processor like human vision or human feel (ie. which pressure nerve activates on the hand) it may appear constant, but if you use a computer it would be n right (as you would need to check n slots). Wouldn't either defy O(n)?
- thfuran 2y ago
  You're talking about some other kind of sort.
- dahart 2y ago
  The analog algorithm described is not described for digital computer. It’s an amusing theoretical thought experiment and not a recipe for actual fast sorting. It’s O(n) when you use your hand for contact and removal. I don’t know if it’s possible to implement spaghetti sort on a computer, maybe not, but I guess if it were possible, it would probably at least require n processors to sort n elements. Maybe the nearest analogy on digital computers is radix sort.
  - Izkata 2y ago
    Radix sort is probably the closest usable one, but a more direct translation would probably be sleep sort.
    - dahart 2y ago
      Oh yeah I forgot about sleep sort, that is similar and also more in the same spirit as spaghetti sort. ;)
- sdwr 2y ago
  You can simplify the "human hand" to a rigid metal sheet that comes down from the top and stops on the highest object. Still constant time, but no "parallel processing" needed. The point is that reality itself is highly parallel
  - lambdaxyzw 2y ago
    I wonder if the removal operation is not actually O(sqrt(n)). Depending on the way we structure thought experiment of course. But as the pile of spaghetti gets bigger, the act of picking the largest one is constrained by: 1. how fast your hand can reach for the next spaghetti piece - on average proportional to the radius of the pile of spaghetti, which is proportional to sqrt(n). 2. to actually notice the biggest piece, you need to again wait for a time proportional to sqrt(n) - light propagation is not instant. So if we start thinking about this algorithm more like a computer scientist would (how fast it is as n grows to the infinity) it doesn't seem to be O(n) IMO.
- posix86 2y ago
  Depends on the mathematical framework you're working with.... there's a genre in theoretical compsci that deals with parallel algorithms, and as a toy example, I remember an O(1) sorting algo (given O(n^2) processors). This example is more fun than anything, but ofc in general you're free what constraints you subject your statements to.
JKCalhoun 2y ago
Spaghetti Sorting is just one of the Analog Gadgets called out in Dewdney's "The Armchair Universe" (originally in his Computer Recreations column in "Scientific American"). There are many other cool ones (beginning on page 28): https://archive.org/details/armchairuniverse0000dewd_x2e7/ https://archive.org/details/armchairuniverse0000dewd_x2e7/
tshaddox 2y ago
Of course, all computation is just setting up some physical stuff in such a way that, after the laws of physics play themselves out for a while, that physical stuff will be in a new state, and you'll be able to interpret your desired result from that new state.

>you can let the world do the work for you. Reminds me of the Spaghetti Sorting algorithm. https://en.wikipedia.org/wiki/Spaghetti_sort https://en.wikipedia.org/wiki/Spaghetti_sort

bravetraveler 2y ago

That's how some 'trick' card decks work, for anyone unfamiliar

marhee 2y ago

Interesting but I am not sure I understand this: >> contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n). How is the contact-and-removal operation constant time? How can that assumption ever be true? If you use a parallel processor like human vision or human feel (ie. which pressure nerve activates on the hand) it may appear constant, but if you use a computer it would be n right (as you would need to check n slots). Wouldn't either defy O(n)?

thfuran 2y ago
You're talking about some other kind of sort.
dahart 2y ago
The analog algorithm described is not described for digital computer. It’s an amusing theoretical thought experiment and not a recipe for actual fast sorting. It’s O(n) when you use your hand for contact and removal. I don’t know if it’s possible to implement spaghetti sort on a computer, maybe not, but I guess if it were possible, it would probably at least require n processors to sort n elements. Maybe the nearest analogy on digital computers is radix sort.
- Izkata 2y ago
  Radix sort is probably the closest usable one, but a more direct translation would probably be sleep sort.
  - dahart 2y ago
    Oh yeah I forgot about sleep sort, that is similar and also more in the same spirit as spaghetti sort. ;)
sdwr 2y ago
You can simplify the "human hand" to a rigid metal sheet that comes down from the top and stops on the highest object. Still constant time, but no "parallel processing" needed. The point is that reality itself is highly parallel
- lambdaxyzw 2y ago
  I wonder if the removal operation is not actually O(sqrt(n)). Depending on the way we structure thought experiment of course. But as the pile of spaghetti gets bigger, the act of picking the largest one is constrained by: 1. how fast your hand can reach for the next spaghetti piece - on average proportional to the radius of the pile of spaghetti, which is proportional to sqrt(n). 2. to actually notice the biggest piece, you need to again wait for a time proportional to sqrt(n) - light propagation is not instant. So if we start thinking about this algorithm more like a computer scientist would (how fast it is as n grows to the infinity) it doesn't seem to be O(n) IMO.
posix86 2y ago
Depends on the mathematical framework you're working with.... there's a genre in theoretical compsci that deals with parallel algorithms, and as a toy example, I remember an O(1) sorting algo (given O(n^2) processors). This example is more fun than anything, but ofc in general you're free what constraints you subject your statements to.

JKCalhoun 2y ago

Spaghetti Sorting is just one of the Analog Gadgets called out in Dewdney's "The Armchair Universe" (originally in his Computer Recreations column in "Scientific American"). There are many other cool ones (beginning on page 28): https://archive.org/details/armchairuniverse0000dewd_x2e7/ https://archive.org/details/armchairuniverse0000dewd_x2e7/

tshaddox 2y ago

Of course, all computation is just setting up some physical stuff in such a way that, after the laws of physics play themselves out for a while, that physical stuff will be in a new state, and you'll be able to interpret your desired result from that new state.