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.