Counting sort (Python, functional)

From LiteratePrograms

Other implementations: C | C# | Haskell | Java | Python, functional | Scala

Counting sort is a very simple sort that is efficient for lists that take on only a small number of values. A linear-time algorithm based on array indexing, it trades time for space.

For the purposes of this article, we'll use character elements that are restricted to integer digits, but the same ideas apply to any type. We begin by declaring a function that takes as arguments the sequence to be sorted, and the domain (in sort order) that we are sorting by.

<<counting sort>>=
lambda seq, dom: generate result

Next, we perform the sort. There are two phases to counting sort. In the first phase, count occurrences, we count the number of times each element of the domain occurs in the sequence. Note that we are comparing the elements of the sequence with the elements of the domain, not with each other — this is what makes counting sort not a comparison sort.

NB. Due to an apparent numpy bug with equal.outer we currently use newaxis by hand to perform this operation

<<count occurences>>=
sum(seq[:,newaxis] == dom[newaxis,:], 0)

In the second phase, generate result, we use repeat to repeat each element of the domain as many times as we counted it in the original sequence.

<<generate result>>=
repeat(dom, count occurences)

Finally we package things up with a few tests:

<<counting_sort.py>>=
from numpy import *
csort=counting sort
if __name__ == "__main__":
        a=lambda str: fromstring(str,dtype="S1")
        print "counting sort of 3.1415926535897931"
        print csort(a("3.1415926535897931"), a("0123456789"))
        print "counting sort of 2.71828182846"
        print csort(a("2.71828182846"), a("0123456789"))

that we expect to produce the following output:

counting sort of 3.1415926535897931
['1' '1' '1' '2' '3' '3' '3' '4' '5' '5' '5' '6' '7' '8' '9' '9' '9']
counting sort of 2.71828182846
['1' '1' '2' '2' '2' '4' '6' '7' '8' '8' '8' '8']

---

this definition of counting sort may appear terse, but it is actually an expansion of the APL equivalent, in which the definition of csort would be something along the lines of

Download code