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

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

1 Answer

+2 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 (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 Feb 2017
  1. Arjun

    4898 Points

  2. Bikram

    4102 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2288 Points

  6. Smriti012

    2222 Points

  7. Arnabi

    1946 Points

  8. Debashish Deka

    1920 Points

  9. mcjoshi

    1614 Points

  10. sh!va

    1462 Points

Monthly Topper: Rs. 500 gift card

20,793 questions
25,951 answers
59,557 comments
21,976 users