Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sleep Sort is an integer sorting algorithm I found on the Internet. It opens an output stream, and for each input numbers in parallel, delay for the number seconds and output that number. Because of the delays, the highest number will be outputted last. I estimate it has O(n + m), where n is the number of elements and m is the highest number.

Here is the original code in Bash

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

Here is the pseudocode

sleepsort(xs)
 output = []
 fork
   for parallel x in xs:
     sleep for x seconds
     append x to output
 wait until length(output) == length(xs)
 return output

Your task is to implement Sleep Sort as a function in the programming language of your choice. You can neglect any concurrency factors such as race conditions and never lock any shared resources. The shortest code wins. The function definition counts toward the code length.

The input list is limited to non-negative integers only, and the length of the input list is expected to reasonably long (test at least 10 numbers) so race conditions never happen. and assuming race conditions never happen.

share|improve this question
3  
What counts towards the length? Complete programs including IO or just the relevant routine? –  Konrad Rudolph Jun 2 '11 at 10:21
7  
A problem with this. Depending on the order of the list, you might not read the entire list before the first value is printed. For example, a large list that takes 45 seconds to read, the first value is 2 and the last value is 1. The thread to print 1 might be executed after the 2 is printed. Oops - the output is no longer sorted properly. There might be some workarounds - creating the threads and then starting them after the whole list is read (but that will lead to longer code, against the golf). I wonder if someone can provide a golf that addresses this potential issue...I'm going to try. –  Thomas Owens Jun 2 '11 at 11:03
6  
Incidentally, what makes this algorithm really interesting is that there actually exist real-life applications. For instance, DNA sequencing (Sanger sequencing) depends on something like this to sort DNA fragments according to their length (and more generally, every electrophoresis does something similar). The difference is that sequencing is performed physically, not in a computer. –  Konrad Rudolph Jun 2 '11 at 12:47
7  
I hate to be the one to rain on everybody's parade, but doesn't this just offload complexity onto the OS scheduler in a way that's probably O(N^2)? –  Random832 Jun 3 '11 at 12:25
    
I wonder weather you can implement this in a way it actually performs well. How would you have to figure out the amount of time it has to wait per step, so the numbers would be still placed in the right order? –  Nils Jun 3 '11 at 15:50

23 Answers 23

up vote 14 down vote accepted

A kind of lame Perl attempt, 59 55 52 38 32 characters:

map{fork||exit print sleep$_}@a

Barebones: 25 Characters:

...if you don't mind the sort results as die output:

map{fork||die sleep$_}@a

With all the trimmings:

(for maximum challenge compliance, 44 characters)

sub t{map{fork||exit print sleep$_}@_;wait}

If you let perl do the wait for you, 39 characters:

sub t{map{fork||exit print sleep$_}@_}

And again, if you don't mind die(), 32 characters...

sub t{map{fork||die sleep$_}@_}

Note that in Perl 6, or when the 'say' feature is declared, it is possible to replace the print function with say, saving a character in each instance. Obviously since die both terminates the forked process and writes the output, it remains the shortest solution.

share|improve this answer
    
you can stil run perl-E to enable 5.010 features like say –  mbx Jun 6 '11 at 16:33

Tcl 8.6, 41 chars

lmap c $argv {after $c "puts $c"};vwait f

You have to kill it with ^C

share|improve this answer

Haskell, 90

import Control.Concurrent
s::[Int]->IO()
s=mapM_(\x->forkIO$threadDelay(x*9999)>>print x)

I hope this meets all the requirements.

share|improve this answer

Bash (38):

xargs -P0 -n1 sh -c 'sleep $0;echo $0'

Edit: Floating-point from stdin, separated by spaces or newlines.

share|improve this answer

Clojure, 54

(defn s[n](doseq[i n](future(Thread/sleep i)(prn i))))

share|improve this answer

APL (15 13)

{⎕←⍵⊣⎕DL⍵}&¨⎕

What it does:

¨⎕       : for each element of the input
&        : do on a separate thread
⎕DL⍵    : wait approx. ⍵ seconds
⎕←⍵     : output ⍵
share|improve this answer
    
I see boxes instead of 3 characters. –  mlatu Aug 16 '12 at 13:02
4  
@ArtemIce: There are supposed to be three boxes (quads). Two are the I/O variable (reading it gets input, and writing to it prints output), and one is in the name of the ⎕DL function which is sleep. –  marinus Aug 16 '12 at 19:05

PHP 57 bytes

<?for(;$i=fgets(STDIN);)pcntl_fork()?:die($i.usleep($i));

pcntl_fork() is only available under linux.

share|improve this answer

C, 70 69 chars

Doesn't wait for child processes to return, otherwise works.

main(n) {
    while(~scanf("%d",&n)?fork()||!printf("%d\n",n,sleep(n)):0);
}
share|improve this answer

Java (aka never wins at codegolf) : 234 211 187 chars

public class M{public static void main(String[]s){for(final String a:s)new Thread(){public void run(){try{sleep(Long.parseLong(a));}catch(Exception e){}System.out.println(a);}}.start();}}

ungolfed:

public class M {
    public static void main(String[] s) {
        for(final String a:s) new Thread(){
            public void run() {
                try {
                    sleep(Long.parseLong(a));
                } catch(Exception e){}
                System.out.println(a);
            }
        }.start();
    }
}
share|improve this answer
    
@Joey thanks for setting it straight. –  trutheality Jun 18 '11 at 19:10
    
The class can be non-public, saving 7 chars. –  Daniel Oct 28 '13 at 1:53
    
You could also declare throws Throwable and get rid of the catch clause. –  Daniel Oct 28 '13 at 2:05

JavaScript, 65 characters (depending on whether you use console.log or something else for outputting the result)

a.map(function(v){setTimeout(function(){console.log(v)},v*1000)})

This assumes that a is an array of non-negative integers and that map() exists on the array prototype (JavaScript 1.6+).

share|improve this answer
    
You can probably shave off two or even three characters by multiplying with 10 (or 9) instead of 1000, without compromising correctness. –  Konrad Rudolph Jun 2 '11 at 10:46
    
@Konrad: Yes, I think that would work. I just took the "one second" from the question. –  Tomalak Jun 2 '11 at 10:50
10  
If the one second is intended to remain, you can probably use 1e3 instead. –  Joey Jun 2 '11 at 10:56
1  
@Tomalak, alert is JavaScript's blocking output, prompt is JavaScript's blocking input, and confirm is JavaScript's blocking binary input. If JS were to be written on the command line, those would be the calls you would use. –  zzzzBov Jun 2 '11 at 13:13
1  
@zzzzBov, it's the order in which they're called which I'm worried about - unless the JS spec has strong guarantees about the order in which setTimeout-enqueued thunks are called. –  Peter Taylor Jun 2 '11 at 17:36

Scala - 42 40 characters (special case)

If you have a thread pool at least the size of the number of list elements:

a.par.map{i=>Thread.sleep(i);println(i)}

Scala - 72 characters (general)

a.map(i=>new Thread{override def run{Thread.sleep(i);println(i)}}.start)
share|improve this answer
    
afaik you don’t use {} when staying on one line. –  flying sheep Jun 16 '11 at 19:36
    
@flying sheep - You can omit {} with one statement, but you still need it to group things separated by ;, one line or no. And you can write multi-line statements without {} in some cases (if/else for instance). –  Rex Kerr Jun 16 '11 at 22:33
    
oh, i didn’t mean you can omit them, but that you can use () for one-liners instead. it’s a matter of taste there, i think. (i just don’t really get why () are supported at all when {} superseed them. maybe to not alienate java users instantly). Scala is cool, but defining code blocks by indentation is clearly superior. (and so, the religious war ensues ;)) –  flying sheep Jun 17 '11 at 9:59
    
@flying sheep - You're misinformed. You can use () for single statements. Try entering (1 to 9).map(i => {val j = i+1; i*j}) in the REPL and then see what happens if you use (1 to 9).map(i => (val j = i+1; i*j)). –  Rex Kerr Jun 17 '11 at 15:34
    
true, but i only referred to for expressions and stuff. Sorry, I hate writing stuff without being able to use linebreaks ;) –  flying sheep Jun 17 '11 at 18:25

JavaScript, 74

function(a){for(i=0;i<a.length;i++)setTimeout('alert('+a[i]+')',a[i]*1e3)}

or 71/65 characters with nonstandardness:

function(a){a.map(function(v){setTimeout('console.log('+v+')',v*1e3)})}
share|improve this answer

Python - 81 93 148 150 153

Tweaking @BiggAl's code, since that's the game we're playing....

import threading as t,sys
for a in sys.argv[1:]:t.Timer(int(a),print,[a]).start()

... or 97 175 with delayed thread starting

import threading as t,sys
for x in [t.Timer(int(a),print,[a]) for a in sys.argv[1:]]:x.start()

Takes input via the command line, ala

./sleep-sort\ v0.py 1 7 5 2 21 15 4 3 8

As with many python golfs, there comes a point where the code is compact enough that aliasing variables to shorten names doesn't even save characters.

This one is funky though because it aliases sys and threading BOTH as t, so sys.argv becomes t.argv. Shorter than from foo import *, and a net character savings! However I suppose Guido wouldn't be pleased...

Note to self - learn c and stop golfing in python. HOLY COW THIS IS SHORTER THAN THE C SOLUTION!

share|improve this answer
    
I managed to make some tweaks, but the formatting doesn't show up nicely in comments so I made my own answer. daemon doesn't need setting unless you're starting this as a daemon, and it's shorter to use positional args, esp. if you alias None to N –  theheadofabroom Jun 6 '11 at 12:51
    
Oh and the first one doesn't work for me under 2.7.1, as j seems to end up as False - a side-effect of trying to do too much in one line? –  theheadofabroom Jun 6 '11 at 13:11
    
shit I didn't realise you could import multiple modules to the same alias - I could actually think of some uses for that where I have multiple subclasses of the same custom base class lying about in seperate sub-modules. If we can shave off another 30 it's shorter than bash... But I don't think that'll happen. –  theheadofabroom Jun 8 '11 at 9:15
    
Argh the reason why I didn't know is because you can't - I just tried running it and threading is not aliased, it's just called threading. It's sys that is aliased to t... Did you try running this? It's only an extra 2 chars on each though to import as t,s and then change to use s for sys –  theheadofabroom Jun 8 '11 at 9:29
1  
why don’t you use the print function instead of sys.stdout.write? –  flying sheep Jun 16 '11 at 19:35

A little late to the party:

Maple - 91 83 characters

In 91:

M:=():use Threads in p:=proc(n)Sleep(n);:-M:=M,n;end:Wait(map(i->Create(p(i)),L)[])end:[M];

In 83:

M:=():use Threads in Wait(seq(Create(proc(n)Sleep(n);:-M:=M,n end(i)),i=L))end:[M];

(This needs Maple version 15, and expects the list to be sorted in L)

share|improve this answer

Kind of boring, port of C#, just to get started with the language again:

F# - 90 characters

PSeq.withDegreeOfParallelism a.Length a|>PSeq.iter(fun x->Thread.Sleep(x);printfn "%A" x)
share|improve this answer

Just some tweaking from @rmckenzie 's version:

Python delayed thread start in 155 152 114 108 107:

import sys, threading as t
for x in [t.Timer(int(a),sys.stdout.write,[a]) for a in sys.argv[1:]]:x.start()

Python without delay in 130 128 96 95 93:

import sys,threading as t
for a in sys.argv[1:]:t.Timer(int(a),sys.stdout.write,[a]).start()

Managed a few more optimisations, using Timer instead of Thread, which has a more concise call and removed the need to import time. Delayed thread start method benefits from list comprehension as it removes the need to initialise the list seperately at the start, although it's two characters longer ("["+"]"+" "-":") than the for loop so it's useless without delayed start, and you have to be careful to use a list rather than a generator, or you're not actually creating the timer threads until you chunk through the generator.

Does anyone else have any optimisations?


The trick with as helps, but in 2.7.1 you can only import one module into an alias, and after some playing about you can't even import mod1,mod2 as a,b, you have to import mod1 as a, mod2 as b. It still saves a few characters, but isn't quite the cure-all I thought it was... And in fact it's better to leave sys as sys. Aliasing threading still helps though...

share|improve this answer
    
you got me beat, have an upding. I like the x=[];x+=[]. Didn't know you could do that.... –  arrdem Jun 6 '11 at 13:51
    
... you could do this in 128 if you loose the spaces between the : [statement] in your loop and f(x)... somehow I got it to 127, but I think that's by not counting the final newline (which is legit in CG). Thought I'd give you the update rather than being a tool and stealing your code. –  arrdem Jun 6 '11 at 14:09
    
@rmckenzie go for it, I stole yours. I'm always interested in seeing CG'd python - I feel like I'm doing something very perverse considering the goals of the language... –  theheadofabroom Jun 7 '11 at 15:05
    
Yeah, I'm honestly shocked by how legible most python golfs stay... at the cost of a "glass floor" of characters. Check this one out: import threading,sys as t –  arrdem Jun 7 '11 at 20:13

Haskell - 143 characters

import Control.Concurrent
import System
d=threadDelay
f x=d(10^6*x)>>print x
g s=mapM(forkIO.f)s>>d(10^6*maximum s+1)
main=getArgs>>=g.map read

This probably could be made a shorter by taking input on stdin if that were an option, but it's late and either way, it's still 104 characters for the function itself.

share|improve this answer

Javascript - 52 characters

for(i in a)setTimeout("console.log("+a[i]+")",a[i])
share|improve this answer
    
Welcome to CodeGolf.SE! I have formatted you answer for you, in particular indenting your code by four space to make it display as code. You'll find other formatting help in the sidebar of the edit page. –  dmckee Jun 3 '11 at 0:29

C# - 137 characters

Here is an answer in C# (updated with degrees of parallelism as commented)

void ss(int[]xs){xs.AsParallel().WithDegreeOfParallelism(xs.Length).Select(x=>{Thread.Sleep(x);return x;}).ForAll(Console.WriteLine);}
share|improve this answer
1  
You’ll need to specify WithDegreeOfParallelism for this to work, analogously to the num_threads in my OpenMP C code. –  Konrad Rudolph Jun 2 '11 at 20:18
    
Thank you, I have updated it to match that. –  Yet Another Geek Jun 2 '11 at 20:25

For fun, here's a ColdFusion (8+) version ;-) It has 109 characters not counting the line wraps and indentation that I added for legibility here.

<cfloop array="#a#" index="v">
  <cfthread><cfthread action="sleep" duration="#v*1000#"/>#v#</cfthread>
</cfloop>

This assumes that <cfoutput> is in effect. A few characters could be saved by writing it all on one line.

share|improve this answer

Ruby 1.9, 32 characters

As a function:

s=->a{a.map{|i|fork{p sleep i}}}

If we can just use a predefined variable, it reduces to 25 characters:

a.map{|i|fork{p sleep i}}
share|improve this answer
1  
You can save quite some chars by using Thread.new{p sleep i} to print the output. –  Howard Jun 2 '11 at 10:32
    
@Howard: Good catch, thanks! –  Ventero Jun 2 '11 at 10:37

Four tries in Erlang:

Output to the console, have taken the liberty to do this each 9ms * Number since this is plenty enough to make it work (tested on a Atom embedded board = slow):

Needs 60 chars

s(L)->[spawn(fun()->timer:sleep(9*X),io:write(X)end)||X<-L].

Output to the console is total un-Erlangish, so we send a message to process P instead:

Needs 55 chars

s(P,L)->[spawn(fun()->timer:sleep(9*X),P!X end)||X<-L].

Sending after a time can also be done differently (this even works with 1ms * Number):

Needs 41 chars

s(P,L)->[erlang:send_after(X,P,X)||X<-L].

Actually this is a bit unfair since the built in function send_after is a late comer and needs the namespace erlang: prefixed, if we consider this namespace imported (done on module level):

Needs 34 chars

s(P,L)->[send_after(X,P,X)||X<-L].
share|improve this answer

C, 127 characters, a rather obvious solution:

main(int c,char**v){
#pragma omp parallel for num_threads(c)
for(int i=1;i<c;++i){int x=atoi(v[i]);sleep(x);printf("%d ",x);}}

(Compiled with gcc -std=c99 -fopenmp sort.c and ignoring all warnings.)

share|improve this answer
4  
Cool I really have to learn opemp –  Nils Jun 2 '11 at 11:38
    
I would call that 93 characters (without command-line parsing and such), but it's impressive that you can do that in only 34 extra characters in C! –  Rex Kerr Jun 2 '11 at 13:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.