Skip to content

Instantly share code, notes, and snippets.

@fcamel fcamel/sleep_sort.py
Created Jun 23, 2011

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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.