Created
March 9, 2014 03:59
-
-
Save jordanhudgens/9442741 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#python2.6 < | |
from math import log | |
def getDigit(num, base, digit_num): | |
# pulls the selected digit | |
return (num // base ** digit_num) % base | |
def makeBlanks(size): | |
# create a list of empty lists to hold the split by digit | |
return [[] for _ in xrange(size)] | |
def split(a_list, base, digit_num): | |
buckets = makeBlanks(base) | |
for num in a_list: | |
# append the number to the list selected by the digit | |
buckets[getDigit(num, base, digit_num)].append(num) | |
return buckets | |
# concatenate the lists back in order for the next step | |
def merge(a_list): | |
new_list = [] | |
for sublist in a_list: | |
new_list.extend(sublist) | |
return new_list | |
def maxAbs(a_list): | |
# largest abs value element of a list | |
return max(abs(num) for num in a_list) | |
def radixSort(a_list, base): | |
# there are as many passes as there are digits in the longest number | |
passes = int(round(log(maxAbs(a_list), base)) + 1) | |
new_list = a_list[:] | |
for digit_num in range(passes): | |
new_list = merge(split(new_list, base, digit_num)) | |
return new_list |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment