Stable vs unstable sorting
What defines a stable sorting algorithm?
This question has already been talked a little about what is stable and unstable ordering, but I still do not realize the advantage of using an unstable.
In which cases can we use an unstable sort? Is it always preferable to use a stable?
Depending on the data structure we use, do we need to be careful with unstable sorting?
An sorting algorithm is considered stable when it manages to preserve the register order of equal keys, in other words if the records appear in the ordered sequence in the same order as they are in the initial sequence.
This explanation I did not understand, what would the records be? Ex:
int vec[5]={4,2,5,1,7};
If I wanted to sort this vector what would it be to preserve the order of the records?
1 answers
Here I go by Occam knife: if all solutions give the same result I choose the simplest. Which may be the most efficient.
In general if you have 2 "Jose" and nothing else that differentiates them, so which of them enters first after classified and therefore whatever algorithm to use. But if the sorted list being assembled needs to consider the order of entry into the list then the stable algorithm is mandatory. Basically the question you should ask is whether the position in the original listing is part of the tiebreaker or not, if it is an important information need to use the stable algorithm.
Any unstable sorting algorithm can be turned into stable if you modify the sorting key by manually adding the position, as long as it is available.
As always, it's a question of what guarantees you need and what commitments you accept. Some algorithms give up some efficiency to offer stability. But this is not guaranteed, depending on the comparison the stable can have more efficiency than the unstable.
Is not that you need to be careful with a given data structure, but rather careful with the desired need.
For example, a scattering table has no clear position, so it makes no sense to require stability if this is the source.
Remembering that there can only be instability in case of a tie. If the structure guarantees to have single key a stability is guaranteed for any algorithm. So the example cited whether the algorithm is stable or not, after all there is no tie in 2 elements of it. Read again the question linked because you have not yet understood what stability is quoted.
I particularly prefer the stable whenever it makes no difference or that it doesn't matter, but it is common to make some difference.
It may be that in the future you need the original order, even if you do not need it now, there would have to redo the rating in the original, if it is available.
Furthermore stable algorithms tend to have more predictability of resource consumption.