CODEWITHSUNDEEP
radix-sortbucket-sort
Manish
Manish

Reputation: 2337

How many comparisons are needed in worst case if we have to sort 7 numbers each of 4 digit?

How many comparisons are needed in worst case if we have to sort 7 numbers each of 4 digit ?(Radix sort) Options are- 40,38,47,280 .

My solution-I have taken 10 buckets( 0 to 9)(linked list) . Then for every number for ith digit I have put it into Bucket corresponding to its digit's value. Then I collected those numbers into array back. This process is repeated for all the digits and thus my original array got sorted. Total number of comparisons= 10*4=40 (10 because I iterated through all buckets to look for corresponding bucket).

Now the problem is in the book by Timothy J Williams its given no of comparisons= no of digits* no of numbers * no of buckets= 4*7*10=280. I am not able to comprehend up. Can someone please explain how this came.

Upvotes: 4

Views: 4258

Answers (1)

Saiteja
Saiteja

Reputation: 21

It is true that radix sort is not a comparison based algorithm. Here comparisons account to the comparisons involved in iterations. First, we need to traverse the array of 7 elements and keep the digit of each number in the appropriate bucket. Here in order to traverse the array we need 7 comparisons. After placing all the elements in the buckets from 0-9 we need to traverse all the buckets from 0-9 and arrange the elements in order according to their bucket number, this takes 10 comparisons to traverse the bucket from 0-9. Now we have to repeat this process for all the 4 digits of 7 elements. So, the total number of comparisons would be 7*10*4 = 280

Upvotes: 2

Related Questions