Original subtitles

1 1

So we're going to kick off 2

2

our look at sort algorithms by starting with bubble sort. 3

3

I want to say right up front that this 4

4

algorithm's performance degrades quickly 5

5

as the number of items you need to sort grows, 6

6

but it's a commonly taught algorithm 7

7

and you might hear about it so will take a look at it 8

8

and it will get us warmed up for the rest of this section. 9

9

So I'm going to start out by explaining 10

10

how the algorithm works. 11

11

So I have an array on this screen, 12

12

it's an array of length seven 13

13

so we can store seven integers. 14

14

At index 0 we have 20, at index 1 35, at index 2 -15. 15

15

You can see the rest of the array there 16

16

and we want to use bubble sort to sort this array. 17

17

Now the way that bubble sort works 18

18

and you're going to see that this is 19

19

pretty common with sort algorithms is 20

20

as the algorithm progresses, 21

21

it partitions the array into a sorted partition 22

22

and an unsorted partition 23

23

and this is a logical partitioning so 24

24

we don't create completely separate array instances 25

25

and we an array instance that contains 26

26

what we've sorted so far and another 27

27

array instance that contains unsorted numbers. 28

28

No, everything is done when it comes to bubble sort 29

29

using the array that we're sorting 30

30

and we partition the array logically 31

31

and you're going to see this when 32

32

we go through the algorithm in just a minute. 33

33

So when we start the algorithm for this array, 34

34

we're going to have a field that 35

35

we're going to call unsorted partition index 36

36

and when we start this will be 6 37

37

because the entire array is the 38

38

unsorted partition when we start out 39

39

because we haven't sorted anything yet. 40

40

So 6, it will be the last index of the unsorted partition. 41

41

Alright, so the implementation that I'm going to show you 42

42

starts at the left of the array, or at index 0, 43

43

so that's what I is and what we do 44

44

is we compare the elemented index 0 45

45

with the elemented index 1 46

46

and if the elemented index 0 is greater 47

47

than the elemented index 1, we swap the elements. 48

48

If it's less we don't do anything 49

49

because of course we want to move larger elements 50

50

towards the end of the array or towards the right 51

51

because we're sorting in ascending order. 52

52

So in this case 20 is less than 35 53

53

so we don't do any swapping 54

54

and then what we're going to do is increment I to 1. 55

55

So now we're going to look at 56

56

the element at position 1 57

57

and compare it with the element at position 2 58

58

and in this case 35 is greater than -15, 59

59

so we swap them. 60

60

So now -15 will be at position 1 61

61

and 35 will be at position 2 62

62

and we increment I to 2. 63

63

So now we're going to compare the 64

64

element at index 2 with the elemented index 3. 65

65

35 is greater than 7 so we swap them 66

66

and we increment I to 3. 67

67

So now we're going to compare the elemented index 3 68

68

with the elemented index 4. 69

69

35 is less than 55 so we don't do anything 70

70

we just increment I to 4 71

71

and then we compare 55 to 1, 72

72

that's the elemented position 4 73

73

with the elemented position 5. 74

74

55 is greater than 1 so we swap them 75

75

and we increment I to 5 76

76

and finally we compare 55 to -22 77

77

and of course 55 is greater than -22 so we swap them 78

78

and at this point I is equal to 79

79

the last unsorted partition index so we stop. 80

80

We have completed the first traversal of the array 81

81

and at the end of that traversal, 82

82

the last element in the array is in its correct position 83

83

and so at this point the greatest element in the array 84

84

will be at index array length minus one 85

85

and for our array length minus one is 6. 86

86

So at this point what we're going to do is 87

87

we're going to set the unsorted partition index to 5 88

88

because we now consider position 6 to be sorted 89

89

and so the logical partition is going to be between 90

90

the elemented index 5 and the elemented index 6. 91

91

Everything from index 5 down to the front 92

92

of the array is in the unsorted partition 93

93

and everything at array index 6 and to the right, 94

94

and in this case there isn't anything to the right, 95

95

everything there is in the sorted partition. 96

96

So on the next traversal, 97

97

we can see that 55 is now in the sorted partition 98

98

and we set I back to zero 99

99

because we want to repeat the process we just did 100

100

and the unsorted partition index is now 5. 101

101

So we start all over again we go OK 102

102

the element at array index 0 103

103

is it greater than the element array index 1 104

104

and it is and so we swap them 105

105

and we increment I to 1 106

106

and then we say 107

107

is the array element at index 1 108

108

greater than the array element at index 2? 109

109

Yes it is so we swap them and we increment I to 2. 110

110

We say is the element at index 2 111

111

greater than the elemented index 3? 112

112

No it isn't so we just increment I to 3. 113

113

Then we compare the elemented index 3 114

114

to the elemented index 4. 115

115

35 is greater than one so we swap them, 116

116

I get incremented to 4 . 117

117

35 is greater than -22 so we swap them. 118

118

I gets incremented to 5 and now I equals 119

119

the unsorted partition index so we stop. 120

120

And at this point, 35 and 55 are in their correct positions 121

121

and we set the unsorted partition index to 4. 122

122

So now everything in array index 0 123

123

to array index 4 is in the unsorted partition 124

124

and everything from array index 5 125

125

up to the end of the array is in the sorted partition 126

126

and we've set I back to zero 127

127

because we're now going to repeat the process. 128

128

Now I'm not going to go through the other traversals, 129

129

they'll operate the exact same way. 130

130

We're gonna to keep incrementing I and 131

131

we're gonna keep comparing the elemented I 132

132

with its neighbour and swap the elements 133

133

if its neighbour is less than the elemented I 134

134

until the sorted partition is the entire array 135

135

and then we're done. 136

136

Now this is called a bubble sort because depending on 137

137

which way you're sorting, in our case the larger 138

138

values in the array will bubble up to the end of the array 139

139

and another way of looking at it is to flip 140

140

the array vertically so we take the array 141

141

and we flip it counterclockwise so that 142

142

array element zero is at the bottom and 143

143

array element 6 is at the top 144

144

and another way of looking at it 145

145

is saying that the larger values are 146

146

bubbling up to the top of the array. 147

147

Now as I said there are some variations 148

148

where the array is sorted from right to left 149

149

so the traversal goes from right to left 150

150

and sometimes the smaller elements are bubbled 151

151

to the front of the array 152

152

rather than the larger elements 153

153

being bubbled to the back of the array 154

154

but the same steps are used, 155

155

it's the same algorithm. 156

156

So that's bubble sort and so now let's take a look at 157

157

how this algorithm performs. 158

158

First of all, it's an in-place algorithm. 159

159

Now what do I mean by that? 160

160

Well as I said we're logically partitioning the array. 161

161

We don't have to create another array 162

162

in order to perform this sort 163

163

and so when it comes to memory, 164

164

this is an in-place algorithm. 165

165

Now we do, as you see when we look at the implementation, 166

166

we do create some local variables but that's OK. 167

167

It's an in-place algorithm. 168

168

If the extra memory that you need 169

169

doesn't depend on the number of items you're sorting. 170

170

So we're going to create a few local variables, for example, 171

171

to store the last sorted partition 172

172

and to store I, for example, but 173

173

that doesn't mean it's not an in-place algorithm. 174

174

If the extra memory you're using 175

175

doesn't increase as the number 176

176

of items in the array increases, 177

177

then it's still an in-place algorithm. 178

178

It's OK to use a few extra variables. 179

179

Now this algorithm has O to the n square time complexity. 180

180

It's a quadratic algorithm 181

181

so that means that it will take 100 steps to sort 10 items, 182

182

10,000 steps to sort 100 items, 183

183

1,000,000 steps to sort 1,000 items. 184

184

So as you can see this algorithm really degrades quickly. 185

185

Now how do we get O to the n squared? 186

186

Well, we'll talk about this a little more 187

187

in the next video when we take 188

188

a look at the implementation. 189

189

So I'll see you there.