Spaghetti Sort (2018) • Hacker News Board

Re: Spaghetti Sort (2018)

#51

Post by FartyMcFarter » Tue, Oct 01, 2019, 9:27 PM UTC

madmax96 wrote: post #50

FartyMcFarter wrote: post #33

Earlier quoted context omitted.

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.

But many sorting algorithms work in-place, so they don't require extra memory beyond a small O(1) or O(log n) amount for bookkeeping.

When algorithms do require extra memory, they state this requirement as the space complexity.

Re: Spaghetti Sort (2018)

#52

Post by s_gourichon » Thu, Oct 03, 2019, 6:41 PM UTC

saagarjha wrote: post #38

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.

According to https://en.wikipedia.org/wiki/O(1)_scheduler

> The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003-2007), at which point it was superseded by the Completely Fair Scheduler.

https://en.wikipedia.org/wiki/Completely_Fair_Scheduler

> The fair queuing CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the runqueue is implemented as a red-black tree.

Re: Spaghetti Sort (2018)

#53

Post by s_gourichon » Thu, Oct 03, 2019, 6:48 PM UTC

krajzeg wrote: post #45

fenomas wrote: post #30

Earlier quoted context omitted.

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.

Interesting remark. So, a "data structure where the largest remaining element can be extracted in O(1) time" can be turned into a sorted list in O(n) time.

So, under the assumtions, the overall algorithm does complete in constant time.

Re: Spaghetti Sort (2018)

#54

Post by s_gourichon » Thu, Oct 03, 2019, 7:20 PM UTC

mirekrusin wrote: post #37

tlb wrote: post #12

Earlier quoted context omitted.

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

Reminds me how you can compute pi in a hilariously inefficient yet very interesting way with a physics engine by counting collision of 3 blocks bouncing with one another: https://youtu.be/HEfHFsfGXjs

Re: Spaghetti Sort (2018)

#55

Post by s_gourichon » Sat, Oct 05, 2019, 10:46 AM UTC

wubblebubble wrote: post #48

c3534l wrote: post #29

Earlier quoted context omitted.

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

The traditional mechanical systems in automatic vending machines that tell and sort correct coins from wrong or fake ones are probably of the same class of mechanical "sorting" (rather categorization in this case) systems. "Mechanical coin acceptor" appears to be the established expression for it.