Counting sort (Haskell)

From LiteratePrograms

Jump to: navigation, search
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. (Although the implementation here is very inefficient. I'm not even sure if it qualifies as a counting sort.)

We begin by declaring a function that takes as arguments the list to be sorted, and the domain (in sort order) that we are sorting by as another list. Note that we require that the type that we are sorting be able to be compared for equality, as we will need that to "count" later. This is reflected in the type of the function: 

<<counting sort>>=
csort :: (Eq a) => [a] -> [a] -> [a]
csort seq dom =
  generate result

Next, we perform the sort. First, I use the List Monad to iterate through all the elements of the domain, in order: 

<<generate result>>=
do x <- dom
   count occurences

Then, I count the number of times that element occurs in the sequence. In this case, I simply find those occurrences and extract them with "filter". 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. 

<<count occurences>>=
filter (x ==) seq

The occurrences for each element of the domain will now be grouped together, sorted by the order of the elements in the domain.

Finally we package things up with a few tests: 

<<counting_sort.hs>>=
counting sort
main :: IO ()
main = do putStrLn "counting sort of 3.1415926535897931"
          putStrLn $ csort "3.1415926535897931" "0123456789"
          putStrLn "counting sort of 2.71828182846"
          putStrLn $ csort "2.71828182846" "0123456789"

that we expect to produce the following output: 

counting sort of 3.1415926535897931
11123334555678999
counting sort of 2.71828182846
112224678888


For an implementation that runs through the list just twice see [[1]]

Download code
Retrieved from "http://literateprograms.org/Counting_sort_%28Haskell%29"
Views