Sorting algorithms/Sleep sort: Difference between revisions

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.

 

 

=={{header|Ada}}==

with Ada.Command_Line; use Ada.Command_Line;

procedure SleepSort is

TaskList(i) := new PrintTask(Integer'Value(Argument(i)));

end loop;

{{out}}

<pre>./sleepsort 35 21 11 1 2 27 32 7 42 20 50 42 25 41 43 14 46 20 30 8

 

=={{header|APL}}==

sleepsort←{{r}⎕TSYNC{r,←⊃⍵,⎕DL ⍵}&¨⍵,r←⍬}

 

=={{header|Bash}}==

function sleep_and_echo {

sleep "$1"

 

wait

 

{{out}}

{{works with|BBC BASIC for Windows}}

This does not explicitly 'sleep', but uses timers to implement the different delays.

DIM test%(9)

DEF PROCtask7 : PRINT test%(7) : ENDPROC

DEF PROCtask8 : PRINT test%(8) : ENDPROC

'''Output:'''

<pre>

 

=={{header|Brainf***}}==

>>>>>,----------[++++++++

++[->+>+<<]>+>[-<<+>>]+++

->>>>>[>>>>>]<-<<<<[<<<<<

]+<]<<<<]>>>>>[>>>>>]<]

Not exactly 'sleep' sort but it is similar: it inputs an array of digits and in each iteration reduces elements by 1. When an element becomes 0 – it prints the original digit.

 

 

=={{header|C}}==

#include <unistd.h>

#include <sys/types.h>

wait(0);

return 0;

1

2

5

6

If you worry about time efficiency of this sorting algorithm (ha!), you can make it a 100 times faster by replacing the <code>sleep(...</code> with <code>usleep(10000 * (c = atoi(v[c])))</code>. 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.

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Linq;

SleepSort(arguments.Select(int.Parse));

}

 

===Using Tasks===

 

 

foreach (var n in input)

Console.WriteLine(n);

});

 

Output, i.e. in LINQPad:

 

=={{header|C++}}==

#include <chrono>

#include <iostream>

}

}

{{out}}

<pre>

=={{header|Clojure}}==

Using core.async

(require [clojure.core.async :as async :refer [chan go <! <!! >! timeout]]))

 

(go (<! (timeout (* 1000 i)))

(>! c i)))

 

=={{header|CoffeeScript}}==

{{works_with|node.js}}

after = (s, f) -> setTimeout f, s*1000

 

input = (parseInt(arg) for arg in process.argv[2...])

sleep_sort input

output

> time coffee sleep_sort.coffee 5, 1, 3, 4, 2

1

user 0m0.147s

sys 0m0.024s

 

=={{header|Common Lisp}}==

{{works_with|SBCL}}

(sleep (/ n 10))

(format t "~a~%" n))

(sb-thread:make-thread (lambda() (sleeprint (parse-integer arg)))))

 

{{Out}}

<pre>$ sbcl --script ss.cl 3 1 4 1 5

 

=={{header|D}}==

{

{{out}}

 

=={{header|Dart}}==

void main() async {

Future<void> sleepsort(Iterable<int> input) => Future.wait(input

await sleepsort([3, 10, 2, 120, 122, 121, 54]);

}

{{out}}

<pre>

 

=={{header|Delphi}}==

 

{$APPTYPE CONSOLE}

Writeln;

ReadLn;

Output:

<pre>

 

=={{header|Elena}}==

import system'routines;

import extensions'threading;

sleepSort()

{

{

threadControl.start(

}

}

public program()

{

 

=={{header|Elixir}}==

{{trans|Erlang}}

def sleep_sort(args) do

Enum.each(args, fn(arg) -> Process.send_after(self, arg, 5 * arg) end)

end

 

 

{{out}}

GNU Emacs supports threads, but it's more straightforward to do this by just using timers.

Evaluate in the *scratch* buffer by typing <code>C-M-x</code> on the expression:

 

The output printed in the *Messages* buffer is:

 

=={{header|Erlang}}==

%% -*- erlang -*-

%%! -smp enable -sname sleepsort

io:format("~s~n", [Num]),

loop(N - 1)

{{out}}

<pre>./sleepsort 2 4 8 12 35 2 12 1

 

=={{header|Euphoria}}==

 

integer count

task_yield()

end while

 

=={{header|Factor}}==

 

USING: threads calendar concurrency.combinators ;

 

: sleep-sort ( seq -- ) [ dup seconds sleep . ] parallel-each ;

 

Usage:

 

{ 1 9 2 6 3 4 5 8 7 0 } sleep-sort

 

=={{header|Fortran}}==

program sleepSort

use omp_lib

end subroutine sleepNprint

end program sleepSort

Compile and Output:

<pre>

Can't use FreeBASIC '''sleep''' since it halts the program.

Instead it uses a second array filled with times based on the value of number, this array is check against the timer. If the timer is past the stored time the value is printed.

' compile with: fbc -s console

' compile with: fbc -s console -exx (for bondry check on the array's)

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsorted 5 2 5 6 4 6 9 5 1 2 0

 

=={{header|Go}}==

 

import (

fmt.Println(<-out)

}

Usage and output:

<pre>./sleepsort 3 1 4 1 5 9

9

</pre>

 

=={{header|Groovy}}==

@Grab(group = 'org.codehaus.gpars', module = 'gpars', version = '1.2.1')

import groovyx.gpars.GParsPool

}

}

 

Sample Run:

=={{header|Haskell}}==

 

import Control.Concurrent

import Control.Monad

 

main :: IO ()

 

import Control.Concurrent

import Control.Concurrent.Async

 

sleepSort :: [Int] -> IO ()

 

main :: IO ()

 

This is problematic for inputs with multiple duplicates like <code>[1,2,3,1,4,1,5,1]</code> because simultaneous <code>print</code>s are done concurrently and the 1s and newlines get output in jumbled up order. The channels-based version above doesn't have this problem.

The following solution only works in Unicon.

 

every insert(t:=set(),mkThread(t,!A))

every spawn(!t) # start threads as closely grouped as possible

procedure mkThread(t,n) # 10ms delay scale factor

return create (delay(n*10),delete(t,&current),n@>&main)

 

Sample run:

->

</pre>

 

=={{header|Java}}==

{{works with|Java|1.5+}}

 

public class SleepSort {

sleepSortAndPrint(nums);

}

Output (using "3 1 4 5 2 3 1 6 1 3 2 5 4 6" as arguments):

<pre>1

 

=={{header|JavaScript}}==

this.forEach(function (n) {

setTimeout(function () { f(n) }, 5 * n)

});

}

Usage and output:

<pre>

0

</pre>

 

const res = [];

for (let n of this)

[1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0].sleepSort(console.log);

// [ 1, 0, 2, 3, 4, 5, 5, 6, 7, 8, 9 ]

 

=={{header|jq}}==

Doesn't actually sleep. Instead, iterates reducing the values by one until each is zero.

 

def f:

if .unsorted == [] then

end;

{unsorted: [.[] | {v: ., t: .}], sorted: []} | f | .[]

{{out}}

<pre>1

 

=={{header|Julia}}==

 

@async begin

end

end

end

 

v = rand(-10:10, 10)

 

{{out}}

 

=={{header|Kotlin}}==

 

import kotlin.concurrent.thread

println("Unsorted: ${list.joinToString(" ")}")

sleepSort(list, 50)

 

Sample output:

<pre>

$ java -jar sleepsort.jar 5 7 -1 2 4 1 8 0 3 9 6

Unsorted: 5 7 2 4 1 8 0 3 9 6

Sorted : 0 1 2 3 4 5 6 7 8 9

Here's a slow implementation using only stock C Lua:

 

local t0 = os.time()

while os.time() - t0 <= n do

end

end

 

By installing LuaSocket, you can get better than 1-second precision on the clock, and therefore faster output:

 

 

function sleeprint(n)

end

end

 

Either way, the output is the same:

</pre>

 

{{Out}}

<pre>

As implemented this sample goes beyond the scope of the task as defined; it will handle negative numbers.

 

options replace format comments java crossref symbols nobinary

import java.util.concurrent.CountDownLatch

parent.getDoneLatch().countDown() -- this one's done; decrement the latch

return

'''Output:'''

<pre>

=={{header|Nim}}==

Compile with <code>nim --threads:on c sleepsort</code>:

 

proc single(n: int) =

thr.joinThreads

 

Usage:

<pre>$ ./sleepsort 5 1 3 2 11 6 4

 

=={{header|Objeck}}==

use System.Concurrency;

use Collection;

}

}

 

=={{header|Objective-C}}==

 

int main(int argc, char **argv)

}

[queue waitUntilAllOperationsAreFinished];

Rather than having multiple operations that sleep, we could also dispatch the tasks after a delay:

 

int main(int argc, char **argv)

^{ NSLog(@"%d\n", i); });

}

 

=={{header|Oforth}}==

20 milliseconds is used to (try to) handle scheduler tick on Windows systems (around 15 ms). On Linux systems (after kernel 2.6.8), this value can be smaller.

 

 

: sleepSort(l)

Channel new ->ch

l forEach: n [ #[ n dup 20 * sleep ch send drop ] & ]

 

{{out}}

3, 93, 94, 94, 95, 95, 96, 96, 97, 97, 98, 98, 99, 99, 100, 100]

</pre>

 

=={{header|Perl}}==

Basically the C code.

sleep $_;

print "$_\n";

 

 

A more optimal solution makes use of Coro, a cooperative threading library. It has the added effect of being much faster, fully deterministic (sleep is not exact), and it allows you to easily collect the return value:

$ret = Coro::Channel->new;

@nums = qw(1 32 2 59 2 39 43 15 8 9 12 9 11);

}

 

 

=={{header|Phix}}==

 

=={{header|PicoLisp}}==

===Sleeping in main process===

(make

(for (I . N) Lst

(pop 'Lst)

(task (- I)) ) )

===Sleeping in child processes===

(make

(for N Lst

(pop 'Lst)

(task (close @)) ) )

Output in both cases:

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

===Just printing (no sorted result list)===

Basically the C code.

(unless (fork)

(call 'sleep N)

(msg N)

Output:

<pre>1

=={{header|Pike}}==

 

#!/usr/bin/env pike

return;

}

Output :

<pre>

=={{header|Prolog}}==

Works with SWI-Prolog.

thread_pool_create(rosetta, 1024, []) ,

maplist(initsort, L, LID),

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

 

Output :

<pre> sleep_sort([5, 1, 3, 2, 11, 6, 3, 4]).

 

=={{header|PureBasic}}==

 

Procedure Foo(n)

Next

Print("Press ENTER to exit"): Input()

<pre>Sleep_sort.exe 3 1 4 1 5 9

1

===Python: Using threading.Timer===

 

from threading import Timer

 

print('sleep sort worked for:',x)

else:

 

;Sample output:

could be a sole translation from the original version in Bash:

{{Works with|Python 3.5+}}

from asyncio import run, sleep, wait

from sys import argv

 

if __name__ == '__main__':

Example usage:

<pre>

=={{header|Racket}}==

 

#lang racket

 

;; outputs '(2 5 5 7 8 9 10)

(sleep-sort '(5 8 2 7 9 10 5))

 

=={{header|Raku}}==

(formerly Perl 6)

 

 

{{out}}

This can also be written using reactive programming:

 

use v6;

 

{{out}}

 

=={{header|REXX}}==

<br>REXX isn't particular what is being sorted.

end /*j*/

 

 

 

end /*k*/

end /*Asort*/

<pre>

 

after sort:

</pre>

 

=={{header|Ruby}}==

 

nums = ARGV.collect(&:to_i)

threads.each {|t| t.join}

 

 

Example

 

=={{header|Rust}}==

 

fn sleepsort<I: Iterator<Item=u32>>(nums: I) {

fn main() {

sleepsort(std::env::args().skip(1).map(|s| s.parse().unwrap()));

Output:

<pre>$ ./sleepsort 50 34 43 3 2

 

=={{header|Scala}}==

 

def main(args: Array[String]): Unit = {

}.start())

 

{{out}}

 

=={{header|Sidef}}==

{Sys.sleep(i); say i}.fork;

{{out}}

<pre>% sidef test.sf 5 1 3 2 11 6 4

 

=={{header|Simula}}==

BEGIN

 

OUTIMAGE;

 

{{out}}

<pre> 1 2 3 3 4 6 7 9

=={{header|SNUSP}}==

Bloated SNUSP is ideally suited to this task, since this the variant adds multithreading and an additional dimension of data space. Sleep time is simulated by the loop delay required to copy each cell value, thereby ensuring that smaller values are printed earlier than larger values. This program requires a Bloated SNUSP interpreter which returns zero on input end-of-file.

/$>\ input until eof

#/?<\?,/ foreach: fork

/:\?-; delay /

\.# print and exit thread

 

Legend:

 

=={{header|Swift}}==

 

for i in [5, 2, 4, 6, 1, 7, 20, 14] {

}

 

{{out}}

<pre>

=={{header|Tcl}}==

===Tcl 8.5===

set count 0

proc process val {

while {$count < $argc} {

vwait count

'''Demo:'''

<pre>

6

</pre>

===Tcl 8.6: coroutine===

package require Tcl 8.6

coroutine c sleep-sort [validate $argv] ::sorted

'''Demo:'''

<pre>

=={{header|UNIX Shell}}==

{{works with|Bourne Shell}}

sleep "$1"

echo "$1"

shift

done

Usage and output:

<pre>

5

9

</pre>

 

=={{header|zkl}}==

{{out}}

<pre>