ISRO CS 2023 Q.25: solution and answer

ISRO 2023 · CSQ.25 · 1 mark · MCQ

What is the maximum number of comparisons needed to sort 6 items using radix sort, if each number is a 3-digit decimal number?

(A)
120
(B)
180
(C)
210
(D)
360

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum number of comparisons is $3 \times 6 \times 10 = 180$ , so the answer is (B).

Official answer: BSource: ISRO's revised and final answer key of 16 February 2024

Radix sort (least significant digit first) does one pass per digit position. A 3-digit decimal number has $d = 3$ positions, so there are $3$ passes.
In each pass, an item is placed in one of the $k = 10$ digit buckets (0 to 9). In the worst case its digit is checked against each of the 10 possible digit values, which costs $k = 10$ comparisons per item.
One pass over $n = 6$ items therefore costs at most $6 \times 10 = 60$ comparisons.
Over all passes the maximum is $d \times n \times k = 3 \times 6 \times 10 = 180$ .
This agrees with the cost model $O (d (n + k))$ in its usual form, where the work per pass grows with the number of items times the number of possible digit values.
Check against the options: $120 = 3 \times 6 \times 6.67$ and $210 = 3 \times 6 \times 11.67$ are not whole multiples of $3 \times 6$ , and $360$ would need $k = 20$ buckets, which a decimal digit does not have. Only $180$ fits.

KEY IDEA

Radix sort makes one pass per digit, and each pass handles every item against the $k$ possible digit values, so the count is $d \times n \times k$ with $d = 3$ , $n = 6$ , $k = 10$ .

WATCH OUT FOR

Counting only $n \times d = 18$ operations, or using $k = 20$ or $k = 2$ buckets, instead of multiplying passes, items and the 10 possible decimal digit values.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 3 ISRO Sorting & hashing questions, with notes