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