Skip to content

Instantly share code, notes, and snippets.

@3kwa
Created December 13, 2015 00:42
Show Gist options
  • Save 3kwa/9d8eb385e44a0a6071f9 to your computer and use it in GitHub Desktop.
Save 3kwa/9d8eb385e44a0a6071f9 to your computer and use it in GitHub Desktop.
"""
A radix sort implementation to illustrate:
+ testing with doctest
+ __main__
+ yield
+ refactoring for legibility (your future self may thank you)
+ Python is __magic__
+ PEP 8
+ ...
"""
from collections import deque
def radix(sequence):
"""Sort sequence of positiver integers using LSD radix sort
>>> radix([])
[]
>>> radix([1])
[1]
>>> radix([2, 1, 3, 1, 2])
[1, 1, 2, 2, 3]
>>> radix([11, 1])
[1, 11]
>>> radix([11, 1, 2])
[1, 2, 11]
>>> radix([2000, 30, 10])
[10, 30, 2000]
>>> import random
>>> data = [random.randint(1, 10000) for _ in range(100)]
>>> all(r == t for r, t in zip(radix(data), sorted(data)))
True
"""
buckets = Buckets(range(10))
buckets[0] = sequence
N = max_number_of_digits(sequence)
for n in range(1, N + 2):
for element in buckets:
digit = least_significant_nth_digit(element, n)
buckets[digit].append(element)
return list(buckets[0])
class Buckets(object):
"""Buckets of Queue(s) associated to keys from the instantiating sequence
Iterable consumes its values (frozen) in order of the instantiating sequence
then appending order (FIFO over mutliple queues).
>>> buckets = Buckets(range(10))
>>> buckets[0]
Queue([])
>>> buckets[0] = [1, 2, 3]
>>> buckets[0]
Queue([1, 2, 3])
>>> for elements in buckets:
... pass
"""
def __init__(self, keys):
self.keys = keys
self._dict = {key: Queue() for key in keys}
def __getitem__(self, key):
return self._dict[key]
def __setitem__(self, key, sequence):
for element in sequence:
self._dict[key].append(element)
def __iter__(self):
man = [(key, len(self._dict[key])) for key in self.keys]
for key, count in man:
for _ in range(count):
yield self._dict[key].pop()
def max_number_of_digits(sequence):
"""
>>> max_number_of_digits([1, 45, 890, 2])
3
>>> max_number_of_digits([])
0
"""
return len(str(max(sequence))) if sequence else 0
def least_significant_nth_digit(integer, n):
"""
>>> least_significant_nth_digit(23, 1)
3
>>> least_significant_nth_digit(23, 2)
2
>>> least_significant_nth_digit(23, 3)
0
"""
i = 1
man = integer
while i <= n and man > 0:
result = man % 10
man /= 10
i += 1
if i > n:
return result
else:
return 0
class Queue(object):
"""An iterable FIFO queue
append at the back
pop from the front
>>> queue = Queue()
>>> for i in range(10):
... queue.append(i)
>>> queue.pop()
0
>>> len(queue)
9
"""
def __init__(self):
self._deque = deque()
def append(self, value):
self._deque.append(value)
def pop(self):
return self._deque.popleft()
def __iter__(self):
for value in self._deque:
yield value
def __len__(self):
return len(self._deque)
def __repr__(self):
return 'Queue({0})'.format(list(self._deque))
if __name__ == '__main__':
import doctest
doctest.testmod()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment