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

11–20 of 55 posts

Re: Spaghetti Sort (2018)

#11

Post by carapace »

My favorite "analog computer" example is finding the balance point of a broom or mop.

Start by holding the broom horizontally (so that the shaft is parallel to the floor) and support it between the thumb and fingers of each hand with your hands held about a meter apart. The palms of your hands should be facing each other, fingers and thumb flat in vertical plane, with the thumbs sticking out to make cradles for the broomstick.

     side view

          ////
      /\o////
      \    /
       \  /
Once it's set up, all you do is gently bring your hands towards each other until they are touching, palm to palm. The broom will remain balanced on your hands the entire time.

As you draw your hands together there will be an unequal amount of friction between the broomstick and each hand. The side that is further from the center of mass of the broom will have less friction. The side with less friction will slide. This changes the weight distribution between your two hands until the friction on the sliding hand has increased [enough] past the friction on the non-sliding hand. When that happens, the sliding hand stops sliding and the non-sliding hand starts sliding. The process alternates from hand to hand until, at the end, your hands are touching and the center of mass of the broomstick is [close enough to exactly] between them.

- - - -

Derp, it's on the youtube: https://www.youtube.com/watch?v=B4axmjVFsK8

Stephen Fry...

Re: Spaghetti Sort (2018)

#12

Post by tlb »

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.

Re: Spaghetti Sort (2018)

#13

Post by robbya »

As an exercise, when could spaghetti sort beat computers?

As others have mentioned, your hand can only hold so much pasta (about 10^2). For n=10^2, a computer will easily win. So I'll need to abuse logic a bit...

Let's assume - The hand is large enough to hold all the pasta. - The linear time operations take about 1 second total (breaking, removing, transcribing).

Benchmarks[1] for sorting show TencentSort (which looks like it's based on a O(nlog(n)) merge sort[2]?) can sort 100TB in 100 seconds, for 100 byte records. So about 10^12 records/minute.

  c*(n*log(n))=time
  n=10^12
  time=1min
  c~=1/10^12 minute
(assume log base 2)

Solving:

  (1/10^12)*n*log(n)=n
  (1/10^12)*log(n)=1
  log(n)=10^12
  log(n)=1,000,000,000,000
  n=2^1,000,000,000,000
How big is that?

A piece of spaghetti is about 1 gram. 2^1,000,000,000,000 grams is significantly larger than the mass of the observable universe. (10^56 grams, or 2^186 grams).

How long is that?

2^56 seconds is the age of the universe.

Intuitively, this sort of makes sense. For extremely large values of n, log(n) is dwarfed by n so much that it looks like just n. A computer performing a single step of the sort operation is several orders of magnitude faster than any of the human operations. It takes insanely long, and an insanely large n for spaghetti sort to catch up.

[1] https://sortbenchmark.org/ [2] http://sortbenchmark.org/TencentSort2016.pdf

Re: Spaghetti Sort (2018)

#14

Post by war1025 »

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.

Re: Spaghetti Sort (2018)

#15

Post by Ecco »

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.

Re: Spaghetti Sort (2018)

#16

Post by war1025 »

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.

I don't remember the specifics of it, and maybe there were added restrictions, but I do remember working it out to be O(nlog n). Not something I've thought about in a long time.

Re: Spaghetti Sort (2018)

#17

Post by bashinator »

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

Re: Spaghetti Sort (2018)

#18

Post by jakear »

empath75 wrote: post #5
ziofill wrote: post #2

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

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.

Re: Spaghetti Sort (2018)

#19

Post by kadoban »

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.

Probably depends what you're doing with it, physically, but if you were running insertion sort manually it'd be very intuitive to do something like binary search to find the correct insertion point. That would make it O(n lg n).

Re: Spaghetti Sort (2018)

#20

Post by madmax96 »

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.

Post reply on HN