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

2 Answers

Best answer
9 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:
Position:
Show:

Related questions

3 3 votes
2 2 answers
3.3k
3.3k views
Tesla! asked Feb 4, 2018
3,311 views
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference?If the best algorithm for $B$ takes exponenti...
5 5 votes
2 answers 2 answers
2.7k
2.7k views
Tesla! asked Feb 5, 2018
2,655 views
Consider the following function that takes as input a sequence $A$ of integers with n elements,$A ,A , \dots ,A[n]$ and an integer $k$ and returns an integer value. The f...
1 1 vote
2 2 answers
1.1k
1.1k views
Tesla! asked Feb 5, 2018
1,140 views
We are given a sequence of pairs of integers $(a_1, b_1),(a_2, b_2), \dots ,(a_n, b_n)$. We would like to compute the largest $k$ such that there is a sequence of numbers...
2 2 votes
1 1 answer
655
655 views
Tesla! asked Feb 5, 2018
655 views
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and ...