Stable vs. Unstable Sort Algorithms
A free video tutorial from Tim Buchalka
Java Python Android and C# Expert Developer - 707K+ students
4.5 instructor rating • 10 courses • 710,555 students
In this video, you'll learn about stable and unstable sort algorithms.
Learn more from the full courseData Structures and Algorithms: Deep Dive Using Java
Learn about Arrays, Linked Lists, Trees, Hashtables, Stacks, Queues, Heaps, Sort algorithms and Search algorithms
15:57:03 of on-demand video • Updated February 2020
- Learn the strengths and weaknesses of a variety of data structures, so you can choose the best data structure for your data and applications
- Code an implementation of each data structure, so you understand how they work under the covers
- Learn many of the algorithms commonly used to sort data, so your applications will perform efficiently when sorting large datasets
- Learn what’s available in the JDK for storing and sorting data, so you won’t waste time reinventing the wheel
English (techno music) Sarah: Before we move on to looking at some of the other sort algorithms, I wanna introduce the concept of a stable versus an unstable sort. When it comes to sort algorithms, there are stable sorts and there are unstable sorts. So what does this mean? Well, stable versus unstable comes into play when you have duplicate values in the data that you're sorting. For example, I have an array on the screen here and it contains two nines. There is a nine at position one and there's a nine at position three. So the question is when we sort this array, will the original ordering of the two nines be preserved? In other words, in the sorted array, will the white nine still come before the black nine or will their positions have changed so that the black nine comes before the white nine? If a sort is unstable, then that means the relative ordering of duplicate items will not be preserved. And so in an unstable sort, the black nine will end up coming before the white nine. So what will happen is the nines are sorted now, the array is sorted, but the two nines have flipped position. Their relative ordering has not been preserved. So in the original array, the white nine came before the black nine. And in the sorted array, the black nine is coming before the white nine. And so when this happens, when the relative ordering of duplicate items is not preserved when you sort, it's considered to be an unstable sort. And you'll see that some of the algorithms we look at are unstable sort algorithms. Now by contrast for a stable sort, we're starting off with the same array, but after we've sorted, the white nine still appears before the black nine, so the relative ordering of the duplicate items has been preserved and in this case it's a stable sort. Now all other things being equal, a stable sort is preferable to an unstable sort. Now you might look at this and say, "Well, who cares "if the relative ordering of the nines flip position?" And for integers, it doesn't really matter. A nine is a nine is a nine, but if you're sorting objects, it could make a difference depending on how you're using it. For example if you wanna do a sort within a sort, so for example you may first sort based on name and then you wanna sort based on age or something, well if the second sort causes the positions you got from the first sort to flip, that's going to be a problem. So for integers it doesn't matter and depending on how you're using the data it might not matter, but in some situations it will matter and you're not going to want a sort to change the ordering of duplicate items. And so as we go through and look at the sort algorithms, we'll think about whether they're stable or unstable. So how about bubble sort? Is bubble sort a stable sort algorithm or an unstable sort algorithm? Think about this for a minute. Think back to the code and how bubble sort works. The answer is that bubble sort is a stable sort algorithm and why is that? Well, when we're comparing adjacent elements, we only swap them if the element at I is greater than the element at I plus one. And so when those two nines end up next to each other and they will eventually, eventually the white nine will end up at position I and the black nine will end up at position I plus one and when we compare them, because nine is not greater than nine, we don't swap them so their positions remain the same, the relative ordering. If the algorithm said greater than equals or implementation said greater or equals, then we would swap them and that would be an unstable sort and you don't want to turn a stable sort into an unstable sort and it's really easy to do. And I have seen cases around the internet in blog posts and things like that where a stable sort algorithm has been coded to be unstable. That pesky little equals can make a big difference. So be aware of this. Be aware of this when you're reading code on the internet and be aware of this when you're writing your own code. Make sure that if a sort algorithm is stable that your implementation isn't inadvertently changing it to an unstable algorithm. So in a nutshell, a stable sort algorithm preserves the relative ordering of duplicate items and an unstable sort algorithm does not. And on that note, let's move on to the next sort algorithm. I'll see you in the next video.