Sorting algorithms/Sleep sort: Difference between revisions
No edit summary |
|||
Line 382: | Line 382: | ||
Usage and output: |
Usage and output: |
||
<lang javascript>[1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0].timeoutSort(function(n) { document.write(n + 'br'); })</lang> |
<lang javascript>[1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0].timeoutSort(function(n) { document.write(n + 'br'); })</lang> |
||
<pre> |
|||
0 |
|||
1 |
|||
2 |
|||
3 |
|||
4 |
|||
5 |
|||
6 |
|||
7 |
|||
8 |
|||
9 |
|||
</pre> |
|||
=={{header|Mathematica}}== |
|||
<lang mathematica>SleepSort = RunScheduledTask[Print@#, {#, 1}] & /@ # &; |
|||
SleepSort@{1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0};</lang> |
|||
{{Out}} |
|||
<pre> |
<pre> |
||
0 |
0 |
Revision as of 15:22, 28 March 2013
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:
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.
Ada
<lang Ada>with Ada.Text_IO; with Ada.Command_Line; use Ada.Command_Line; procedure SleepSort is
task type PrintTask (num : Integer); task body PrintTask is begin delay Duration (num) / 100.0; Ada.Text_IO.Put(num'Img); end PrintTask; type TaskAcc is access PrintTask; TaskList : array (1 .. Argument_Count) of TaskAcc;
begin
for i in TaskList'Range loop TaskList(i) := new PrintTask(Integer'Value(Argument(i))); end loop;
end SleepSort;</lang>
- Output:
./sleepsort 35 21 11 1 2 27 32 7 42 20 50 42 25 41 43 14 46 20 30 8 1 2 7 8 11 14 20 20 21 25 27 30 32 35 41 42 42 43 46 50
BBC BASIC
This does not explicitly 'sleep', but uses timers to implement the different delays. <lang bbcbasic> INSTALL @lib$+"TIMERLIB"
DIM test%(9) test%() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1 FOR i% = 0 TO DIM(test%(),1) p% = EVAL("!^PROCtask" + STR$(i%)) tid% = FN_ontimer(100 + test%(i%), p%, 0) NEXT REPEAT WAIT 0 UNTIL FALSE DEF PROCtask0 : PRINT test%(0) : ENDPROC DEF PROCtask1 : PRINT test%(1) : ENDPROC DEF PROCtask2 : PRINT test%(2) : ENDPROC DEF PROCtask3 : PRINT test%(3) : ENDPROC DEF PROCtask4 : PRINT test%(4) : ENDPROC DEF PROCtask5 : PRINT test%(5) : ENDPROC DEF PROCtask6 : PRINT test%(6) : ENDPROC DEF PROCtask7 : PRINT test%(7) : ENDPROC DEF PROCtask8 : PRINT test%(8) : ENDPROC DEF PROCtask9 : PRINT test%(9) : ENDPROC</lang>
Output:
0 1 2 2 4 31 65 83 99 782
C
<lang C>#include <stdlib.h>
- include <unistd.h>
- include <sys/types.h>
- 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>
CoffeeScript
<lang coffeescript> after = (s, f) -> setTimeout f, s*1000
- Setting Computer Science back at least a century, maybe more,
- this algorithm sorts integers using a highly parallelized algorithm.
sleep_sort = (arr) ->
for n in arr do (n) -> after n, -> console.log n
do ->
input = (parseInt(arg) for arg in process.argv[2...]) sleep_sort input
</lang> output <lang> > time coffee sleep_sort.coffee 5, 1, 3, 4, 2 1 2 3 4 5
real 0m5.184s user 0m0.147s sys 0m0.024s </lang>
D
<lang d>import std.stdio, std.conv, std.datetime, core.thread;
final class SleepSorter: Thread {
private immutable uint val;
this(in uint n) { super(&run); val = n; }
private void run() { Thread.sleep(dur!"msecs"(1000 * val)); writef("%d ", val); }
}
void main(in string[] args) {
if (args.length > 1) foreach (arg; args[1 .. $]) (new SleepSorter(to!uint(arg))).start();
}</lang>
sorting_algorithms_sleep_sort 1 6 2 5 3 4 1 2 3 4 5 6
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>package main
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.ParseInt(a, 10, 64); err != nil { lg.Print(err) wg.Done() } else { time.AfterFunc(time.Duration(i*int64(time.Second)), 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
<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
Mathematica
<lang mathematica>SleepSort = RunScheduledTask[Print@#, {#, 1}] & /@ # &; SleepSort@{1, 9, 8, 7, 6, 5, 3, 4, 5, 2, 0};</lang>
- Output:
0 1 2 3 4 5 6 7 8 9
Objeck
<lang objeck> use System.Concurrency; use Collection;
bundle Default {
class Item from Thread { @value : Int; New(value : Int) { Parent(); @value := value; }
method : public : Run(param : System.Base) ~ Nil { Sleep(1000 * @value); @value->PrintLine(); } }
class SleepSort { function : Main(args : String[]) ~ Nil { items := Vector->New(); each(i : args) { items->AddBack(Item->New(args[i]->ToInt())); }; each(i : items) { items->Get(i)->As(Item)->Execute(Nil); }; } }
} </lang>
Objective-C
<lang objc>#import <Foundation/Foundation.h>
int main(int argc, char **argv) {
NSOperationQueue *queue = [NSOperationQueue new]; while (--argc) { int i = atoi(argv[argc]); [queue addOperationWithBlock: ^{ sleep(i); NSLog(@"%d\n", i); }]; } [queue waitUntilAllOperationsAreFinished];
}</lang>
Perl
Basically the C code. <lang Perl>1 while ($_ = shift and @ARGV and !fork); sleep $_; print "$_\n"; wait;</lang>
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:
<lang Perl>use Coro;
$ret = Coro::Channel->new;
@nums = qw(1 32 2 59 2 39 43 15 8 9 12 9 11);
for my $n (@nums){ async { Coro::cede for 1..$n; $ret->put($n); } }
print $ret->get,"\n" for 1..@nums;</lang>
Perl 6
Using the MuEvent module from the Perl 6 module ecosystem.
<lang Perl6>use MuEvent;
for <6 8 1 12 2 14 5 2 1 0> -> $item {
MuEvent::timer( after => $item, cb => sub { say $item } );
}
MuEvent::run;</lang>
Output
0 1 1 2 2 5 6 8 12 14
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]
Racket
<lang racket>
- lang racket
- accepts a list to sort
(define (sleep-sort lst)
(define done (make-channel)) (for ([elem lst]) (thread (λ () (sleep elem) (channel-put done elem)))) (for/list ([_ (length lst)]) (channel-get done)))
- outputs '(2 5 5 7 8 9 10)
(sleep-sort '(5 8 2 7 9 10 5)) </lang>
REXX
This sort will accept any manner of numbers, or for that matter, any character string as well.
REXX isn't particular what is being sorted.
<lang rexx>/*REXX program implements a sleep sort (with numbers entered from C.L.)*/
numeric digits 300 /*over the top, but what the hey!*/
/* (above) ... from vaudeville.*/
- .= /*placeholder for the array of #s*/
stuff='1e9 50 5 40 4 1 100 30 3 12 2 8 9 7 6 6 10 20 0' /*alphabetically*/ parse arg numbers /*let the user specify on the CL.*/ if numbers= then numbers=stuff /*Not specified? Then use default*/ N=words(numbers) /*N is the number of numbers. */ w=length(N) /*width of N (for nice output).*/ say N 'numbers to be sorted:' numbers /*informative informational info.*/
do j=1 for N /*let's start to boogie-woogie. */ #.j=word(numbers,j) /*plug in one number at a time. */ if datatype(#.j,'Numeric') then #.j = #.j/1 /*normalize it if num.*/ call fork /*REGINA REXX supports FORK func.*/ call sortItem j /*start a sort for array number. */ end /*j*/
do forever while \inOrder(N) /*wait for the sorts to complete.*/ call sleep 1 /*1 sec is the min effective time*/ end /*forever while*/ /*well, other than zero seconds. */
m=max(length(#.1),length(#.N)) /*width of smallest | largest num*/ say; say 'after sort:'; indent=left(,20) /*same as: COPIES(' ',20) */
/*∙∙∙but LEFT pads [much faster]*/ do k=1 for N /*list (sorted) array's elements.*/ say indent 'array element' right(k,w) '───>' right(#.k,m) end /*k*/
exit /*stick a fork in it, we're done.*/ /*───────────────────────────────────SortItem subroutine────────────────*/ sortItem: procedure expose #.; parse arg ? /*sorts single item.*/
do Asort=1 until \switched /*cook until cooked.*/ switched=0 /*honky-dorey so far*/ do i=1 while #.i\== & \switched if #.? >= #.i then iterate /*this one ok*/ parse value #.? #.i with #.i #.? switched=1 /*yup, we done switched one.*/ end /*i*/ if Asort//?==0 then call sleep switched /*sleep if last*/ end /*Asort*/
return /*Sleeping Beauty awakes. Not to worry: (c) = circa 1697.*/ /*───────────────────────────────────InOrder subroutine─────────────────*/ inOrder: procedure expose #.; parse arg howMany /*is array in order? */
do m=1 for howMany-1; next=m+1; if #.m>#.next then return 0 end /*m*/ /*keep looking for fountain of yut*/
return 1 /*yes, indicate with an indicator.*/</lang> output when using the default input
19 numbers to be sorted: 1e9 50 5 40 4 1 100 30 3 12 2 8 9 7 6 6 10 20 0 after sort: array element 1 ───> 0 array element 2 ───> 1 array element 3 ───> 2 array element 4 ───> 3 array element 5 ───> 4 array element 6 ───> 5 array element 7 ───> 6 array element 8 ───> 6 array element 9 ───> 7 array element 10 ───> 8 array element 11 ───> 9 array element 12 ───> 10 array element 13 ───> 12 array element 14 ───> 20 array element 15 ───> 30 array element 16 ───> 40 array element 17 ───> 50 array element 18 ───> 100 array element 19 ───> 1000000000
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]
Rust
<lang rust>extern mod std; use std::timer::sleep; use std::uv::global_loop;
fn main() {
for os::args().tail().each |&arg| { do task::spawn { let n = uint::from_str(arg).get(); sleep(global_loop::get(), n); io::println(arg); } }
}</lang>
Scala
<lang scala>object SleepSort {
def sort(nums:Seq[Int])=nums foreach {n => scala.concurrent.ops.spawn{ Thread.sleep(500*n) print(n+" ") } }
def main(args:Array[String])={ sort(args map (_.toInt)) }
}</lang> Example:
> scala SleepSort 1 9 8 7 6 5 3 4 5 2 0 0 1 2 3 4 5 5 6 7 8 9
Tcl
<lang tcl>#!/bin/env tclsh set count 0 proc process val {
puts $val incr ::count
}
- Schedule the output of the values
foreach val $argv {
after [expr {$val * 10}] [list process $val]
}
- 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
<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