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

asked in Algorithms by Active (1.2k points)   | 60 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 Junior (953 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 Jan 2017
  1. Debashish Deka

    7906 Points

  2. Habibkhan

    4736 Points

  3. Vijay Thakur

    4474 Points

  4. sudsho

    4318 Points

  5. saurabh rai

    4200 Points

  6. Arjun

    3638 Points

  7. Bikram

    3500 Points

  8. santhoshdevulapally

    3480 Points

  9. GateSet

    3228 Points

  10. Sushant Gokhale

    3116 Points

Monthly Topper: Rs. 500 gift card

18,944 questions
23,897 answers
52,122 comments
20,213 users