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

Â