Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sleep Sort: an amazing sorting algorithm!!
#!/usr/bin/env python2.6
# -*- encoding: utf8 -*-
'''
An advanced version of Sleep Sort.
The original idea is from: http://coolshell.cn/articles/4883.html
Use the concept of radix sort to speed it up.
The newer version references WanCW's implementation in Ruby:
https://gist.github.com/1044476
This implementation only allows positive integers.
'''
import sys
import threading
import time
import Queue
__author__ = 'fcamel'
# The bigger, the faster. But a bigger value has higher risk to get incorrect results.
FASTER_RATE = 1000.0
def position(sleep_second, numbers, queue):
time.sleep(sleep_second / FASTER_RATE)
for n in numbers:
queue.put(n)
def sleep_sort(numbers):
def sort_a_round(numbers, index):
buckets = [[] for _ in range(10)]
for n in numbers:
sleep_second = int(('%15s' % n).replace(' ', '0')[index])
buckets[sleep_second].append(n)
threads = []
for i, ns in enumerate(buckets):
th = threading.Thread(target=position, args=(i, ns, queue))
th.start()
threads.append(th)
for th in threads:
th.join()
numbers = []
while not queue.empty():
numbers.append(queue.get())
return numbers
queue = Queue.Queue()
max_n_digit = max(map(len, numbers))
for i in range(1, max_n_digit + 1):
numbers = sort_a_round(numbers, -i)
return numbers
def main():
if len(sys.argv) <= 1:
return
for n in sleep_sort(sys.argv[1:]):
print n
if __name__ == '__main__':
# Usage:
#
# $ ./sleep_sort.py 23 20 25 512 987 98 5
# 5
# 20
# 23
# 25
# 98
# 512
# 987
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment