Basic Radix sort via Counting Sort

radix_sort.py

#!/usr/bin/env python
import math
import random
from itertools import filterfalse, tee

def get_digit(number, digit):
    # Given number, pull the digit-th digit (starts at 0).
    # e.g. get_digit(120, 2) => 1
    # e.g. get_digit(120, 0) => 0
    return number // 10**digit % 10

def counting_sort(seq, digit, radix=10):
    sorted_list = [0] * len(seq)
    buckets = [0] * radix

    # now iterate through and build a histogram of values by digit
    for elem in seq:
        place = get_digit(elem, digit)
        print("Elem: {} Digit: {} Place: {}".format(elem, digit, place))
        buckets[place] += 1

    print("buckets {}".format(buckets))

    # calculate starting index for each key
    total = 0
    for i in range(radix):
        oldCount = buckets[i]
        buckets[i] = total
        total += oldCount

    print("histo index buckets: {}".format(buckets))

    for elem in seq:
        print("Elem: {} - Putting something into element: sorted_list[{}]".format(elem, buckets[get_digit(elem, digit)]))
        sorted_list[buckets[get_digit(elem, digit)]] = elem
        buckets[get_digit(elem, digit)] += 1
        print("digit buckets {}".format(buckets))

    print("Sorted list: {}".format(sorted_list))

    #return sorted_list
    for i in range(len(seq)):
        print("seq[{}]={} sorted_list[{}]={}".format(i, seq[i], i, sorted_list[i]))
        seq[i] = sorted_list[i]



def filter_negpos(seq):
    t1, t2 = tee(seq)
    return list(filterfalse(lambda i: i >= 0, t1)), list(filter(lambda i: i>= 0, t2))

# A radix sort
# can operate different ways
# Usually order by radix and then sort via counting or bucket sort,
# but radix sort can be used exclusively
# For efficiency, use counting sort as the sorting subfunction
def digit_radix_sort(seq):
    negatives, positives = filter_negpos(seq)


    max_number = max(positives)
    min_number = min(negatives)


    max_digits = int(math.log(max_number, 10))
    min_digits = int(math.log(abs(min_number), 10))

    for i in range(max_digits + 1):
        # now we're [0, max_number] range
        counting_sort(positives, i)

    for i in range(min_digits + 1):
        counting_sort(negatives, i)

    return negatives + positives


if __name__ == '__main__':
    #ulist = [int(100000 * random.random()) for i in range(100)]
    ulist = [-1, 35, -24, 245, 958, 380, 243, 223, 224, 253]
    sorted_list = digit_radix_sort(ulist)
    print(sorted_list)