Talk:Sorting algorithms/Counting sort: Difference between revisions

 

There's a slight ambiguity in the task description (I think). The last sentence reads: "<tt>sparse arrays may limit the impact of the memory usage</tt>" which appears to allow for the use of sparse arrays, i.e. arrays that have <i>indices</i> in the range [min..max] but do NOT actually have (max-min+1) elements. The pseudocode, however, expressly requires "<tt>count: array of (max - min + 1) elements</tt>" which appears to contradict the prose.

 

I'm asking because the TCL implementation strikes me as a shade kludgy - I would write the whole thing using associative arrays, which have only the elements that are actually set. I.e. more like a "sparse array". They also have things like [incr arr(i)] so that the 'helper function' wouldn't be needed at all. They do, however require a bunch more time in element access (since there's a hash function under the hood somewhere) and in a sense dilute the purity of the implemented algorithm. On the other hand, they wouldn't obscure the algorithm all that much, as the user can <i>think of</i> the array as having all the element arr[min] to arr[max] even though most of them don't actually exist (i.e. no memory is allocated for them. They come into existence when they're incremented.)