87
\$\begingroup\$

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.

\$\endgroup\$
9
  • 3
    \$\begingroup\$ What counts towards the length? Complete programs including IO or just the relevant routine? \$\endgroup\$ Commented Jun 2, 2011 at 10:21
  • 11
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 2, 2011 at 11:03
  • 14
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 2, 2011 at 12:47
  • 14
    \$\begingroup\$ 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)? \$\endgroup\$
    – Random832
    Commented Jun 3, 2011 at 12:25
  • 2
    \$\begingroup\$ I think there are physical sort algorithms that takes O(n) time but O(n) physical objects. Well, we can use melting candles and a tube to do it. en.wikipedia.org/wiki/Spaghetti_sort \$\endgroup\$
    – Ming-Tang
    Commented Jun 3, 2011 at 23:06

39 Answers 39

1
2
0
\$\begingroup\$

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)})}
\$\endgroup\$
1
  • \$\begingroup\$ Even back in 2011 I think function(a){a.map(function(v){setTimeout(console.log,v,v)})} may have worked in at least one browser for 60 bytes. Of course these days you would write a=>a.map(v=>setTimeout(console.log,v,v)) instead. \$\endgroup\$
    – Neil
    Commented Mar 17, 2019 at 14:37
0
\$\begingroup\$

Tcl 8.6, 41 chars

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

You have to kill it with ^C

\$\endgroup\$
0
\$\begingroup\$

VB.NET 100 bytes

Because VB.Net requires single line lambdas to contain only one statement, this code has to have the multiple lines:

Array.ForEach(i, Async Sub(x)
Await Threading.Tasks.Task.Delay(x*1000)
Console.WriteLine(x)
End Sub)

Ungolfed:

Option Strict Off

Sub Main(i() as String)
    Array.ForEach(i, Async Sub(x)
                         Await Threading.Tasks.Task.Delay(x * 1000)
                         Console.WriteLine(x)
                     End Sub)
End Sub

However I'm not sure if you count imports statements in the byte counts because if you don't count them then I could write this:

VB.NET 71 bytes

a.ForEach(i, Async Sub(x)
Await t.Delay(x*1000)
c.WriteLine(x)
End Sub)

Ungolfed:

Option Strict Off
Imports t = System.Threading.Tasks.Task
Imports c = System.Console
Imports a = System.Array

Sub Main(i() as String)
    a.ForEach(i, Async Sub(x)
                     Await t.Delay(x * 1000)
                     c.WriteLine(x)
                 End Sub)
End Sub
\$\endgroup\$
0
\$\begingroup\$

Groovy, 47 bytes

Assumes numbers are given on the command line...

args.each{i->Thread.start{sleep(i*22)print i}}

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 34 or 36 bytes

RunScheduledTask[Print@#,{#,1}]&/@

Just append the list to be sorted to the end of this code and evaluate. If it needs to be a valid function definition then it takes two extra bytes:

RunScheduledTask[Print@#,{#,1}]&/@#&
\$\endgroup\$
0
\$\begingroup\$

Java 9, 82 bytes

i->{i.parallelStream().map(j->{Thread.sleep(j);System.out.println(j);return 0;});}
i->{                                                                             }  //lambda: arguments: List<int> i
    i.parallelStream().map(                                                    );   //iterate over each item in a parallel thread
                           j->{                                               }     //lambda: arguments: int j
                               Thread.sleep(j);                                     //sleep j milliseconds
                                               System.out.println(j);               //print that int
                                                                     return 0;      //just some return value to fullfil the requirements of map()
\$\endgroup\$
1
  • \$\begingroup\$ Some issues which practically mean this is an invalid solution. Thread.sleep throws InterruptedException (a checked exception that needs to be caught) which means this does not work. Also, streams don't run every element in a separate thread, and in fact because streams are lazy, this doesn't work at all as nothing is done with result of map. There is also no such thing as List<int> in Java. \$\endgroup\$
    – null
    Commented Jan 12, 2018 at 10:59
0
\$\begingroup\$

Java - 106 bytes

l->l.forEach(x->new Thread(()->{try{Thread.sleep(x);System.out.println(x);}catch(Exception e){}}).start())

Complete test program:

import java.util.List;
import java.util.function.Consumer;

public class CG {
    public static void main(String[] args) {
        Consumer<List<Integer>> sleepSort = l->l.forEach(x->new Thread(()->{try{Thread.sleep(x);System.out.println(x);}catch(Exception e){}}).start());
        sleepSort.accept(List.of(3423, 143, 4545, 2545, 764, 5121, 2333, 944, 6555, 1066));
    }
}
\$\endgroup\$
0
\$\begingroup\$

Japt, 11 bytes

Ëe3 t{OpD
P

Try it online!

Unpacked & How it works

UmD{De3 t{OpD
P

UmD{  Map input array with the function...
De3 t{  Run the following function after D * 1000 milliseconds...
OpD       Print D with newline

P     Set "" as the thing to implicitly print

JS's setTimeout is obviously the winner. Unlike setInterval which is low-capped at 10ms, setTimeout doesn't have such an arbitrary limit.

If the delay need not be in seconds, the following works (and gives the result much faster):

8 bytes

Ët{OpD
P

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ You could overwrite the crud output by N.t() (no idea why ETH did that) and avoid the need for the "P" by using O.q() instead. Each number would overwrite the previous one, though, which may not be allowed behaviour. \$\endgroup\$
    – Shaggy
    Commented Aug 27, 2021 at 10:37
0
\$\begingroup\$

PowerShell 6, 34 bytes

$args|%{$(sleep $_;$_)&}|rcjb -wai

Try it online!

See Background operator &


PowerShell, 48 bytes

$args|%{sajb{sleep $args;$args}-ar $_}|rcjb -wai

Try it online!

where:

  • sajb is the predefined alias for start-job and
  • rcjb is the predefined alias for receive-job

The default ThrottleLimit is 32.

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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