Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

What is it about the structure of counting sort that only makes it work on integers?

Surely strings can be counted?

''' allocate an array Count[0..k] ; initialize each array cell to zero ; THEN '''
for each input item x:
    Count[key(x)] = Count[key(x)] + 1
total = 0
for i = 0, 1, ... k:
    c = Count[i]
    Count[i] = total
    total = total + c

''' allocate an output array Output[0..n-1] ; THEN '''
for each input item x:
    store x in Output[Count[key(x)]]
    Count[key(x)] = Count[key(x)] + 1
return Output

Where above does the linear time break down if you try to use counting sort on strings instead (assuming you have strings of fixed length)?

share|improve this question
    
Title improvements welcome, btw. –  The Unfun Cat Nov 12 '12 at 21:35
    
How do you store counters if you don't have integers? In which order to you progress when writing them to the output. Also, the algorithm is only in linear time if $k$ is in $O(n)$. –  Raphael Nov 13 '12 at 15:55

1 Answer 1

up vote 16 down vote accepted

If you naively apply the algorithm you need an encoding $f$ of strings of length $m$ into integers such that $s_1≤s_2$ iff $f(s_1)≤f(s_2)$. The bound on these integers is necessarily at least $c^m$ where $c$ is the number of possible characters.

You then have a complexity in $O(nc^m)$ where $n$ is the number of elements to be sorted. This could be interesting when $c^m$ is not too big compared to the usual bound $\log n$, which is possible, in very peculiar cases.

In general, one would prefer the bound $O(n\log n)$ which does not depend on the length of your strings and in general much faster than $O(nc^m)$. To give a formal comparison between them, the former would be $O(s\log s)$ and the latter $O(sc^s)$ where $s$ is the size of the input.

However what is possible if you know that you will have a number of different strings no greater than some $k$, and that there will be a lot of occurrences of the same strings, is to build a correspondence between these strings and $\{1,\dots,k\}$ on which you will apply the counting sort, thus obtaining a complexity of $O(kn)$ i.e. linear (since $k$ is constant). But in this case the counting sort is not the only one reaching a linear complexity, for example all algorithms using balanced trees can be adapted to be linear, even insertion sort which is quadratic in the worst case, becomes linear.

share|improve this answer
    
Yes, excellent answer. I had some inklings, but this also pointed out many things I hadn't thought about. –  The Unfun Cat Nov 12 '12 at 22:24
    
Of course, you could apply the algorithm without such $f$ but with a (total) order. –  Raphael Nov 13 '12 at 15:56
    
@Raphael really? I thought you would need more than a total order; to be non-comparison based, you also need an index i.e. an integer for each string. –  Joe Nov 15 '12 at 7:16
    
The bound isn't necessarily $c^m$, if you have more information, e.g. a dictionary of valid strings or some known structure on the strings. –  Joe Nov 15 '12 at 7:19
    
@Joe A total order implies a numbering (if the universe is countable). You can either create a numbering in expected linear time (a hashtable) or assume you have a computable (and hopefully efficient) enumeration. –  Raphael Nov 15 '12 at 13:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.