Radix Sort

A post to review RadixSort. The idea is to 

 

Code

class RadixSort():

    def sort(self, nums):
        max_num = max(nums)

        exp = 1
        while max_num / exp:
            nums = self.count_sort(nums, exp)
            exp = exp * 10

        return nums

    def count_sort(self, nums, exp):
        # how many numbers have 0~9 for the current position
        digit_counts = [0] * 10

        for n in nums:
            digit_counts[(n / exp) % 10] += 1

        # accumulate counts
        for i in xrange(1, 10):
            digit_counts[i] += digit_counts[i-1]

        outputs = [0] * len(nums)
        # traverse from tail to head because we want to keep original order
        # of numbers having same digit on the current position
        for n in nums[::-1]:
            outputs[digit_counts[(n / exp) % 10] - 1] = n
            digit_counts[(n / exp) % 10] -= 1

        return outputs


if __name__ == "__main__":
    s = RadixSort()
    print s.sort([4,3,1,20,100])

 

Idea

Traverse digits: for each digit, count how many numbers have 0~9 on that digit and put the counts in a bucket (digit_count). Then, convert the bucket into accumulated counts. For example, if digit_count[0]=3 and digit_count[1]=4, then after the conversion, digit_count[1]=7 because we know numbers with 1 on that digit will be put in the position between `[3, 7)` (position starts from 0).  

Then we can reorder the numbers. We reorder from right to left (line 27~29) because we want to keep the original order of numbers which have the same digit on the current digit position.

If a number at most uses $latex d$ digits, radix sort uses time $latex O(d(n+d))$ and space $latex O(n+d)$.  

 

Reference: http://www.geeksforgeeks.org/radix-sort/

Also see MergeSort and QuickSort.