15 ms·
Sleep sort (2011)
- avodonosov 12y agojavascript version (faster): var input = [5, 3, 6, 3, 6, 3, 1, 4, 7]; var timeAxis = []; // Put every element to the corresponding time point. // Time point would hold an array, as we can have // equal elements. for (var i = 0; i < input.length; i++) { elem = input[i]; timeAxis[elem] = [elem].concat(timeAxis[elem] || []); } // skip all empty (UNDEFINED) time points // and contact all the arrays: var sorted = timeAxis.reduce(function (accum, cur) { return cur ? accum.concat(cur) : accum}, []); console.log(sorted)
- avodonosov 12y agoThe speedup is from usage of _virtual time_, which we don't need to wait for.
- deleted 12y ago[deleted]
- codezero 12y agoThis is my new favorite after bogosort. I'm sad nobody has implemented my idea, rock, paper, scissors sort.
- mc_hammer 12y agolmao i actually looked that up, it even has a wikipedia entry. what a good read.
- sebastialonso 12y agoCare to share the look link? Couldn't find it.
- codezero 12y agoI believe they were referring to bogosort: http://en.wikipedia.org/wiki/Bogosort http://en.wikipedia.org/wiki/Bogosort
- maaaats 12y agoMy favorite is spaghetti sort. Make one spaghetti straw per item that is as long as the value of the item. Then take all spaghettis in your hand and put them against a flat surface. Remove the longest one and keep doing that. :)
- kevinwang 12y agoAnd what, exactly, is rock paper scissors sort?
- codezero 12y agoThe comparison function is a game of Rock Paper Scissors with the winner being given the 'greater than' position. Games proceed until all items are in sorted order :)
- antics 12y agoJust to be 100% clear, in case anyone who is new to the field stumbles on this thread, this is NOT breaking math or anything. This is a fun, but totally normal result. First of all, there are quite a few linear time sorting algorithms. Radix, pigeonhole, and counting sort are all linear time sorting algorithms. The popular result that any comparison-based sorting algorithm works in O(n log n) applies _specifically_ to comparison-based sorting algorithms, and not those like the above. So, even if you ignore the underlying mechanics of the OS scheduler and assume sleep works "perfectly", the result would not that unusual. Second off, in the comments there appears to be considerable time worrying about the technicalities of the scheduler, the nondeterministic nature of sleep, and so on, and whether this really implies linear time bound. IMHO these are not worth worrying about because we already have linear time sorting algorithms. It's fine to assume the scheduler adds no significant asymptotic cost here, even if we know differently. Third off, remember that all of these sorting bounds assume machines of the Von Neumann architecture. In particular, this model assumes constant time memory and constant time comparison operations. In cases where you're comparing really big numbers, these bounds get worse. This is easy to forget, but worth remembering just since we're on the subject anyway.
- wcrichton 12y agoThis is not "linear time" in any decent sense--we shouldn't conflate the number of elements with the size of the elements (in this case, O(max element) is actually exponential in the input size!).
- duaneb 12y agoYea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
- bnegreve 12y agoTrue, but writing a linear sort with bounded number of distinct elements is not really a challenge. E.g. Intput, T: array of n elements, m: number of distinct elements. for i in 1..m for j in 1..n if( T[j] == i ) print T[j]; This is O(n * m) which is O(n) since m is a constant.
- danso 12y agoSadly, the somewhat lengthy Wikipedia entry for Sleep sort was deleted. Here's archive.org's version: https://web.archive.org/web/20110622073615/http://en.wikipedia.org/wiki/Sleep_sort https://web.archive.org/web/20110622073615/http://en.wikiped... Reading through Wikipedia's existing pages for other esoteric sorts makes me laugh as I did when reading Hitchhiker's Guide to the Galaxy's various entries for scientific theories (e.g. Bistromathics)...There's Bogosort, Stooge sort, American flag sort, and my favorite, "Gnome sort", named thusly because "that is 'how a gnome sorts a line of flower pots'" http://en.wikipedia.org/wiki/Gnome_sort http://en.wikipedia.org/wiki/Gnome_sort
- Al-Khwarizmi 12y agoGnome sort used in a practical application (for natural language parsing): http://stp.lingfil.uu.se/~nivre/docs/gotal.pdf http://stp.lingfil.uu.se/~nivre/docs/gotal.pdf
- seabee 12y agoUnlike most esoteric algorithms, American flag sort is actually pretty useful in its niche of string sorting.
- drcomputer 12y agoBut why. I would think the gnome is the perfect size to pick up exactly one flower pot (the next smallest) and would also be able to recall a dividing line (because the gnome is tiny and prefers traveling less).
- chriswarbo 12y agoI like the comparison between the incredibly inefficient Bogosort: 1) Shuffle the list. 2) If it's sorted, halt. 3) If it's not sorted, go to step 1. and the incredibly efficient Quantum Bogosort: 1) Shuffle the list. 2) If it's sorted, halt. 3) If it's not sorted, destroy the Universe. According to the Many Worlds interpretation, step (1) creates multiple Universes, each with a different ordering of the list. Step (3) ensures that, by the anthropic principle, we must be in a Universe where the list was sorted correctly (otherwise we wouldn't be around to observe anything).
- SwellJoe 12y agoPrevious discussion: https://news.ycombinator.com/item?id=2657277 https://news.ycombinator.com/item?id=2657277 Pretty sure it's been posted a couple other times, but I'm on a tablet at the moment.
- deleted 12y ago[deleted]
- shultays 12y agoDidn't saw this post before I heartily disagree with all the attempts to downplay the brilliance of the sleep sort algorithm. Many of you have missed the important point that while traditional sorting algorithms can only utilize one core, sleep sort has the capacity to use the full power of a massively parallel execution environment. Given that you need nearly no computing in each of the threads, you can implement them using low-power CPUs, so this is in fact a GREEN COMPUTING algorithm. Oh, and did I mention that the algorithm can also run inside a cloud...? Sure, you're a genius!
- mrcexii 12y agohaha, read before but still feel its hilarious
- interesting_guy 12y agoThis one gets posted on 4chan's /g/ from time to time for amusement. Here's one I saved: http://imgur.com/XOR55PF http://imgur.com/XOR55PF
- majke 12y agoWith fluxcapacitor it will run in fraction of a second! https://github.com/majek/fluxcapacitor#basic-examples https://github.com/majek/fluxcapacitor#basic-examples $ ./fluxcapacitor examples/sleep_sort.sh 1 4 20 3 55
- ambrop7 12y agoI remember a few years ago, I hacked up the Wine source code so some skiing game would run at half speed. It totally worked :) It was even simpler than fluxcapacitor since you don't need to hook anything but just change the implementation of some time related functions.
- perlgeek 12y agoRecently I wrote about sleepsort for the Perl 6 advent calendar, mostly as a fun topic to talk about threads, promises etc. http://perl6advent.wordpress.com/2014/12/23/webscale-sorting-of-the-sleepy-kind/ http://perl6advent.wordpress.com/2014/12/23/webscale-sorting...
- ambrop7 12y agoOne should know that it is the timer scheduler of the kernel which ends up doing the sorting. With Linux, this is probably a red-black tree[1], so performance of sleep sort (when it works) is O(n *log(n)). [1] https://www.kernel.org/doc/Documentation/timers/hrtimers.txt https://www.kernel.org/doc/Documentation/timers/hrtimers.txt
- logicallee 12y agoif you'd like to trade space for time, here is another sort with no comparisons: http://codepad.org/0k2Ou2Db http://codepad.org/0k2Ou2Db
- vlad003 12y agoI don't know Perl, so I rewrote it in Python in an attempt to understand what's going on: https://gist.github.com/vlad003/35105af5892cb9cc5051 https://gist.github.com/vlad003/35105af5892cb9cc5051 I'm not storing key,value pairs for elements that don't exist (not sure what the Perl code's doing), so it shouldn't be too bad in terms of space used.
- woadwarrior01 12y agoI'm not entirely sure about this, but it looks more like Counting sort [1], than Pigeonhole sort. [1]: https://en.wikipedia.org/wiki/Counting_sort https://en.wikipedia.org/wiki/Counting_sort
- xianshou 12y agoRadix sort, with time as the buckets...stylish.
- veesahni 12y ago(impure) ruby implementation: ruby -e '[3,1,2].each{|n| system("sleep #{n} && echo #{n} &")}'
- Nimi 12y agoPardon the shameless plug, but I've recently used a similarly unorthodox approach for replacing the heap inside Dijkstra's algorithm, and got a speedup - I use an array indexed by the vertices' current distances, and scan it from start to finish. A paper is currently making the rounds, would love to hear feedback: https://www.dropbox.com/s/zy1gx1azfvvqm6i/NetSciComm%20version%2C%20December%202014.pdf?dl=0 https://www.dropbox.com/s/zy1gx1azfvvqm6i/NetSciComm%20versi...
- bluecalm 12y agoC implementation for Windows: #include <stdio.h> #include <windows.h> #include <process.h> void sleep_on_it(void* param) { int n = *(int*)param; Sleep(n); printf("%d ", n); } int main(int argc, char **argv) { int ar[argc]; HANDLE threads[argc-1]; for (int i = 1; i < argc; i++){ ar[i] = atoi(argv[i]); threads[i-1] = (HANDLE)_beginthread(&sleep_on_it, 0, &(ar[i])); } WaitForMultipleObjects(argc-1, threads, TRUE, INFINITE); } Compile with gcc -std=c99 (because of VLA's it won't work in Visual Studio). Example: D:>sleepsort 1000 9 2 150 1 7 17 624 1 2 7 9 17 150 624 1000
- taternuts 12y agoThis guy makes the rounds every once in awhile it seems. Here's a /r/dailyprogrammer thread with solutions in various languages: http://www.reddit.com/r/dailyprogrammer/comments/yqydh/8242012_challenge_91_easy_sleep_sort/ http://www.reddit.com/r/dailyprogrammer/comments/yqydh/82420...
- angersock 12y agoFor the record, in that thread, there are implementations in Bash, Erlang, Haskell (I think), Perl, C, and Racket. It also is interspersed with entertaining banter and unentertaining racism. So, basically, a more caustic more technical less orderly version of HN. Think about that. There's a reason 4chan should be considered a national...maybe not treasure, but it's pretty awesome.
- matheusbn 12y agoDo you mind if I submit a javascript version!? http://js.do/code/48519 http://js.do/code/48519 http://js.do/code/48526 http://js.do/code/48526 (Optimized milliseconds). :)