in Algorithms edited by
2,041 views
7 votes
7 votes

A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points

$[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].$

We sort these in ascending order by the second coordinate. Which of the following corresponds to a stable sort of this input?

  1. $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(6, 5, 9),(3, 5, 7)]$
  2. $[(0, 2, 5),(3, 5, 7),(6, 1, 4),(6, 5, 9),(7, 1, 8),(9, 0, 9)]$
  3. $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
  4. $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$
in Algorithms edited by
by
2.0k views

1 comment

Thankyou so much brother. Your cleared my all doubts
1
1

2 Answers

9 votes
9 votes
Best answer

A stable sort preserves the order of values that are equal with respect to the comparison function.

What does that mean?

That is whenever we compare two keys(values) for sorting and if they are equal, the order in which they will appear in the sorted list is same as they appeared in the original list. That is, if we have $x_1$ and $x_2$ in our list, such that $x_1 = x_2$ (they are equal when compared) and $x_1$ appeared before $x_2$ in the list (our list is something like: $... , x_1, ... , x_2, ...$).

Then the sorted list will be like: $..., x_1, x_2, ...$ and NOT like: $..., x_2, x_1, ...$ . That is, in the sorted list $x_1$ comes before $x_2$. Then such a sort is known to be stable.

https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important

Now the given list:

$[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)]$

is sorted in ascending order by the second coordinate. We have to compare second coordinate to get the ordering.

Answer should be:

(c) $[(9, 0, 9),(7, 1, 8),(6, 1, 4),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$

Notice here that when compared, $(7, 1, 8)$ is equal to $(6, 1, 4)$ (compare second coordinates). So, in the sorted list $(7, 1, 8)$ comes before $(6, 1, 4)$, same order as in original list.

Similarly for $(3, 5, 7)$ and $(6, 5, 9).$

edited by

1 comment

Stable Sorting :

in simple words 

if the duplicate elements are present then relative position of the element doesn't change after  sorting .

means=>        2(a),  3(a)  ,  1,  0 ,  6 ,  8 ,  2(b) ,  3(b) ,  2(c) before sorting

After Sorting =>      0 ,  1 ,  2(a)   , 2(b) , 2(c)  , 3(a)  ,  3(b) ,   6  ,  8  relative ordering of 2 and 3 is matter

1
1
0 votes
0 votes

Answer:

Answer:

Related questions