Sorting algorithms/Sleep sort

From Rosetta Code
Task
Sorting algorithms/Sleep sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log2n) sorts
Shell Sort

O(n2) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

In general, sleep sort works by starting a separate task for each item to be sorted, where each task sleeps for an interval corresponding to the item's sort key, then emits the item. Items are then collected sequentially in time.

Task: Write a program that implements sleep sort. Have it accept non-negative integers on the command line and print the integers in sorted order. If this is not idomatic in your language or environment, input and output may be done differently. Enhancements for optimization, generalization, practicality, robustness, and so on are not required.

Sleep sort was presented anonymously on 4chan and has been discussed on Hacker News.

C

<lang C>#include <stdlib.h>

  1. include <unistd.h>
  2. include <sys/types.h>
  3. include <sys/wait.h>

int main(int c, char **v) { 

       while (--c > 1 && !fork());
       sleep(c = atoi(v[c]));
       printf("%d\n", c);
       wait(0);
       return 0;

}</lang> Running it:<lang>% ./a.out 5 1 3 2 11 6 4 1 2 3 4 5 6 11</lang> If you worry about time efficiency of this sorting algorithm (ha!), you can make it a 100 times faster by replacing the sleep(... with usleep(10000 * (c = atoi(v[c]))). The smaller the coefficient, the faster it is, but make sure it's not comparable to your kernel clock ticks or the wake up sequence will be wrong.

C#

<lang csharp>using System; using System.Collections.Generic; using System.Linq; using System.Threading;

class Program { 

   static void ThreadStart(object item)
   {
       Thread.Sleep(1000 * (int)item);
       Console.WriteLine(item);
   }

   static void SleepSort(IEnumerable<int> items)
   {
       foreach (var item in items)
       {
           new Thread(ThreadStart).Start(item);
       }
   }

   static void Main(string[] arguments)
   {
       SleepSort(arguments.Select(int.Parse));
   }

}</lang>

Delphi

<lang Delphi>program SleepSortDemo;

{$APPTYPE CONSOLE}

uses 

 Windows, SysUtils, Classes;

type 

 TSleepThread = class(TThread)
 private
   FValue: Integer;
   FLock: PRTLCriticalSection;
 protected
   constructor Create(AValue: Integer; ALock: PRTLCriticalSection);
   procedure Execute; override;
 end;

constructor TSleepThread.Create(AValue: Integer; ALock: PRTLCriticalSection); begin 

 FValue:= AValue;
 FLock:= ALock;
 inherited Create(False);

end;

procedure TSleepThread.Execute; begin 

 Sleep(1000 * FValue);
 EnterCriticalSection(FLock^);
 Write(FValue:3);
 LeaveCriticalSection(FLock^);

end;

var 

 A: array[0..15] of Integer;
 Handles: array[0..15] of THandle;
 Threads: array[0..15] of TThread;
 Lock: TRTLCriticalSection;
 I: Integer;

begin 

 for I:= Low(A) to High(A) do
   A[I]:= Random(15);
 for I:= Low(A) to High(A) do
   Write(A[I]:3);
 Writeln;

 InitializeCriticalSection(Lock);
 for I:= Low(A) to High(A) do begin
   Threads[I]:= TSleepThread.Create(A[I], @Lock);
   Handles[I]:= Threads[I].Handle;
 end;
 WaitForMultipleObjects(Length(A), @Handles, True, INFINITE);
 for I:= Low(A) to High(A) do
   Threads[I].Free;
 DeleteCriticalSection(Lock);

 Writeln;
 ReadLn;

end.</lang> Output: 

  0  0 12  3  4 10  4  2  5  6  1  7  1 12  0  4
  0  0  0  1  1  2  3  4  4  4  5  6  7 10 12 12

Euphoria

<lang euphoria>include get.e

integer count

procedure sleeper(integer key) 

   ? key
   count -= 1

end procedure

sequence s, val atom task

s = command_line() s = s[3..$] if length(s)=0 then 

   puts(1,"Nothing to sort.\n")

else 

   count = 0
   for i = 1 to length(s) do
       val = value(s[i])
       if val[1] = GET_SUCCESS then
           task = task_create(routine_id("sleeper"),{val[2]})
           task_schedule(task,{val[2],val[2]}/10)
           count += 1
       end if
   end for
   
   while count do
       task_yield()
   end while

end if</lang>

Go

<lang go>import ( 

   "log"
   "os"
   "strconv"
   "sync"
   "time"

)

func main() { 

   lg := log.New(os.Stdout, "", 0)
   var wg sync.WaitGroup
   wg.Add(len(os.Args) - 1)
   for _, a := range os.Args[1:] {
       if i, err := strconv.Atoi64(a); err == nil {
           time.AfterFunc(i*1e9, func() {
               lg.Print(i)
               wg.Done()
           })
       }
   }
   wg.Wait()

}</lang> Usage and output: 

./sleepsort 3 1 4 1 5 9
1
1
3
4
5
9

Haskell

<lang haskell>import System.Environment import Control.Concurrent import Control.Monad

sleepSort :: [Int] -> IO () sleepSort values = do chan <- newChan forM_ values (\time -> forkIO (threadDelay (50000 * time) >> writeChan chan time)) forM_ values (const (readChan chan >>= print))

main :: IO () main = getArgs >>= sleepSort . map read</lang>

Java

Works with: Java version 1.5+

<lang java5>import java.util.concurrent.CountDownLatch;

public class SleepSort { public static void sleepSortAndPrint(int[] nums) { final CountDownLatch doneSignal = new CountDownLatch(nums.length); for (final int num : nums) { new Thread(new Runnable() { public void run() { doneSignal.countDown(); try { doneSignal.await();

//using straight milliseconds produces unpredictable //results with small numbers //using 1000 here gives a nifty demonstration Thread.sleep(num * 1000); System.out.println(num); } catch (InterruptedException e) { e.printStackTrace(); } } }).start(); } } public static void main(String[] args) { int[] nums = new int[args.length]; for (int i = 0; i < args.length; i++) nums[i] = Integer.parseInt(args[i]); sleepSortAndPrint(nums); } }</lang> Output (using "3 1 4 5 2 3 1 6 1 3 2 5 4 6" as arguments): 

1
1
1
2
2
3
3
3
4
4
5
5
6
6

JavaScript

<lang javascript>Array.prototype.timeoutSort = function (f) { this.forEach(function (n) { setTimeout(function () { f(n) }, 5 * n) }); } </lang> Usage and output: <lang javascript>[1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0].timeoutSort(function(n) { document.write(n + 'br'); })</lang> 

0
1
2
3
4
5
6
7
8
9

Perl

Basically the C code. <lang Perl>1 while ($_ = shift and @ARGV and !fork); sleep $_; print "$_\n"; wait;</lang>

PicoLisp

Sleeping in main process

<lang PicoLisp>(de sleepSort (Lst) 

  (make
     (for (I . N) Lst
        (task (- I) (* N 100)  N N  I I
           (link N)
           (pop 'Lst)
           (task (- I)) ) )
     (wait NIL (not Lst)) ) )</lang>

Sleeping in child processes

<lang PicoLisp>(de sleepSort (Lst) 

  (make
     (for N Lst
        (task (pipe (wait (* N 100))) N N
           (link N)
           (pop 'Lst)
           (task (close @)) ) )
     (wait NIL (not Lst)) ) )</lang>

Output in both cases: 

: (sleepSort (3 1 4 1 5 9 2 6 5))
-> (1 1 2 3 4 5 5 6 9)

Just printing (no sorted result list)

Basically the C code. <lang PicoLisp>(for N (3 1 4 1 5 9 2 6 5) 

  (unless (fork)
     (call 'sleep N)
     (msg N)
     (bye) ) )</lang>

Output: 

1              
1
2
3
4
5
5
6
9

Prolog

Works with SWI-Prolog. <lang Prolog>sleep_sort(L) :- thread_pool_create(rosetta, 1024, []) , maplist(initsort, L, LID), maplist(thread_join, LID, _LStatus), thread_pool_destroy(rosetta).

initsort(V, Id) :- thread_create_in_pool(rosetta, (sleep(V), writeln(V)), Id, []).

</lang> Output : 

 sleep_sort([5, 1, 3, 2, 11, 6, 3, 4]).
1
2
3
3
4
5
6
11
true.

PureBasic

<lang PureBasic>NewMap threads()

Procedure Foo(n) 

 Delay(n)
 PrintN(Str(n))

EndProcedure

If OpenConsole() 

 For i=1 To CountProgramParameters()
   threads(Str(i)) = CreateThread(@Foo(), Val(ProgramParameter()))
 Next
 
 ForEach threads()
   WaitThread(threads())
 Next
 Print("Press ENTER to exit"): Input()

EndIf</lang> 

Sleep_sort.exe 3 1 4 1 5 9
1
1
3
4
5
9
Press ENTER to exit

Python

<lang python>from time import sleep from threading import Timer

def sleepsort(values): 

   sleepsort.result = []
   def add1(x):
       sleepsort.result.append(x)
   mx = values[0]
   for v in values:
       if mx < v: mx = v
       Timer(v, add1, [v]).start()
   sleep(mx+1)
   return sleepsort.result

if __name__ == '__main__': 

   x = [3,2,4,7,3,6,9,1]
   if sleepsort(x) == sorted(x):
       print('sleep sort worked for:',x)
   else:
       print('sleep sort FAILED for:',x)</lang>
Sample output
sleep sort worked for: [3, 2, 4, 7, 3, 6, 9, 1]

Ruby

<lang ruby>require 'thread'

nums = ARGV.collect(&:to_i) sorted = [] mutex = Mutex.new

threads = nums.collect do |n| 

 Thread.new do
   sleep 0.01 * n
   mutex.synchronize {sorted << n}
 end

end threads.each {|t| t.join}

p sorted</lang>

Example 

$ ruby sleepsort.rb 3 1 4 5 2 3 1 6 1 3 2 5 4 6
[1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6]

Tcl

<lang tcl>#!/bin/env tclsh set count 0 proc process val { 

   puts $val
   incr ::count

}

  1. Schedule the output of the values

foreach val $argv { 

   after [expr {$val * 10}] [list process $val]

}

  1. Run event loop until all values output...

while {$count < $argc} { 

   vwait count

}</lang> Demonstrating: 

bash$ sleepsort.tcl 3 1 4 5 2 3 1 6 1 3 2 5 4 6
1
1
1
2
2
3
3
3
4
4
5
5
6
6

UNIX Shell

Works with: Bourne Shell

<lang bash>f() { 

   sleep "$1"
   echo "$1"

} while [ -n "$1" ] do 

   f "$1" &
   shift

done wait</lang> Usage and output: 

sh sleepsort.sh 3 1 4 1 5 9
1
1
3
4
5
9
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort?oldid=189050"