Hacker News Reader

Comment by namdnay | Hacker News Reader

I think it's different in that you don't care what the output of a hash is, as long as it's sufficiently unique or whatever. Whereas here the buckets are are intimately tied to the input. It's more of an arithmetic hack I'd say, as it only works on decimal numbers

View on HN

Radix sort works in any base

Radix sort also works on strings, etc. (anything that can be lexicographically ordered)

I guess it could work well for sets of strings that you know will not go above a certain length? But after that it might become painful, i.e. the algorithm complexity will start depending on the maximum string length

Well, it just means you actually see the complexity. Normally that is hidden in a strcmp, which is actually O(L) for the Length of the shorter string.

No, the point of radix sort is that you don't have to do comparisons. Radix sort on strings is the same as radix sort on numbers, just with more buckets.

What they mean is that a standard comparative sort can also become very long if the strings are long, because strong compare can take up to the length of the string to return a result

It's the same problem when working with numbers, since you have to assume some maximum number of digits as well. Radix sort essentially treats numbers as zero-padded strings.

When sorting single words consisting only of the letters A-Z, for example, you can think of it as the same thing but with 26 buckets (27 if you pad with spaces instead of As) instead of 10. Or you can think of it as a specific subset of numbers in base 36, if that makes more sense to you.

Sorry, I meant decimal as in excluding some rationals e.g. not 1/3.

Reply on news.ycombinator.com