Geek Answers Handbook

How many comparisons are needed in the worst case, if we need to sort 7 numbers, each of 4 digits?

How many comparisons are needed in the worst case, if we need to sort 7 numbers, each of 4 digits (sorted by Radix) Possible options: 40,38,47,280.

My solution: I took 10 buckets (0 to 9) (linked list). Then for each number for the ith digit, I put it in a bucket corresponding to its digit value. Then I gathered these numbers into an array back. This process is repeated for all digits, and thus my original array is sorted. Total number of comparisons = 10 * 4 = 40 (10, because I repeated all the buckets to find the corresponding bucket).

Now the problem is the book of Timothy J. Williams, which he did not give comparisons = no numbers * no numbers * no buckets = 4 * 7 * 10 = 280. I can not understand. Can someone explain how this happened.

+4
source share
1 answer

It is true that radix sorting is not a comparison based algorithm. This compares the score with comparisons related to iterations. First, we need to cross an array of 7 elements and store the digit of each number in the corresponding bucket. Here, to cross the array, we need 7 comparisons. After placing all the elements in buckets from 0 to 9, we need to go through all the buckets from 0-9 and arrange the elements according to their number of buckets, it will take 10 comparisons to move the bucket from 0-9. Now we must repeat this process for all 4 digits of 7 elements. Thus, the total number of comparisons will be 7 * 10 * 4 = 280

+1
source

More articles:


All Articles