Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,172 --> 00:00:02,755 (techno music) 2 2 00:00:05,220 --> 00:00:06,800 Before we move on to looking at 3 3 00:00:06,800 --> 00:00:08,430 some of the other sort algorithms, 4 4 00:00:08,430 --> 00:00:10,240 I wanna introduce the concept 5 5 00:00:10,240 --> 00:00:14,790 of a stable versus an unstable sort. 6 6 00:00:14,790 --> 00:00:16,610 When it comes to sort algorithms, 7 7 00:00:16,610 --> 00:00:19,630 there are stable sorts and there are unstable sorts. 8 8 00:00:19,630 --> 00:00:20,830 So what does this mean? 9 9 00:00:20,830 --> 00:00:24,240 Well, stable versus unstable comes into play 10 10 00:00:24,240 --> 00:00:26,310 when you have duplicate values 11 11 00:00:26,310 --> 00:00:27,760 in the data that you're sorting. 12 12 00:00:27,760 --> 00:00:29,870 For example, I have an array on the screen here 13 13 00:00:29,870 --> 00:00:31,390 and it contains two nines. 14 14 00:00:31,390 --> 00:00:33,200 There is a nine at position one 15 15 00:00:33,200 --> 00:00:34,930 and there's a nine at position three. 16 16 00:00:34,930 --> 00:00:37,930 So the question is when we sort this array, 17 17 00:00:37,930 --> 00:00:42,930 will the original ordering of the two nines be preserved? 18 18 00:00:42,940 --> 00:00:45,970 In other words, in the sorted array, 19 19 00:00:45,970 --> 00:00:49,780 will the white nine still come before the black nine 20 20 00:00:49,780 --> 00:00:52,320 or will their positions have changed 21 21 00:00:52,320 --> 00:00:54,870 so that the black nine comes before the white nine? 22 22 00:00:54,870 --> 00:00:57,640 If a sort is unstable, 23 23 00:00:57,640 --> 00:01:01,250 then that means the relative ordering of duplicate items 24 24 00:01:01,250 --> 00:01:03,560 will not be preserved. 25 25 00:01:03,560 --> 00:01:06,620 And so in an unstable sort, 26 26 00:01:06,620 --> 00:01:10,820 the black nine will end up coming before the white nine. 27 27 00:01:10,820 --> 00:01:14,890 So what will happen is the nines are sorted now, 28 28 00:01:14,890 --> 00:01:16,220 the array is sorted, 29 29 00:01:16,220 --> 00:01:19,350 but the two nines have flipped position. 30 30 00:01:19,350 --> 00:01:21,740 Their relative ordering has not been preserved. 31 31 00:01:21,740 --> 00:01:23,260 So in the original array, 32 32 00:01:23,260 --> 00:01:25,710 the white nine came before the black nine. 33 33 00:01:25,710 --> 00:01:27,030 And in the sorted array, 34 34 00:01:27,030 --> 00:01:29,910 the black nine is coming before the white nine. 35 35 00:01:29,910 --> 00:01:31,390 And so when this happens, 36 36 00:01:31,390 --> 00:01:33,600 when the relative ordering of duplicate items 37 37 00:01:33,600 --> 00:01:35,780 is not preserved when you sort, 38 38 00:01:35,780 --> 00:01:38,720 it's considered to be an unstable sort. 39 39 00:01:38,720 --> 00:01:41,270 And you'll see that some of the algorithms we look at 40 40 00:01:41,270 --> 00:01:43,680 are unstable sort algorithms. 41 41 00:01:43,680 --> 00:01:46,450 Now by contrast for a stable sort, 42 42 00:01:46,450 --> 00:01:48,770 we're starting off with the same array, 43 43 00:01:48,770 --> 00:01:50,740 but after we've sorted, 44 44 00:01:50,740 --> 00:01:54,700 the white nine still appears before the black nine, 45 45 00:01:54,700 --> 00:01:57,580 so the relative ordering of the duplicate items 46 46 00:01:57,580 --> 00:02:00,990 has been preserved and in this case it's a stable sort. 47 47 00:02:00,990 --> 00:02:03,270 Now all other things being equal, 48 48 00:02:03,270 --> 00:02:07,610 a stable sort is preferable to an unstable sort. 49 49 00:02:07,610 --> 00:02:10,417 Now you might look at this and say, "Well, who cares 50 50 00:02:10,417 --> 00:02:13,660 "if the relative ordering of the nines flip position?" 51 51 00:02:13,660 --> 00:02:15,520 And for integers, it doesn't really matter. 52 52 00:02:15,520 --> 00:02:17,270 A nine is a nine is a nine, 53 53 00:02:17,270 --> 00:02:19,750 but if you're sorting objects, 54 54 00:02:19,750 --> 00:02:22,590 it could make a difference depending on how you're using it. 55 55 00:02:22,590 --> 00:02:25,060 For example if you wanna do a sort within a sort, 56 56 00:02:25,060 --> 00:02:27,960 so for example you may first sort based on name 57 57 00:02:27,960 --> 00:02:30,070 and then you wanna sort based on age or something, 58 58 00:02:30,070 --> 00:02:33,990 well if the second sort causes the positions you got 59 59 00:02:33,990 --> 00:02:36,180 from the first sort to flip, 60 60 00:02:36,180 --> 00:02:38,090 that's going to be a problem. 61 61 00:02:38,090 --> 00:02:40,550 So for integers it doesn't matter 62 62 00:02:40,550 --> 00:02:42,610 and depending on how you're using the data 63 63 00:02:42,610 --> 00:02:43,590 it might not matter, 64 64 00:02:43,590 --> 00:02:46,110 but in some situations it will matter 65 65 00:02:46,110 --> 00:02:48,380 and you're not going to want a sort 66 66 00:02:48,380 --> 00:02:51,300 to change the ordering of duplicate items. 67 67 00:02:51,300 --> 00:02:55,040 And so as we go through and look at the sort algorithms, 68 68 00:02:55,040 --> 00:02:57,710 we'll think about whether they're stable or unstable. 69 69 00:02:57,710 --> 00:02:59,520 So how about bubble sort? 70 70 00:02:59,520 --> 00:03:02,800 Is bubble sort a stable sort algorithm 71 71 00:03:02,800 --> 00:03:04,930 or an unstable sort algorithm? 72 72 00:03:04,930 --> 00:03:06,130 Think about this for a minute. 73 73 00:03:06,130 --> 00:03:09,060 Think back to the code and how bubble sort works. 74 74 00:03:09,060 --> 00:03:13,220 The answer is that bubble sort is a stable sort algorithm 75 75 00:03:13,220 --> 00:03:14,320 and why is that? 76 76 00:03:14,320 --> 00:03:17,250 Well, when we're comparing adjacent elements, 77 77 00:03:17,250 --> 00:03:21,700 we only swap them if the element at I 78 78 00:03:21,700 --> 00:03:24,630 is greater than the element at I plus one. 79 79 00:03:24,630 --> 00:03:27,870 And so when those two nines end up next to each other 80 80 00:03:27,870 --> 00:03:28,840 and they will eventually, 81 81 00:03:28,840 --> 00:03:31,940 eventually the white nine will end up at position I 82 82 00:03:31,940 --> 00:03:35,210 and the black nine will end up at position I plus one 83 83 00:03:35,210 --> 00:03:36,980 and when we compare them, 84 84 00:03:36,980 --> 00:03:39,140 because nine is not greater than nine, 85 85 00:03:39,140 --> 00:03:42,660 we don't swap them so their positions remain the same, 86 86 00:03:42,660 --> 00:03:43,900 the relative ordering. 87 87 00:03:43,900 --> 00:03:47,000 If the algorithm said greater than equals 88 88 00:03:47,000 --> 00:03:49,790 or implementation said greater or equals, 89 89 00:03:49,790 --> 00:03:52,370 then we would swap them and that would be an unstable sort 90 90 00:03:52,370 --> 00:03:53,830 and you don't want to turn 91 91 00:03:53,830 --> 00:03:56,190 a stable sort into an unstable sort 92 92 00:03:56,190 --> 00:03:57,750 and it's really easy to do. 93 93 00:03:57,750 --> 00:04:00,560 And I have seen cases around the internet 94 94 00:04:00,560 --> 00:04:02,580 in blog posts and things like that 95 95 00:04:02,580 --> 00:04:07,580 where a stable sort algorithm has been coded to be unstable. 96 96 00:04:07,980 --> 00:04:11,650 That pesky little equals can make a big difference. 97 97 00:04:11,650 --> 00:04:12,770 So be aware of this. 98 98 00:04:12,770 --> 00:04:15,220 Be aware of this when you're reading code on the internet 99 99 00:04:15,220 --> 00:04:17,730 and be aware of this when you're writing your own code. 100 100 00:04:17,730 --> 00:04:21,090 Make sure that if a sort algorithm is stable 101 101 00:04:21,090 --> 00:04:24,890 that your implementation isn't inadvertently changing it 102 102 00:04:24,890 --> 00:04:26,750 to an unstable algorithm. 103 103 00:04:26,750 --> 00:04:30,070 So in a nutshell, a stable sort algorithm preserves 104 104 00:04:30,070 --> 00:04:32,240 the relative ordering of duplicate items 105 105 00:04:32,240 --> 00:04:35,530 and an unstable sort algorithm does not. 106 106 00:04:35,530 --> 00:04:39,060 And on that note, let's move on to the next sort algorithm. 107 107 00:04:39,060 --> 00:04:40,610 I'll see you in the next video. 9261