retagged by
2,915 views

3 Answers

1 votes
1 votes
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.
0 votes
0 votes
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
0 votes
0 votes
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)

Related questions

1 votes
1 votes
2 answers
2
Pradeep Verma asked Jul 7, 2018
501 views
3 votes
3 votes
1 answer
3
Rohan Mundhey asked Nov 9, 2016
4,276 views
Consider an array of n integers ranges from 0, 1, ..., n5-1. What is the time complexity of RADIX-SORT when using base-10 representation?
1 votes
1 votes
1 answer
4
iarnav asked May 4, 2019
834 views
I’ve seen this wikipedia article – https://en.wikipedia.org/wiki/Comparison_sortAlso see this link – https://gateoverflow.in/32948/minimum-number-of-comparisonshttp...