What is the benefit of a classification algorithm being stable?

Asked

Viewed 186 times

2

A classification algorithm (Sorting) is said to be stable if it maintains the relative order of the elements with equal keys.

I think my question is, what is the benefit of maintaining this relative order?

Can someone give an example?

Source

algorithm classification

  • Is that it? https://answall.com/q/188646/101 Is that it? https://answall.com/q/325088/101

  • The linked questions helped me understand something I never really understood about stability: that what is preserved is the order of the elements with equal keys in relation to the order in which they were in the initial provision, and not an intrinsic order of the secondary classification criterion. However, as far as I have seen, no example of the link can be an example of use that shows a benefit, but rather examples invented for example.

  • 1

    But the benefit is just this, there’s nothing to it.

  • Got it. It’s just that in the original question (in English, linked above) they try to give concrete examples.

  • 1

    They only adorned the example, but in essence it is the same, because it has nothing to invent

  • 1

    If the relative order of the equal keys is important to you, using a stable algorithm ensures predictability in the result. I guess that’s just the benefit.

  • 1

    I also think it’s just that, I think the spirit of the question was to know a situation (as far as possible not invented) in which this is put into practice.

  • There is a detail of stable ordering that I have not seen mentioned in the linked questions. If you need to sort by two keys, say K1 and K2, in that order, but you cannot do the composite check, you can first sort by K2 and, using a stable sort, then sort by K1.

  • My answer didn’t work? I guess I’d better delete it, right?

  • @RHERWOLF Not fully answered but help, if I were you would not delete.

  • In summary, he said that stable sorting saves the filling and handling of an additional field for tiebreaker that is required in unstable sorting algorithms to give stability. I have also given a practical example where stability may be needed. Some doubt somewhere?

  • On second thought, the example answers my question. I will accept it.

Show 7 more comments

1 answer

2


There are cases where a new element in a structure has the same sort key value as an existing one and it is more convenient to place it right after it, as in cases where it is fairer when what comes first is prioritized. But if at the time of insertion the sorting key is not known yet, only later will it be determined?

For it is, alternatively one can insert the elements at the end, ie in order of insertion in the structure to only then apply an ordering by the desired key, but still taking into account as tiebreaker this insertion order, from which in fact the sorting started. For this, there are two options.

(1) Add to each element a field that is the starting sorting index to use it as a tiebreaker.

(2) Use a stable algorithm, thus not needing that field.

An example of a problem that suggests a ranking of the former over the latter in a structure is the ranking of candidates competing for vacancies. If there is only one spot left for two equally performing candidates on the exams, is it fairer to give it to the one who was ahead of the registration or the one who took the longest to register? In a competition for a post usually several tie-breakers are used, but if the grades in the ratings are all the same then at the end of the day it is fairer that those who register first have priority in the reception of vacancies, correct?

Browser other questions tagged algorithm classification

You are not signed in. Login or sign up in order to post.