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

asked in Algorithms by Active (1.4k points) 11 33 61 | 84 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) 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

Related questions

+3 votes
0 answers
1
asked in Algorithms by manu00x Veteran (14.9k points) 6 19 58 | 93 views
0 votes
2 answers
3


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8280 Points

  4. srestha

    6300 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4352 Points

  9. sushmita

    3970 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Regular Rishabh Gupta 2
Popular Question Sunil8860
Reader Rajesh Veeranki 2
Notable Question rahul sharma 5
Commentator Shivam Chauhan
Notable Question set2018
Nice Comment srestha
Notable Question set2018
Regular Shankar Jha
Popular Question Shubhanshu
27,325 questions
35,177 answers
84,123 comments
33,280 users