Julius Beckmann | Bash: Sleepsort Algorithm

Some code that a friend showed to me was this:

#!/bin/bash

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

while [ -n “$1” ]
do
  f “$1” &
  shift
done

wait

Example:

./sleepsort 9 3 7 1 3 2 4 7 4 6

He called it “sleepsort”. And somehow, it really works. Not the fastest, but it works.

However, the results seem to be amusingly non-deterministic with non-numeric input:

$ for i in 1 2 3 4 5; do ./sleepsort a 1 c 3 2 b | fmt; donea c b 1 2 3c a b 1 2 3a b c 1 2 3a c b 1 2 3a c b 1 2 3$

Explanation for non-nerds:

This program “sorts” a list of numbers by taking the list, then for each item in the list pausing for an amount of time equal to each number, then displaying the number it was waiting for.

The result, at least if you give it a list of all numbers, is the original list displayed in numeric order.

The catch is that if one of the numbers you want to sort is, say, 1000000, then it’s going to take a million seconds (11.5740741 days) to run. :-)

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s