Mix of radix sort and sleep sort. (inspired by @fcamel)
#!/usr/bin/env ruby | |
# | |
# fcamel's implementation in Python: https://gist.github.com/1042867 | |
# | |
def radix_sleep_sort(numbers) | |
max_length = numbers.map {|n| n.to_s.length }.max | |
return numbers if max_length.nil? | |
(1..max_length).each { |i| | |
groups = {} | |
numbers.each { |n| | |
digit = (n.to_s[-i,1] || '0').to_i | |
groups[digit] = [] unless groups.has_key?(digit) | |
groups[digit] << n | |
} | |
sorted_groups = [] | |
threads = groups.map { |s, g| | |
Thread.new { | |
sleep(s / 1000.0) | |
sorted_groups << g | |
} | |
} | |
threads.each { |t| t.join } | |
numbers = sorted_groups.flatten | |
} | |
return numbers | |
end | |
if __FILE__ == $0 | |
# Usage: | |
# | |
# $ ./radix_sleep_sort.rb 23 20 25 512 987 98 5 | |
# 5 | |
# 20 | |
# 23 | |
# 25 | |
# 98 | |
# 512 | |
# 987 | |
puts radix_sleep_sort(ARGV.map {|s| s.to_i}) | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment