Data Structures and Algorithms in JavaScript

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Stability and Adaptability" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

## A sorting algorithm can be described as stable if it preserves the order of equal items. The algorithm is adaptive if it becomes more efficient when the inputted data is already nearly sorted. Bianca spends a few minutes demonstrating stability and adaptability before moving on to the next sorting algorithm.

Get Unlimited Access Now

Transcript from the "Stability and Adaptability" Lesson

[00:00:00]
>> Bianca Gandolfo: We're gonna talk about some other things to think about in terms of our sorting algorithm. So right now, when we're thinking about, is our algorithm good, we're only thinking about, is our algorithm fast? And in sorting, there is another thing that we want to think about, and that's the stability, and the stability preserves the order of equal items.

[00:00:20] And most or all comparison sorts can be stable if you have an order or position as part of the comparison. So here's just a quick example. So if you wanted to sort this by price, but you wanted the lighter ones to be first and so this right now, this list is sorted by weight.

[00:00:48] However, if we wanted to then sort if by price, but preserve that the weight, the lighter one will be first. Am I making sense? I"m like [SOUND]. We want to have a stable sorting algorithm, this will be an example. So here we are we have it sorted. So we can see bike B is 500 pounds or \$500 and 30 pounds and is lighter and it's the least expensive.

[00:01:14] So maybe if you are optimizing for more bang for your buck, in terms of the weight of your bike, will be faster bike probably, then you probably want bike B. So this is an example of why you'd wanna use a stable sorting algorithm. If you don't have a secondary property, or if it doesn't matter the initial order, then the stability of your algorithm doesn't matter.

[00:01:40] But it's something to keep in mind when you're presented with different needs when you're sorting. You're going to be sorting all kinds of things probably in the day to day, so maybe you will need a stable, maybe you won't. It's just something to consider. Any questions about stability?

[00:01:59]
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: All right, so adaptability is another thing to think about. This is the question of, if your list is almost sorted Is it more efficient? Or is it just as inefficient whether it's sorted or not? So if you have data that might be almost sorted, and that's something that is important to your use case, then you want to think about adaptability.

[00:02:29] Yeah? Does that all make sense?
>> Speaker 2: It seemed like with the bubble sort at the right half of it is sorted. So if you had a way of keeping track which part is sorted, then you wouldn't have to compare all the way to the end. Or is that you could, [INAUDIBLE] Never mind.

[00:02:51]
>> Bianca Gandolfo: Yeah, there are different ways to make an algorithm adaptive. So for example, we'll talk about it when we get there, but there are ways to measure, there are different strategies to make it adapt depending on which one you're using. Cool, so Lindsey asked, so stability means retaining the original sorted order?

[00:03:12] Stability means retaining the original sorted order for elements that have the same value. So in the example of our bicycles, since both of them were \$500, we retained the original order that bike B becomes before bike C.
>> Bianca Gandolfo: So it preserves some elements of the original order for the case where they have the same price.