number of comparison require in RADIX sort

Question

I am not able to get this formula  (number of input * number of digit *base of number )

I am not getting how base of number is important ?

Thanks :)

Answer 1

Let, Base of the number system be B.

       There are total N items

        Each item is of D digits each.

We can use Bucket sort as the stable sort algorithm for performing Radix sort. So we need B buckets from 0 to (B-1). (The digits could range from 0 to B-1 in a Number system with base = B)

From each item, we take one digit (start either from LSB or MSB), so there will be total N digits (as there are N items) that we need to put in the bucket. For each digit, we need B comparisons to put that digit into its corresponding bucket(as there are B buckets). So, for all N digits we need (B*N) comparisons.

Each number has D digits,  so we need to perform the above step for all the D digits. So, total D*(B*N) comparisons are there.

After that there will be no comparisons to complete the process, we just need to simply traverse each bucket once to get the sorted list.

Answer 2

Suppose you have N numbers

and base of the number is B

and you have D digits of the number

 

You have to traverse array n times

And as you have d digits, you have to repeat this process D times

and now when you have base B then each number has its bucket B which has to be filled in each iteration.

 

SO in totality, you have N*B*K comparisons

Answer 3

W = log(base 10 n^k) ... (This will give number of iterations)

Radix sort uses counting sort , suppose counting sort uses 10 buckets.

Therefore total time taken for each iteration = initialisation of 10 buckets + putting n elements in bucket = O(n)

Therefore total time ,

Tc = total iteration X time taken for each iteration = klog(n) X n = nklog(n) ...( Base of log is 10)