This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Is the input a list?
• Yes
• Can we assume the inputs are valid?
• Check for None in place of an array
• Assume array elements are ints
• Do we know the max digits to handle?
• No
• Are the digits base 10?
• Yes
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None -> Exception
• [] -> []
• [128, 256, 164, 8, 2, 148, 212, 242, 244] -> [2, 8, 128, 148, 164, 212, 242, 244, 256]

## Algorithm¶

Sample input: [1, 220, 122, 112]

• We'll evaluate each digit starting with the ones position
• [1, 220, 122, 112]
• Bucket 0: 220
• Bucket 1: 1
• Bucket 2: 122, 112
• Result: [220, 1, 122, 112]
• [220, 1, 122, 112]
• Bucket 0: 1
• Bucket 1: 112
• Bucket 2: 220, 122
• Result: [1, 112, 220, 122]
• [1, 112, 220, 122]
• Bucket 0: 1
• Bucket 1: 112, 122
• Bucket 2: 220
• Result: [1, 112, 122, 220]

Bucketing example: 123

• Ones
• 123 // 10^0 = 123
• 123 % 10 = 3
• Tens
• 123 // 10^1 = 12
• 12 % 10 = 2
• Hundreds
• 123 // 10^2 = 1
• 1 % 10 = 1

Complexity:

• Time: O(k*n), where n is the number of items and k is the number of digits in the largest item
• Space: O(k+n)

Misc:

• Not in-place
• Most implementations are stable

If k (the number of digits) is less than log(n), radix sort can be faster than algorithms such as quicksort.

## Code¶

In [1]:
class RadixSort(object):

def sort(self, array, base=10):
if array is None:
raise TypeError('array cannot be None')
if not array:
return []
max_element = max(array)
max_digits = len(str(abs(max_element)))
curr_array = array
for digit in range(max_digits):
buckets = [[] for _ in range(base)]
for item in curr_array:
buckets[(item//(base**digit))%base].append(item)
curr_array = []
for bucket in buckets:
curr_array.extend(bucket)
return curr_array


## Unit Test¶

In [2]:
%%writefile test_radix_sort.py
import unittest

def test_sort(self):
array = [128, 256, 164, 8, 2, 148, 212, 242, 244]
expected = [2, 8, 128, 148, 164, 212, 242, 244, 256]
print('Success: test_sort')

def main():

Overwriting test_radix_sort.py

%run -i test_radix_sort.py

Success: test_sort