Original subtitles

1 1

(bubbly music) 2

2

(keys typing) 3

3

In this video we're going 4

4

to implement the bubble sort algorithm 5

5

that we just went through using slides in the last video. 6

6

So I'm gonna start by creating a new project. 7

7

Now I'm gonna go through this one more time 8

8

and then from this point forward, 9

9

I'm going to assume that you understand 10

10

how to create a project so when we start a video 11

11

I'll already have the project created. 12

12

But, for one last time, we go up to file, 13

13

new, project, 14

14

and I want a Java project, 15

15

so I'll make sure Java is selected on the left-hand side, 16

16

and we don't need to check any of these boxes. 17

17

I have my project SVK set to Java nine. 18

18

I'm going to click next. 19

19

I want the IDE to create the main method for me, 20

20

the main class and the main method 21

21

so I'll select that and click next. 22

22

And I'm gonna call this project bubble sort. 23

23

And I'm going to change the package 24

24

to academy.learnprogramming.bubblesort. 25

25

And I'm gonna click finish, 26

26

and because I have a project open, 27

27

it's asking me if I wanna use the same window 28

28

and I do, so I'm gonna click this window. 29

29

And there we go, we have our new project. 30

30

Fine to move this over a little to make some more room, 31

31

I'm going to delete this comment. 32

32

And this is a rather simple algorithm 33

33

so we're just gonna do the implementation 34

34

within the main method. 35

35

Now before we do that, I'm going to write a swap method. 36

36

As you'll see, a number of the sort algorithms we'll look at 37

37

swap elements at some point, 38

38

and that's true of bubble sort. 39

39

It swaps elements, so I'm going to write a swap method. 40

40

So I'm gonna say public static, 41

41

it has to be static because we're going to be 42

42

calling it from the main method. 43

43

Void swap, and this method's going to take three parameters, 44

44

it's going to take the array that we're sorting, 45

45

and it's going to take two indices. 46

46

And these two indices are the indices 47

47

of the elements we want to swap. 48

48

So if we want it to swap elements three and four, 49

49

we pass the array in, and we pass 50

50

three for I, and four for J. 51

51

So the first thing we're gonna do in this method 52

52

is check whether I equals J. 53

53

Because if I equals J, there's nothing for us to do. 54

54

So I'll say if I, I equals J, 55

55

we'll just return. 56

56

Because essentially if I equals J 57

57

we're saying we wanna swap element two with element two 58

58

or swap element three with element three, 59

59

so there's nothing for us to do. 60

60

There's actually no element to swap. 61

61

But if I isn't equal to J, then we do 62

62

have elements to swap and so what we're going to do 63

63

is we're going to create a temporary int variable 64

64

and we're going to say array I 65

65

into that variable. 66

66

So temp will now contain the value at array I. 67

67

And then we're going to assign the value 68

68

at array J to array I. 69

69

Equals array J. 70

70

Now it's okay for us to do this. 71

71

We've overwritten the value that was at array I, 72

72

but that's fine because we've saved it in temp. 73

73

And so the final thing we have to do 74

74

is assign temp to array J. 75

75

So we'll say array J equals temp. 76

76

So we assign what's at I to temp, 77

77

we assign what's at J to I, 78

78

and then we assign what's at temp to J. 79

79

So, when we exit this method, 80

80

what used to be at position J will now be at position I, 81

81

and what used to be at position I will now be at position J. 82

82

Alright, so now that we have a swap method, 83

83

let's create our intArray. 84

84

So I'll say int, intArray equals, 85

85

and we'll use the same values we used on the slide, 86

86

20, 35, -15, 7, 87

87

55, 1, and -22. 88

88

And now we wanna use the bubble sort algorithm 89

89

to sort this array. 90

90

Now, the implementation that I'm going 91

91

to show you is one implementation. 92

92

There are other implementations of this algorithm, 93

93

there'll be a different implementation 94

94

to sort in descending order. 95

95

Some of the implementations expand 96

96

the sorted partition from left to right 97

97

rather than from right to left. 98

98

I'm going to implement what I showed you in the slides. 99

99

And so we're going to say for int, 100

100

last unsorted index 101

101

equals array.length 102

102

minus one, that should be intArray actually. 103

103

So remember that at the beginning of the algorithm, 104

104

the entire array is unsorted, and so the last unsorted 105

105

index will be the last valid index in the array, 106

106

and that's intArray.length minus one. 107

107

So that's what we're initialising that to. 108

108

And then we're going to do this as long 109

109

as the last unsorted index is greater than zero and 110

110

after each iteration we're going to 111

111

decrement the last unsorted index. 112

112

Now remember that because we're bubbling 113

113

large values to the end of the array, 114

114

the sorted partition is growing from right to left. 115

115

And so the last unsorted index starts at six 116

116

and after the first iteration it's now 117

117

going to be five because whatever's here 118

118

will be in the sorted partition. 119

119

And then after the second iteration it'll be four, 120

120

because then these two elements will be sorted. 121

121

And three, two, et cetera. 122

122

And so the index is going to go from six to zero, 123

123

and once we hit zero, we can stop. 124

124

Because at that point, the entire array is sorted. 125

125

So that's the outer loop. 126

126

For each iteration of the outer loop, 127

127

we want to traverse the array. 128

128

And we want to bubble the largest value that's unsorted 129

129

into the sorted partition. 130

130

So we want to bubble the largest value 131

131

to the end of the array. 132

132

So that's what the inner loop is going to do. 133

133

So we'll say for int, I equals zero 134

134

because we always start at the beginning of the array. 135

135

I less than the last unsorted index, 136

136

because we don't need to go into the sorted partition 137

137

because we know that those, the values 138

138

in the sorted partition are already sorted. 139

139

So in the inner loop, we start at zero 140

140

and we keep going until we hit the last unsorted index. 141

141

And we're gonna increment I, 142

142

and then what we wanna do, is you saw in the slides, 143

143

is we wanna compare the value at I 144

144

with the value at I plus one. 145

145

And if the value at I is greater than 146

146

the value at I plus one, we wanna swap the two values 147

147

because we wanna bubble the largest values 148

148

up to the end of the array. 149

149

And so we're going to say if intArray I 150

150

is greater than intArray I plus one, 151

151

well what do we want to do, we want to swap them. 152

152

And we can use our swap method to do that. 153

153

So we'll pass at the intArray, I and I plus one. 154

154

And that's it, that's our implementation 155

155

of the bubble sort algorithm, as I said 156

156

this is not the only implementation, 157

157

it is a implementation, or should that be 158

158

an implementation. 159

159

So we're sorting in ascending order, 160

160

and we're bubbling large values to the end of the arrray, 161

161

and we are growing the sorted partition from right to left. 162

162

We're starting it right at the end of the array, 163

163

and after each iteration of the outer loop, 164

164

the sorted partition grows by one. 165

165

And so it starts out being basically nothing 166

166

in the sorted partition, and then it, 167

167

after the first iteration, the element at position six 168

168

is sorted, so that's a sorted partition, 169

169

after two iterations, the elements at positions 170

170

five and six are sorted, so that's the sorted partition 171

171

et cetera until we get right down 172

172

to the beginning of the array. 173

173

So let's print out this array after we've sorted it. 174

174

So for int I equals zero, 175

175

I less than intArray.length, 176

176

I plus plus, and we'll just print out 177

177

the value in the arrays, so intArray I. 178

178

So this should work. 179

179

And when we run, these values should be sorted. 180

180

Let's give it a shot. 181

181

And sure enough, our values are sorted. 182

182

22, -15, 1, 7, 183

183

20, 35, and 55. 184

184

I'll just close the console here, and so that's bubble sort. 185

185

Now, I said in the last video that the time complexity 186

186

of bubble sort is O to the N squared, it's quadratic. 187

187

So the absolute worst case is it will take N squared 188

188

steps where N is the number of items we're sorting. 189

189

Now you might look at the code and say 190

190

well it's not N squared, it's actually less than that 191

191

because the sorted partition is growing 192

192

after each iteration of the outer loop 193

193

and the inner loop doesn't cross 194

194

into the sorted partition. 195

195

So the inner loop is actually doing less work 196

196

as the algorithm progresses, or at least 197

197

as this implementation progresses, and you'd be right. 198

198

But remember that when it comes to determining 199

199

the time complexity of an algorithm, we're not doing math. 200

200

We don't want the absolute precise expression. 201

201

What we're trying to do is get some sense 202

202

of how the number of steps grows 203

203

as the number of items we have to sort grows. 204

204

So we kind of want a general idea. 205

205

We want to be able to say this is a linear algorithm, 206

206

or this is a quadratic algorithm, 207

207

or this is a logarithmic algorithm, 208

208

or this is a constant algorithm. 209

209

It doesn't grow as the number of items 210

210

you're dealing with grows. 211

211

And so we're looking for approximations. 212

212

The algorithm grows in a quadratic way 213

213

as the number of items increases. 214

214

The pattern isn't linear, it's not logarithmic, 215

215

and it's certainly not constant. 216

216

And so we still consider bubble sort 217

217

to be an O to the N squared algorithm, 218

218

and in fact this implementation 219

219

has a little bit of an optimization. 220

220

Strictly speaking, bubble sort wants us 221

221

to traverse the entire array every single time. 222

222

It doesn't really pay attention to where 223

223

the sorted partition is. 224

224

This implementation does pay attention 225

225

to where the sorted partition is, 226

226

and it doesn't cross into the sorted partition 227

227

because it doesn't have to. 228

228

Those elements are already sorted. 229

229

One tip when it comes to determining time complexity 230

230

is to look at how many loops there are. 231

231

Because normally each loop corresponds to N, 232

232

and so if you have only one loop, 233

233

then it's linear time complexity. 234

234

If you have two loops, then it's N times N. 235

235

And so that's quadratic time complexity. 236

236

And here we have two loops, and so just at a glance 237

237

we can kind of guess that this is 238

238

O to the N squared time complexity. 239

239

Alright, so that's bubble sort, not very complex. 240

240

As I said upfront in the theory video, 241

241

this algorithm is one of the least efficient algorithms. 242

242

In fact there are some computer scientists 243

243

that think we shouldn't even teach it anymore, 244

244

but it is a classic sort algorithm that is usually taught. 245

245

And it's gotten us warmed up for some of the faster 246

246

algorithms that we'll look at later. 247

247

So I'll see you in the next video.