"""
Copyright 2016, University of Freiburg
Fabian Kuhn
"""
def countingsort_stable(a):
""" Sort array a of elements using the counting sort algorithm.
The idea is to first use subroutine 'count' to determine the ranges
where elements of equal keys must be located in the sorted array.
Then copy those elements into the output array in a stable manner.
>>> a = [Element(3, 'abc'), Element(1, 'xyz')]
>>> a = a + [Element(3, 'ghf'), Element(2, 'tyy')]
>>> countingsort_stable(a)
[(1, 'xyz'), (2, 'tyy'), (3, 'abc'), (3, 'ghf')]
>>> countingsort_stable([])
[]
"""
# compute array 'counts' of seperators with subroutine
counts = count(a)
# sort elements in a into a temporary array b
b = [None for i in range(len(a))]
for i in range(len(a)):
b[counts[a[i].key]] = a[i]
counts[a[i].key] += 1
return b
def count(a):
"""
Returns the an array of length max_key+1, where max_key
is the biggest key of elements in the input array a.
The output array should contain seperators between
blocks of elements with the same key in the sorted array a.
The idea to compute this without actually sorting 'a' is as follows.
First, count the number of occurences of each key in array counts.
Second, for k = 0 to max_key replace counts[k] with
counts[0] + ... + counts[k-1] (whereas counts[0] = 0).
>>> a = [Element(3, 'abc'), Element(1, 'xyz')]
>>> a = a + [Element(3, 'ghf'), Element(2, 'tyy')]
>>> count(a)
[0, 0, 1, 2]
"""
# find maximum key in a
max_key = 0
for i in range(len(a)):
if a[i].key >= max_key:
max_key = a[i].key
# create array counts which stores the number of occurrences of each key
counts = [0 for i in range(max_key + 1)]
for i in range(len(a)):
counts[a[i].key] += 1
# replace counts of the number of occurrences of each particular
# key by counts of the number of occurrences of keys of at most a
# particular value.
sum = 0
for i in range(max_key + 1):
tmp = counts[i]
counts[i] = sum
sum += tmp
return counts
class Element:
"""
Class to represent tuples (data, key).
Key needs to be an non-negative integer.
"""
def __init__(self, key=0, data=None):
self.key = key
self.data = data
def __repr__(self):
return "(" + repr(self.key) + ", " + repr(self.data) + ")"