Original subtitles

1 1

(techno music) 2

2

Before we move on to looking at 3

3

some of the other sort algorithms, 4

4

I wanna introduce the concept 5

5

of a stable versus an unstable sort. 6

6

When it comes to sort algorithms, 7

7

there are stable sorts and there are unstable sorts. 8

8

So what does this mean? 9

9

Well, stable versus unstable comes into play 10

10

when you have duplicate values 11

11

in the data that you're sorting. 12

12

For example, I have an array on the screen here 13

13

and it contains two nines. 14

14

There is a nine at position one 15

15

and there's a nine at position three. 16

16

So the question is when we sort this array, 17

17

will the original ordering of the two nines be preserved? 18

18

In other words, in the sorted array, 19

19

will the white nine still come before the black nine 20

20

or will their positions have changed 21

21

so that the black nine comes before the white nine? 22

22

If a sort is unstable, 23

23

then that means the relative ordering of duplicate items 24

24

will not be preserved. 25

25

And so in an unstable sort, 26

26

the black nine will end up coming before the white nine. 27

27

So what will happen is the nines are sorted now, 28

28

the array is sorted, 29

29

but the two nines have flipped position. 30

30

Their relative ordering has not been preserved. 31

31

So in the original array, 32

32

the white nine came before the black nine. 33

33

And in the sorted array, 34

34

the black nine is coming before the white nine. 35

35

And so when this happens, 36

36

when the relative ordering of duplicate items 37

37

is not preserved when you sort, 38

38

it's considered to be an unstable sort. 39

39

And you'll see that some of the algorithms we look at 40

40

are unstable sort algorithms. 41

41

Now by contrast for a stable sort, 42

42

we're starting off with the same array, 43

43

but after we've sorted, 44

44

the white nine still appears before the black nine, 45

45

so the relative ordering of the duplicate items 46

46

has been preserved and in this case it's a stable sort. 47

47

Now all other things being equal, 48

48

a stable sort is preferable to an unstable sort. 49

49

Now you might look at this and say, "Well, who cares 50

50

"if the relative ordering of the nines flip position?" 51

51

And for integers, it doesn't really matter. 52

52

A nine is a nine is a nine, 53

53

but if you're sorting objects, 54

54

it could make a difference depending on how you're using it. 55

55

For example if you wanna do a sort within a sort, 56

56

so for example you may first sort based on name 57

57

and then you wanna sort based on age or something, 58

58

well if the second sort causes the positions you got 59

59

from the first sort to flip, 60

60

that's going to be a problem. 61

61

So for integers it doesn't matter 62

62

and depending on how you're using the data 63

63

it might not matter, 64

64

but in some situations it will matter 65

65

and you're not going to want a sort 66

66

to change the ordering of duplicate items. 67

67

And so as we go through and look at the sort algorithms, 68

68

we'll think about whether they're stable or unstable. 69

69

So how about bubble sort? 70

70

Is bubble sort a stable sort algorithm 71

71

or an unstable sort algorithm? 72

72

Think about this for a minute. 73

73

Think back to the code and how bubble sort works. 74

74

The answer is that bubble sort is a stable sort algorithm 75

75

and why is that? 76

76

Well, when we're comparing adjacent elements, 77

77

we only swap them if the element at I 78

78

is greater than the element at I plus one. 79

79

And so when those two nines end up next to each other 80

80

and they will eventually, 81

81

eventually the white nine will end up at position I 82

82

and the black nine will end up at position I plus one 83

83

and when we compare them, 84

84

because nine is not greater than nine, 85

85

we don't swap them so their positions remain the same, 86

86

the relative ordering. 87

87

If the algorithm said greater than equals 88

88

or implementation said greater or equals, 89

89

then we would swap them and that would be an unstable sort 90

90

and you don't want to turn 91

91

a stable sort into an unstable sort 92

92

and it's really easy to do. 93

93

And I have seen cases around the internet 94

94

in blog posts and things like that 95

95

where a stable sort algorithm has been coded to be unstable. 96

96

That pesky little equals can make a big difference. 97

97

So be aware of this. 98

98

Be aware of this when you're reading code on the internet 99

99

and be aware of this when you're writing your own code. 100

100

Make sure that if a sort algorithm is stable 101

101

that your implementation isn't inadvertently changing it 102

102

to an unstable algorithm. 103

103

So in a nutshell, a stable sort algorithm preserves 104

104

the relative ordering of duplicate items 105

105

and an unstable sort algorithm does not. 106

106

And on that note, let's move on to the next sort algorithm. 107

107

I'll see you in the next video.