Different bases for radix sort in C

Question

I am having a difficult time understanding radix sort. I have no problems implementing code to work with bases of 2 or 10. However, I have an assignment that requires a command line argument to specify the radix. The radix can be anywhere from 2 - 100,000. I have spent around 10 hours trying to understand this problem. I am not asking for a direct answer, because this is homework. However, if anyone can shed some light on this, please do.

A few things I don't understand. What is the point of having base 100,000? How would that even work. I understand having a base for every letter of the alphabet, or every number 1-9. I just can't seem to wrap my head around this concept.

I'm sorry if I haven't been specific enough.

Answer 1

I was about to explain it in a comment, but basically you're talking about what we sometimes call "modular arithmetic." Each digit is {0...n-1} and represents that times n^k, where k is the position. 255 in decimal is 5×10⁰ + 5×10¹ + 2×10².

So, your 255 base 177 is hard to represent, but there's a 1 in the 177s place (177×10¹) and 78 in the 1s (177×10⁰) place.

As a general pseudocode algorithm, you want something like...

n = input value
digits = []
while n > 1
    quotient = n / base (as an integer)
    digits += quotient
    remainder = n - quotient * base
    n = remainder

And you might need to check the final remainder, in case something has gone wrong.

Of course, how you represent those digits is another story. MIME is contains semi-standard way for handling up through Base-64, for example.

If it was me, I'd just delimit the digits and make it clear that's the representation, but there's all of Unicode, if you want to mess around with hexadecimal-like extensions...

Answer 2

A number N in any base B is just a series of digits in the range [0, B-1]. Since we don't have enough symbols to represent all the digits in a "normal" human writing system, don't think about how it's written in characters. You'll just need to know that the digits are stored/written separately

For example 255 in base 177 is a 2-digit number in which the first digit has value 1 and the second digit has value 78 since 255₁₀ = 1×177¹ + 78×177⁰. If some culture uses this base they'll have 177 distinct symbols for the digits and they write it in only 2 digits. Since we only have 10 symbols we'll need to define some symbol to delimit the digits, which is often :. As you can see from Wolfram Alpha, 255₁₀ = 1:78₁₇₇

Note that not all people count in base 10. There exists cultures that count in base 4, 5, 6, 8, 12, 15, 16, 20, 24, 27, 32, 36, 60... so they'll have more or less symbols than most of us. However among the non-decimal bases, only base 20, 12 and 60 are most commonly used nowadays.

In base 100000 it's the same. 1234567890987654321 will be a 4-digit number written as symbols with value 1234, 56789, 9876, 54321 in order