+1 vote
84 views

Given array is: 120 , 231 , 417 , 343 , 542 , 998 , 675 , 196.

Since radix sort starts sorting by the LSB and iteratively goes towards the MSB.

So, after one pass the array will look like this: 120 , 231 , 542 , 343 , 675 , 196 , 417 , 998.

Now in the second pass, we have to take care of the ties(when two digits are same) as there are digits which are same.

So, after second pass the array will look like this: 417 , 120 , 231 , 542 , 343 , 675 , 196 , 998.

Now we have to apply bubble sort on the entire array. So each adjacent elements a[i] and a[j] will be swapped if a[j] > a[i] and j > i.

So, the array will look like this: 120 , 231 , 417 , 343 , 542 , 196 , 675 , 998.

Hence option D.
answered by Active (1.1k points) 1 5 11
selected by
How did you break the tie in the second pass?They mentioned FIFO so i did what we would do in stable sort.The number that came first in the original array was higher up than the number that came later on.But my answer was incorrect.
Breaking the ties means if two elements are having same value then whichever comes first will be processed first.

You are making the mistake of checking the fcfs order with original array and not the present array. At 2nd pass, the present sequence will be considered for fcfs.

Is it clear now ?
Why did u apply bubble sort at last. As there are 3 digits it needs 3 passes here so in 2nd pass it would be OPTION C