0:01
Finally, we talk about stability. This is really one of the rules of the game but
it's much easier to talk about in the context of the real algorithms that we've
seen so far. And really it doesn't make sense if you don't know about comparators
which we just introduced. So, the typical application that I just used as an example
is say the set of student records. So we have them sorted by name and this is say,
something that we do just before assigning final grades. Maybe the third line there
is the final grade. So it's all fine sorted by name and but then in order to
distribute it out to the people leading it to the sections, what we want to do is
sort by the second fields, sort by section. The problem is that when we do
that, it messes up the sort by name and that's annoying. You might assume that
once you have it sorted by name, then when you sorted by the second field then it
should maintain the sort of by name for all that have equal keys in that second
field. Actually not all sorts preserve that property that is called stability.
And clearly, it's worthwhile to think about for your application whether you
want or need a stable sort. And so, it's an annoying surprise for many people and
many applications. So a stable sort is a sort that preserves the relative order of
items with equal keys. Whichever sort are stable? That's an interesting question
that we'll take a look at now. The quick bottom line is that insertion sort and
mergesort are stable but not selection sort or Shellsort. And even within that
bottom line, there's implementations that maybe are not stable. You have to
carefully check the code to be sure. Always, in this class, we have an exercise
or exam question is this version of this sort stable or not? So, students learn to
recognize whether the code is stable. So this is just another typical example where
we've got things sorted by time, and then what we want to do is maybe these are
important events. People buying tickets to a rock concert and I'm going to sort by
location what we'd hope is that it would keep the sort by time but this is a
non-stable sort that doesn't do bad so then out in the location they're going to
have to resort it if they use one of these. But if they use a stable sort, then
it stay sorted by time and lots of applications you want stability. Alright,
so let's just look at each of the algorithms that we've considered so far.
Insertion Sort. Insertion Sort is stable. Why is it stable? Well, we never move
equal items pass one another. In this example here, when we get A1, well that's
so in this case, the index is just one that appears in the array, it's just A's
and B's. When we get our second A, we stop the sort as long as we're not less. We're
equal, we're not less, we stop it so we never move an equal item pass another one.
If this less or less than or equal, then it wouldn't work. Or if we did the other
way around and proceeded accordingly. So, equal items never move past each other in
this code so therefore insertion sort is stable. But selection sort is not stable.
Usually way, the way to show that a sort is not stable and it's just to see if it
has a long distance exchange that might move an item pass some equal item. So,
[cough] in this case, for example, for selection sort, when we do that first
exchange oops, [cough] where we found the minimum A and B is in position zero. We
did a long distance exchange and that catapulted that first item past any item
that it might be equal putting them out of order. And that's may not get fixed so
that sort is not stable. It might move items past some equal item and leave a
result where items that are equal or in different order than they were originally
in the file. Selection Sort is not stable. Shellsort also has long distance exchange
and so it's not stable. It moves keys past other keys that could be equal and so its
easy to construct examples showing that Selection Sort is not stable. And what
about Mergesort? Mergesort is stable well, it's stable as long as the merge operation
is stable and that operation is going to be stable depending on how we code it.
And, and in our code, if the two keys are equal, it takes from the left subarray so
that means that, it will always take the, if there's a two sets of equal keys, it
will preserve the relative order and that's enough to show that the merge
operation is stable and then therefore Mergesort is stable. Stability is an
important property in sorting algorithms. Mergesort is not only efficient, it's also
Kevin WayneSenior Lecturer
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
