Genius sorting algorithm: Sleep sort

Man, am I a genius. Check out this sorting algorithm I just invented.


#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

>>120
You reinvented Bogosort: http://en.wikipedia.org/wiki/Bogosort

>>121
Ah damnit.

>>2 >>5
if accept that floating-point sleep and scrpipt have only to sort with natural numbers...

#!/bin/bash
function f() {
  sleep $(echo "($2 - 1) + $1 / 10 ^ $2" | bc -l)
  echo "$1"
}
while [ -n "$1" ]
do
  f "$1" $(echo -n "$1" | wc -c) &
  shift
done
wait


example: 218382 -> 5.218382 seconds.

>>118
What are you talking about?

O(n*k) with fixed k is just O(n) for all nonzero finite k.

Cosmological sort

Wait for the universe to collapse and be replaced by a universe in which the input is in sorted order

>>125
http://en.wikipedia.org/wiki/Everett_many-worlds_interpretation

>>125
You reinvented (Quantum) Bogosort, again: http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort

>>125
What if the new universe would have the same initial conditions and thus the input will always be in unsorted order?

>>128
Destroy the universe, take another one.

I think of sleepsort as a deferred kernelspace-sort.

Hello.
I invented a new sorting algorithm in the Cloud age.
It's called the "Cloud Sort（Google App Engine TaskQueue Sort）".
http://d.hatena.ne.jp/kissrobber/20110527/1306508583

This use GAE TaskQueue(eta) instead of Sleep.
(http://code.google.com/appengine/docs/python/taskqueue/tasks.html)

Specifications:
・The order of the sort result is not guaranteed.
・Sometimes, a part of sorted data is duplicated.

・The order of the sort result is not guaranteed.
・Sometimes, a part of sorted data is duplicated

( ≖‿≖)

It's O(n²) under the hood because the kernel has to scan the list of waiting threads every pass through the idle loop. It's only O(n) if you have n CPUs, in which case you should be using n-way mergesort, since that has already been shown to give O(log n) time.

Remember, guys: the OS is not magic, and just because you didn't take an OS design course doesn't make you a wizard.

Only LispM designers get to be wizards.

>>133
Sorry, correction about the merge sort; I was remembering it incorrectly: http://drdobbs.com/high-performance-computing/229400239

Only LispM designers get to be faggots.

The Jews are after me

A very similar approach is MRSI sort using an array of AMOS delayed event generators.

>>94

Here's a quick (3-minute) attempt at Perl golf:

#!/usr/bin/perl -l -MTime::HiRes=sleep
$SIG{CHLD} = sub { };
push @p, (fork or sleep($_), print, exit) for @ARGV;
waitpid $_, 0 for @p;

>>44

Has flaws: first, you get the numbers without spacing, which is bad; second, you get them to stdout instead as the procedure's result, which is un-Racket-like. Here are some alternatives, indented/linebreaked for clarity, not brevity:

(define (sleepsort1 lst)
  (with-input-from-string
   (with-output-to-string
    (λ () (map thread-wait
               (map (λ (x) (thread (λ () (sleep x) (printf "~a " x)))) lst))))
   (λ () (port->list read))))

(define (sleepsort2 lst)
  (define me (current-thread))
  (map thread-wait
       (map (λ (n) (thread (λ () (sleep n) (thread-send me n))))
            lst))
  (sequence->list (in-producer thread-try-receive false?)))

(define (sleepsort3 lst)
  (define-values (i o) (make-pipe-with-specials))
  (map thread-wait
       (map (λ (n) (thread (λ () (sleep n) (write-special n o))))
            lst))
  (close-output-port o)
  (port->list read-char-or-special i))

The second is my favorite, I think, but it assumes nothing else will be sending to its thread. If you didn't mind (require racket/async-channel), you could replace (current-thread) with (make-async-channel), thread-send with async-channel-put, and thread-try-receive with (λ () (async-channel-get me)) which solves that problem.

HI REDDIT!!!

hi paul graham!!

>>173

nice.

The fags code like cookies dipped in milk. Soggy and gross.

Fixed. Sorts including negative values, sorts any numbers within 1 second.

#!/bin/bash
function f() {
    sleep $(echo "scale=10; 1/(1+1.1^(-$1))" | bc)
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

Greetings from reddit.

Your creation is much better than anything I've ever seen on /r/programming before!

function sleepsort() {
    for (var i = 0, il = arguments.length; i < il; i++) {
        (function(args, index) {
            setTimeout(function() {
                document.body.innerHTML += args[index] + ', ';
            }, args[index]);
        }(arguments, i));
    }
};

sleepsort(5, 26, 3, 845, 1276, 536, 825, 77);

Don't think there was a Python version, so here we go.
It's 'optimized' by waiting only 1/4th of the seconds
in each thread.


#!/usr/bin/python

import sys, time, threading

def sleepit(val):
    time.sleep(val/4.0)
    print val
   
[ threading.Thread(target=sleepit, args=[int(a)]).start() for a in sys.argv[1:] ]

   var numbers  = process.argv.slice(2)
     , output   = []
     , negative = []

   for (var i=0, ln=numbers.length; i<ln; i++){
      var n = +numbers[i]
      setTimeout((function(n){ return function(){
         if (n<0) negative.unshift(n)
         else output.push(n)
         if (output.length + negative.length === numbers.length) {
            return console.log(negative.concat(output))
         }
      }})(n), Math.abs(n)/1000)
   }

    $ node sleepsort -2 1 0.1 4 -1 7 -3 9
    [ -3, -2, -1, 0.1, 1, 4, 7, 9 ]

DIGG SENT ME HERE!

PLEASE DO NOT INCREASE THE POPULATION OF /prog/ BEYOND 3, THANKS!!!

F#:
let sleepsort (xs: int list) =
  for x in xs do Async.Start <| async { Threading.Thread.Sleep x; printfn "%d" x }

All this talk of new different versions, yet I see no code.

it is vulnerable to race conditions

Ruby:
def f(i)
    sleep i
    puts i
end

[3,2,3,4,2,1].each do |i|
  Kernel.fork {
    f(i)
  }
end

Hacker New up in this bitch

>>152
That's been addressed at least 3 times already.

vals = [100, 25, 3,2,1]

sorted = (vals.min..vals.max).to_a.select{ |i|
  vals.include? i
}

>>131
LOL

you are sick

Doesn't work.
./sleepsort.bash 1.00001 1
1.00001
1

>>159
Serious question, are you autistic or just retarded?