Implement Sleep Sort

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

APL (15 13)

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

What it does:

¨⎕       : for each element of the input
&        : do on a separate thread
⎕DL⍵    : wait approx. ⍵ seconds
⎕←⍵     : output ⍵

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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);}

Answer 8

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!

Answer 9

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();
    }
}

Answer 10

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)

Answer 11

ColdFusion (8+), 109 bytes

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

Ungolfed:

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

Answer 12

Javascript - 52 characters

for(i in a)setTimeout("console.log("+a[i]+")",a[i])

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

Answer 14

Befunge-98, 38 31 bytes

I know this is an old challenge, but I just recently discovered both sleepsort and 2D languages, had an idea about how to combine them, and looked for a place to post it, so here we are.

&#vt6j@p12<'
v:^ >$.@
>:!#^_1-

The main IP reads a number (&), then hits the t which clones it: one proceeds on the same line and cycles, reading new numbers and generating new childs until it reaches EOF which terminates the sequence. All the child processes get stuck in a closed loop (the v and ^ of the third column) until the main IP finishes reading the input and executes the sequence of commands '<21p, which puts the character < at position (1,2), overwriting the ^ and freeing all the child processes, which start to simultaneously cycle, reducing by 1 their number at each iteration. Since execution speed of different IPs is synchronized in befunge, they will terminate (and print their value) in order, sorting the input list.

Answer 15

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)

Answer 16

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);
}

Answer 17

Haskell, 90

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

I hope this meets all the requirements.

Answer 18

Rust, 125 bytes

Used the depricated sleep_ms function so I don't need to write a long duration.

|p:Vec<u32>|p.into_iter().for_each(|i|{use std::thread::{spawn,sleep_ms};spawn(move||{sleep_ms(i*1000);println!("{}",i)});});

playground link

Answer 19

JavaScript, 38 bytes

a=>a.map(x=>setTimeout(alert,x*1e3,x))

Answer 20

PHP 57 bytes

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

pcntl_fork() is only available under linux.

Answer 21

Bash (38):

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

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

Answer 22

𝔼𝕊𝕄𝕚𝕟, 11 chars / 22 bytes

ïć⇝שĤ⇀ôa,a⸩

Try it here (Firefox only).

שĤ⇀ôa, this looks cool.

Answer 23

PowerShell 7, 40 bytes

Filters are a kind of function:

filter f{$args|% -Pa{sleep $_;$_}-Th 99}

PS C:\> f 3 2 1
1
2
3

It uses Powershell 7's ForEach-Object -Parallel feature, which defaults to 5 threads, so has -ThrottleLimit 99 to make it at work for the required 10 numbers.

Answer 24

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

Answer 25

Clojure, 54

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

Answer 26

C++11, 229 bytes

#import<future>
#import<iostream>
using namespace std;int main(int a,char**v){auto G=new future<void>[a];while(--a){G[a]=move(async([=](){this_thread::sleep_for(chrono::seconds(atoi(v[a])));cout<<v[a]<<" "<<flush;}));}delete[]G;}

Ungolfed and usage:

#import<future>
#import<iostream>
using namespace std;
int main(int a,char**v){
 auto G=new future<void>[a];
 while(--a){
  G[a]=move(async(
   [=](){
    this_thread::sleep_for(chrono::seconds(atoi(v[a])));
    cout<<v[a]<<" "<<flush;
   }
  ));
 }
 delete[]G;
}

Answer 27

Rust - 150 bytes

And this is why you don't code golf in Rust, it's more verbose than Java ;). Depends on external crate crossbeam, it would be even worse without it.

|x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}

Complete test program:

fn main() {
    let z =
    |x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}
    ;
    z(&[4, 2, 3, 5, 7, 8, 9, 1, 6, 10])
}

Answer 28

Julia 1.0, 41 bytes

!l=@sync l.|>i->@async sleep(i)println(i)

Try it online!

@async adds the task to the machine's scheduler queue, and @sync waits for all @asyncs to finish

Answer 29

C (clang), 72 bytes

main(n){~scanf("%d",&n)?fork()?wait(main()):printf("%d ",n+sleep(n)):0;}

I chose clang but it also works on gcc.

1. takes input from stdin
2. fork()
3. if it's the child, then sleep (returns 0 if sleep succeeded, see sleep(3)) and print the number... if it's the parent call main recursively (which implicitly returns 0 since C99).
4. when there's no more input we return from main() and start waiting for the children, the children also call wait() a number of times depending on the recursion depth but they don't have any children so that fails immediately for them.

Try it online!

Answer 30

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)