Wednesday, June 15, 2011

Sleep Sort

Every so often a certain notorious image board (which shall not be named, lest it is summoned) pops out a gold nugget. I preset sleep sort:

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



It works like this: Imagine you had a room full of people and you each hand them a number between let say 1 and 100. Whatever number that person gets, they wait for that amount of time in minutes and then they write their number down on a white board.

People with the highest numbers will wait for much longer times and people with small numbers will wait less. So the person who got 1, will only wait for one minute and write down their number, the person who got 2 has to wait longer than the person who got 1 to write their number and so on. There you have it sleep sort, instead of minutes it works in seconds.


It's an interesting and new idea on sorting. The problem with it is that it has a terrible worst case and best case. It takes as long as the highest number to sort. So if you wanted to sort some numbers such as 1, 2, 3, 78943893 it would take 78943893 seconds to sort 4 numbers.


This could be fixed by calling some kind of notify whenever a number was printed. This actually seems like a perfect application for a parallel processing. Have each thread sleep, but upon printing out a sorted value, notify all the threads which are still sleeping that they can proceed to process the next one in line with the least amount of sleep time remaining.

What is more fascinating about this is the simplicity of it all. I doubt we'll see this taking over as the default sorting procedure but it is a very humorous and elegant piece of code.


I've whipped up some quick Java code which should re-create this bash script but haven't tested it. Later on I plan to see if I can write it up as a parallel program with the fixes I've suggested.


public void f(int s)
{
    Thread.sleep(s);
    system.out.println(s);
}
public void main()
{
    String sortMe = "9 0 4 56 5 9 1 2 3 64 7 9";
    StringTokenizer t = new StringTokenizer(sortMe, " ");
    while (t. hasMoreTokens())
    {
        f(t.nextElement());
    }

}

7 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. Looks okay, not that effective though ;)

    ReplyDelete
  3. Looking forward to the bash script test.

    ReplyDelete
  4. Wow this stuff just goes over my head every time. Wish I knew more about coding and things like that though.

    ReplyDelete
  5. Im trying to learn more about coding and software, but i specialize in the hardware field. :b great article though, i hope to learn something from you.

    ReplyDelete