Follow me on a journey through the code! Hope you enjoy whatever is currently holding my attention and maybe you can even learn something along the way. Everything from micro board programming on the MSP340 to openGL programming for the iPhone.
Wednesday, June 15, 2011
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:
echo"$1" } while[-n"$1"] do
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)
} 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())