The ingenious sleep sort algorithm makes use of the system (hardware) scheduler to sort a list of data. The original version was implemented with shell scipt:
example:
Of course, it can be implemented with any language that has sleep/schedule functions. A couple of examples have been shown in this wiki.
This algorithm is not as hilarious as it seems. It only takes O(n) in the idea case (ignore the time cost in scheduling and output). This is faster than fastest comparing sort algorithm such as quick sort, which takes O(n log n). The sleep time is proportional to the hardware time. It can be scaled down dramatically. For example we can set the sleeping time to be the cpu clock period.
People have discussed the implementation of scheduling and argued that if the scheduling is achieved via priority queue it will eventually take O(n log n). But if we have sufficient "timers/schedulers", this algorithm is equivalent to bead sort.
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
example:
Of course, it can be implemented with any language that has sleep/schedule functions. A couple of examples have been shown in this wiki.
This algorithm is not as hilarious as it seems. It only takes O(n) in the idea case (ignore the time cost in scheduling and output). This is faster than fastest comparing sort algorithm such as quick sort, which takes O(n log n). The sleep time is proportional to the hardware time. It can be scaled down dramatically. For example we can set the sleeping time to be the cpu clock period.
People have discussed the implementation of scheduling and argued that if the scheduling is achieved via priority queue it will eventually take O(n log n). But if we have sufficient "timers/schedulers", this algorithm is equivalent to bead sort.
No comments:
Post a Comment