'''This version of counting sort is in place, including if you
are sorting on an integer key in a larger object.
The only added memory is two int lists with the size of the range of keys.
Other versions only specifically sort integers in place or
for compound data with a key, require a second list of
the same size as the original to copy into.
All the versions are O(list size) + O(size of range of keys).
This version is not stable, while stability can be preserved
in versions copying to a new array.
'''
def ident(x): # for a simple sort of plain integers
return x
def countingSort(d, keyFunc=ident):
'''list d, where for any element elt in d
keyFunc(elt) generates integers in a limited range to sort on.
In place except for two arrays of the size of the range of values.
'''
m = keyFunc(min(d, key=keyFunc))
M = keyFunc(max(d, key=keyFunc))
size = M - m + 1
counts = [0]*size
nextI = [0]*size
for elt in d:
counts[keyFunc(elt)-m] += 1
for i,c in enumerate(counts[:-1]): # sorted starting index for each key
nextI[i+1] = nextI[i] + c
# counts[i] now contains number of elt's still to place with value i+m
# nextI[i] is the location to put the next elt with value i+m
# embedded functio definitionns can use the local variables above
def passCorrect(i):
while counts[i] and keyFunc(d[nextI[i]]) == i+m: # in right place
counts[i] -= 1 # do bookkeeping
nextI[i] += 1 # for next placement
def insert(i, elt):
'put an element where it belongs; return the element replaced'
tmp = d[nextI[i]] # one to replace
d[nextI[i]] = elt
nextI[i] += 1
counts[i] -= 1
return tmp
def swapAround(i):
'follow a loop of misplaced elements, each going where it belongs'
tmp = d[nextI[i]] # key is not i+m
while keyFunc(tmp) != i+m: # place tmp where it belongs
j = keyFunc(tmp) - m # find the section to put it in
passCorrect(j) # don't overwrite ones in place
tmp = insert(j, tmp) # swap out next misplaced element ...
insert(i, tmp) # now replace original tmp: have right key
# back to countingSort
for i in range(size): # for each key value i+m
while counts[i]: # while not all keys i+m in place
passCorrect(i) # skip ones that are in place
if counts[i]: # if more need to be placed
swapAround(i) # follow a loop of misplaced elements
def main():
print('Illustrate counting sort with given sort key.\n')
a = [2, 5, 2, 3, 1, 3, 1, 6, 5]
print('Initial:', a)
countingSort(a)
print('Sorted with identity sort key:', a)
b = [(6, 2), (2, 5), (3, 2), (6, 1), (3, 1), (6, 5)]
print('\nInitial:', b)
def kf0(tup):
return tup[0]
def kf1(tup):
return tup[1]
countingSort(b, kf0)
print('Sort on first field:', b)
countingSort(b, kf1)
print('Sort on second field:', b)
main()