edited by
2,063 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)]$
edited by

2 Answers

Best answer
9 votes
9 votes

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
Answer:

Related questions