"""
Template for Counting Sort
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.
Argument type:
element[]
Return type:
element[]
"""
def count(a):
"""
Returns an array of integers 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).
Argument type:
element[]
Return type:
int[]
"""
class element:
"""
Class to represent tuples (key, data).
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) + ")"