GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
73 views

asked in Algorithms by Active (1.3k points)   | 73 views

1 Answer

+3 votes
Best answer
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)  
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 ?


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users