9 Replies - 2063 Views - Last Post: 16 June 2011 - 05:17 PM

#1 Curtis Rutland  Icon User is offline

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4577
  • View blog
  • Posts: 8,019
  • Joined: 08-June 10

"Sleep sort"

Posted 15 June 2011 - 01:17 PM

Ok, yet another thing I've gotten from reddit's r/programming subreddit: the Sleep Sort! (I posted the link to a mirror, since the original actually is hosted on 4chan).

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


Example code:
./sleepsort.bash 5 3 6 3 6 3 1 4 7


Not the most efficient sort in the world, but it's non-comparative, and it's an interesting thought process.

This post has been edited by Curtis Rutland: 15 June 2011 - 01:17 PM


Is This A Good Question/Topic? 3
  • +

Replies To: "Sleep sort"

#2 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 916
  • View blog
  • Posts: 3,209
  • Joined: 12-May 09

Re: "Sleep sort"

Posted 15 June 2011 - 01:32 PM

Huh. Interesting that the runtime of such an algorithm is based on the data rather than the distribution of the data.
Was This Post Helpful? 0
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2071
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: "Sleep sort"

Posted 15 June 2011 - 05:04 PM

Ha! I love it! As inefficient as it is, it's an O(1) sorting algorithm.

sleepsort.bash 10
sleepsort.bash 3, 6, 4, 10, 7, 2

Both take the same time!
Was This Post Helpful? 0
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,714
  • Joined: 03-August 09

Re: "Sleep sort"

Posted 15 June 2011 - 06:08 PM

can you explain this to someone who doesn't know bash? e.g. me.

This post has been edited by ishkabible: 15 June 2011 - 06:09 PM

Was This Post Helpful? 0
  • +
  • -

#5 Curtis Rutland  Icon User is offline

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4577
  • View blog
  • Posts: 8,019
  • Joined: 08-June 10

Re: "Sleep sort"

Posted 15 June 2011 - 07:41 PM

Basically, for each number N, it starts a thread, then sleeps for N seconds, then prints the result. So the smallest number will sleep the shortest time, and the biggest the longest.
Was This Post Helpful? 0
  • +
  • -

#6 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: "Sleep sort"

Posted 16 June 2011 - 01:07 AM

Here is an implementation in Clojure:

(defn sleepsort [& numbers]
  (doseq [n numbers]
    (future
      (Thread/sleep (* 1000 n))
      (println n))))



With the above, a threw together a little program for you guys: http://raynes.me/hfiles/sleepsort.jar you can run it like any other executable jar file: java -jar sleepsort.jar, and pass the numbers as command line arguments like with the bash script.

Here is the source of the whole program:

(ns sleepsort.core
  (:gen-class))

(defn sleepsort [& numbers]
  (doseq [n numbers]
    (future
      (Thread/sleep (* 1000 n))
      (println n))))

(defn -main [& args]
  (apply sleepsort (map #(Integer/parseInt %) args)))



The -main part is just some glue for generating Java bytecode. In order for a jar to be executable, there has to be a Java class configured inside of it that contains a 'main' method. The combination of the :gen-class directive and the naming of this -main function results in a class being generated that contains a main function that delegates to this -main function. What this particular -main function does is take arguments (command-line arguments) that are strings, convert them to integers, and then throw them at sleepsort.

And no, this post didn't start out as a Clojure tutorial, it just grew into it.
Was This Post Helpful? 1
  • +
  • -

#7 Nightfish  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 74
  • View blog
  • Posts: 158
  • Joined: 24-May 11

Re: "Sleep sort"

Posted 16 June 2011 - 01:43 AM

Well, who knew a sorting algorithm would ever make me chuckle. We've come a long way. :) I like it.
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5942
  • View blog
  • Posts: 12,871
  • Joined: 16-October 07

Re: "Sleep sort"

Posted 16 June 2011 - 04:12 AM

That's very cute.

I'm not sure if it would work all the time, simply because thread execution time is never a guarantee.

Still, I wrote an example to try to fake it out and couldn't:
#!/bin/bash

function f() {
	sleep $1
	echo $1
}

for n in 3 3 2 2 3 3 1 1 2 2 1 1; do
	f $n &
done

wait




Also, just for testing other lists easily:
#!/bin/bash

function f() {
	sleep $1
	echo -n "$1 ";
}

function sort() {
	LIST=$1
	for n in $LIST; do
		f $n &
	done
	wait
	echo
}

DAT="3 3 2 2 3 3 1 1 2 2 1 1"
DAT=$(sort "$DAT")
echo $DAT



Of course, for numbers higher than a digit, this is torture. :P

Was fun, thanks.
Was This Post Helpful? 1
  • +
  • -

#9 Curtis Rutland  Icon User is offline

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4577
  • View blog
  • Posts: 8,019
  • Joined: 08-June 10

Re: "Sleep sort"

Posted 16 June 2011 - 06:41 AM

Well, some people are suggesting that if you have a version of sleep that can accept fractional parameters, you could divide everything by 10. But the shorter the interval, the less accurate this will be, because sleep isn't a perfect timeout. It just guarantees that the thread will sleep at least that long, but possibly longer.
Was This Post Helpful? 0
  • +
  • -

#10 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,714
  • Joined: 03-August 09

Re: "Sleep sort"

Posted 16 June 2011 - 05:17 PM

lol, that is actually pretty smart. who on earth thought to do this? it's useless but brilliant :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1