Interesting Stuff : Sleep sort

A new sorting algorithm, don't know who invented it but it works well atleast for positive integers. You can follow the link for original version of the article on web http://dis.4chan.org/read/prog/1295544154 . The algorithm is simple. For sorting a list of positive numbers, simply create a thread for each one of them and then set out the thread for sleep some constant times the number assigned to it. And finally print out the numbers as threads wakes up from the sleep. The first one to wake up is the smallest one and last one is the largest. Simple as that. Now the fun part, lets implement that in python.
import thread
import time
 
def sleepy_guy ( number ):
    time.sleep(number)
    print number
    return
 
def sleep_sort(items):
    try:
        for item in items:
            thread.start_new_thread(sleepy_guy, (item,))
    except:
        print "Error!!! Unable to start the thread!!"
 
i_want_it_sorted = [2,4,1,8,3,9,12,57]
sleep_sort(i_want_it_sorted)
# main thread should be alive until last thread is alive
time.sleep(max(i_want_it_sorted)+1);
Ok, after the code lets talk about the time complexity of the algorithm. The algorithm is no good to be used for the real world sorting purpose. The algorithm has variable time complexity of O((max_input)+n). max_input is due to the sleep function we are calling and the additional n is due to the loop we are using for thread creation. For negative numbers, we can make slight improvements by adding the modulus lowest number to all of the inputs i.e. by making all the numbers positive. I haven't tried that in my code yet but you can try that one. Further to reduce the time required for the sorting we can first normalize the data set and proceed with the algorithm. This algorithm is just for fun. Hope you enjoyed the post.

No comments :

Post a Comment