codepad

Language:

def radix_sort(A, highest=None):
    """Stable sort an array A of positive integers in logarithmic time by sorting
       the numbers one digit at a time, starting with the most significant
       digit. The sorting by digits is done using a simplified bucket sort."""
    
    # only two math functions neded
    from math import floor, log
    
    def get_digit(num, n, base=10):
        """Get the nth digit of num from the RIGHT.
            !!! note: the least significant digit is n=1
        """
        ret = 0
        if base**(n-1) <= num:
            ret = int(floor((num % base**n) / base**(n-1)))
        return ret

def num_digits(num, base=10):
        """Return the number of digits in a number."""
        return int(floor(log(num, base)) + 1)

def create_bucket_array():
        """Create an array of 10 buckets, representing the digits [0, 9]"""
        return [[],[],[],[],[],[],[],[],[],[]]
    
    def flatten_bucket_array(b):
        """Flatten the bucket array into a one-dimensional array such that the
            contents of the are in the same order as if they were in their buckets.
        """
        flat = []
        for x in b:
            flat.extend(x)
        return flat

# !!!
    # Perform the sorting
    # !!!
    
    # make sure a tuple isn't being passed in (in which case it is immutable)
    A = list(A)
    
    # should we sort the list?
    if len(A) < 2:
        return A
    
    # was the largest number supplied or not? If not, determine the largest
    # number in the list.
    if highest is None:
        highest = reduce((lambda curr_highest, i: i > curr_highest and i or curr_highest), A)

# create an initial bucket array
    digits_left = num_digits(highest)
    total_digits = digits_left + 1
    
    # while we still have digits to sort by
    while digits_left > 0:
        
        # create a bucket array
        buckets = create_bucket_array()

# go over the numbers in the array and put them into buckets
        for num in A:
            buckets[get_digit(num, total_digits - digits_left)].append(num)

# decrement what digit to sort by
        digits_left = digits_left - 1;

# flatten the bucket array, A is now (partially) sorted
        A = flatten_bucket_array(buckets)
    
    return A

if __name__ == "__main__":
    ls = [24, 5, 13, 8, 1]
    print "Unsorted list:", ls
    print "Sorted list:", radix_sort(ls)

Private [?]

Run code