recategorized
17,102 views
2 votes
2 votes

The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):

  1. 45
  2. 72
  3. 360
  4. 450
recategorized

3 Answers

12 votes
12 votes

Actually radix sort is not a comparison based algorithm. ===> No.of comparissions = 0

So, here comparisons account to the comparisons involved in iterations.

given that, it is 5 digit number ( remember that totally we have 5 iterations due to no.of digits =5 )

       ===> let the number represented as u . w . x . y . z

given that, it is octal number ===> we have 8 buckets, numbered as b$_0$,b$_1$,b$_2$,...b$_7$.

therefore on first iteration, we have sort by LSB..

z is compared by 0, if yes then it dropped into b$_0$.

z is compared by 1, if yes then it dropped into b$_1$.... like that

z is compared by 7, if yes then it dropped into b$_7$.

    ∴ For a number, on first iteration, it takes maximum 8 (due to 8 buckets only)

Given that we have 9 numbers, So on first iteration total comparissions = 8*9 = 72

Totally we have five iterations ===> total comparissions = 72 * 5 = 360.

 

Note that, what is the Time Complexity of Radix Sort ?

Time Complexity = O( d . n . ( time required to match a element to a bucket ) )

generally, we use hashing to match the elements to the bucket, then Time Complexity = O( d . n . ( O(1) ) ) = O( d . n )

But in this question, it is take O(Base) time to match the elements to the bucket, then Time Complexity = O(d n B )

where d - indicates, no.of digits and n indicates number of elements and B indicates Base of the elements.

edited by
0 votes
0 votes

 THE MAX. NO. OF COMPARISON IS NO. OF ITEMS × RADIX × NO. OF DIGITS

         Sort items→ 9

         Octal number having→  5 digits

         The octal number system base value is → 8

         So, items*digits*base= 9*5*8=360

Related questions

1 votes
1 votes
3 answers
1
Pooja Khatri asked Jul 13, 2018
3,337 views
Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are ______ and _____ r...
0 votes
0 votes
2 answers
2
Pooja Khatri asked Jul 13, 2018
8,888 views
A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the ...
0 votes
0 votes
2 answers
3
Pooja Khatri asked Jul 13, 2018
2,570 views
Which of the following algorithms solves the single-source shortest paths?Prim's algorithmFloys-Warshall algorithmJohnson's algorithmDijkstra's algorithm
0 votes
0 votes
8 answers
4