Original subtitles

1 1

(bright music) 2

2

(keyboard clicking) 3

3

Okay, so let's implement shell sort. 4

4

I've created a project. 5

5

I'm using package academy.learnprogramming.shellsort. 6

6

I've added the usual intArray, 7

7

the code for printing out the array 8

8

and we don't need the swap method for this 9

9

because insertion sort doesn't use swap 10

10

and this is just, essentially, 11

11

a variation on insertion sort. 12

12

So let's go. 13

13

So the first loop we're gonna have 14

14

is the one that's going to initialise 15

15

the gap value that we're using 16

16

and then reduce it on each iteration. 17

17

So we'll say for int gap equals 18

18

intArray 19

19

.length over two. 20

20

Because remember, we're going to start 21

21

with intArray, a gap of intArray.length over two. 22

22

Which for this array, will be seven over two 23

23

which is three. 24

24

And then we're gonna keep going 25

25

as long the gap is greater is zero 26

26

because if the gap is zero, 27

27

then that means that we're gonna be comparing elements 28

28

against themselves. 29

29

So we need a gap of one. 30

30

For the final iteration, remember for shell sort, 31

31

the final iteration always has to have a gap of one 32

32

because we want the final iteration 33

33

to essentially be insertion sort. 34

34

And on each iteration, we're going to divide 35

35

the gap value by two. 36

36

And so on the first iteration, 37

37

our gap value will be seven over two 38

38

which is three. 39

39

On the second iteration, it'll be three over two 40

40

which is one. 41

41

So the second iteration will be essentially 42

42

an insertion sort. 43

43

So now we're going to code 44

44

the actual comparing and shifting. 45

45

And as you'll see, and I'll show you this afterwards, 46

46

that what we're gonna code here 47

47

is essentially insertion sort. 48

48

It's gonna look slightly different 49

49

because it's using gap. 50

50

But it's essentially insertion sort, 51

51

and we'll compare the two implemetations, 52

52

the two sets of code in a minute. 53

53

So I'm gonna say four int i equals gap. 54

54

I less than intArray.length 55

55

because we're gonna want to look 56

56

at all the elements in the array. 57

57

I plus plus. 58

58

And we're gonna start out as we did with insertion sort. 59

59

We're gonna assign 60

60

a newElement field 61

61

with intArray i. 62

62

Intarray i is the value that we're going to be looking at. 63

63

So that's essentially intArray gap. 64

64

And we're gonna use j 65

65

to do the traversing. 66

66

So we're gonna say while j is greater than equal to the gap 67

67

because if j becomes less than the gap, 68

68

that means that we've hit the front of the array. 69

69

And 70

70

intArray, j minus gap 71

71

is greater than newElement. 72

72

Well what do we wanna do? 73

73

We wanna shift the element at intArray j minus gap 74

74

up gap positions. 75

75

So we're gonna say intArray j 76

76

equals 77

77

intArray 78

78

j minus gap. 79

79

And so what we're saying here, 80

80

if we were doing the, 81

81

we're starting out with a gap of three, 82

82

so we're starting at seven, 83

83

just as we did with the slides. 84

84

And in the first iteration, we're gonna compare seven 85

85

to j minus gap, right? 86

86

Because we're going to assign seven to newElement. 87

87

J is gonna start at three. 88

88

And we're gonna say if intArray j minus gap 89

89

while our gap for the first iteration is three. 90

90

So if intArray zero which is 20, 91

91

is greater than seven which it is, 92

92

then we wanna shift seven up three positions. 93

93

So we're going to assign intArray j which is three. 94

94

So intArray three with intArray three minus three 95

95

which intArray zero. 96

96

So we're essentially gonna take what's at position zero 97

97

and assign it into position three. 98

98

And then once we've done that, 99

99

we wanna subract the gap from j 100

100

because we're saying that now we're going to want to compare 101

101

newElement with whatever comes three positions over. 102

102

Well, we've hit the front of the array at this point. 103

103

We'll loop and we'll say, 104

104

well j has to be greater than or equal to the gap 105

105

and it isn't because at this point, it's zero. 106

106

And that's because there's no elements to the right here. 107

107

So first, we wanna compare seven against 20. 108

108

If we could, we'd then compare seven against 109

109

whatever occurs three places in front of 20, 110

110

but there is nothing. 111

111

And so we're gonna drop out here. 112

112

And what do we wanna do at this point? 113

113

Just like with insertion sort, 114

114

while we're basically saying we found 115

115

the insertion point for seven when we drop out. 116

116

And so we're going to assign intArray j 117

117

with newElement. 118

118

And this should look somewhat familiar 119

119

because this is essentially 120

120

what we were doing with insertion sort. 121

121

And so, after we've done that, 122

122

we loop back around to this loop 123

123

and i would become four. 124

124

So it would become 55. 125

125

J would become four and then what would happen 126

126

is it's gonna compare 55 against 35. 127

127

And it's not gonna do anything 128

128

because 55's greater than 35. 129

129

And at that point, once again, 130

130

it's gonna wanna jump ahead three places 131

131

and there's nothing so we're gonna just loop around. 132

132

I will become five, 133

133

so it's gonna compare one against minus 15. 134

134

And because one is greater than minus 15, 135

135

it's not gonna do anything, it's gonna loop around. 136

136

And once again, it's gonna wanna compare to whatever's 137

137

three spaces over and there isn't anything, 138

138

so we're gonna loop back. 139

139

I will become six, so minus 22. 140

140

We're gonna compare minus 22 against whatever's here. 141

141

Now it's not seven anymore, it's 20 142

142

because we moved 20 here. 143

143

Minus 22 is less than 20, 144

144

so 145

145

we're gonna shift 20 here. 146

146

And then we're gonna compare minus 22 147

147

to whatever's three spaces over. 148

148

And this time, we do have something 149

149

three positions over. 150

150

We actually have seven here 151

151

because on the very first iteration, 152

152

we moved seven to the front. 153

153

Minus 22 is less than seven, 154

154

so we'll shift seven back to where it was originally was 155

155

and then at this point, it's gonna wanna compare 156

156

three spaces over and there isn't anything. 157

157

We've hit the front of the array 158

158

and so we'll assign minus 22 here. 159

159

And at that point, we'll loop around, 160

160

i will become seven and it'll fail this condition. 161

161

And so we'll drop out, loop back around to the gap loop. 162

162

Reduce the gap to one 163

163

and at this point, when we enter this code, 164

164

we're essentially doing an insertion sort. 165

165

And that's how 166

166

shell sort optimises insertion sort. 167

167

So let's run this to make sure it's working. 168

168

And we get 169

169

the usual minus 22, minus 15, 170

170

one, seven, 171

171

20, 172

172

35, 173

173

and 55. 174

174

So let's go out to a couple of slides for a minute 175

175

to compare the code for insertion sort 176

176

with the code for shell sort. 177

177

Okay, so here's the code that we wrote for insertion sort. 178

178

And we can see that here we're starting 179

179

with a the first unsorted index as one. 180

180

We assign newElement with whatever's at that value. 181

181

We have i and then of course, 182

182

we loop through all the elements 183

183

to the end of the array and if possible, 184

184

we shift elements to the right. 185

185

And if we drop out of this loop, 186

186

then we have found the insertion position for newElements. 187

187

So we assign newElement to i. 188

188

Here's shell sort. 189

189

And if you ignore this part for a minute, 190

190

you'll see that this code is pretty much the same. 191

191

The only difference is, instead of using one, 192

192

we're using whatever the gap value is. 193

193

So in the first iteration we're gonna use three. 194

194

And once again, if we go back to insertion sort, 195

195

we're gonna assign intArray 196

196

first unsorted index to newElement. 197

197

While in shell sort, we assign whatever's at i, 198

198

the gap value to newElement. 199

199

We assign i to j. 200

200

It's pretty similar to what we're doing here 201

201

except the loop is taking care of assigning i. 202

202

Here, we need a different index 203

203

because we don't wanna be changing i as we traverse 204

204

the, not the sorted partition, 205

205

but the part of the array that we're looking for 206

206

in insertion position four. 207

207

And then we say in shell sort, 208

208

while j is great or equal to gap 209

209

and intArray j minus gap is greater than newElement, 210

210

as long as that's true, we're going to shift 211

211

the elements that we're comparing against. 212

212

We're gonna shift it up the array by gap positions 213

213

and then we need to decrease the position 214

214

of the next element that we look at by the gap 215

215

because we always want to be looking at 216

216

the element that's gap positions away. 217

217

And this very similar to what we're doing here. 218

218

We're saying the same thing, 219

219

as long as we haven't hit the front. 220

220

And this is saying, as long as we haven't hit the front 221

221

and as long as the element we're looking at in the, 222

222

for shell sort 223

223

it's not really the sorted partition, 224

224

but the element we're looking at that's gap positions away, 225

225

is greater than newElement. 226

226

And back in insertion sort, 227

227

as long as the element we're looking at is greater than 228

228

newElement, we wanna do the shifting. 229

229

And here, we wanna do the shifting. 230

230

And here, because we're using a gap, 231

231

we have to calculate the next index 232

232

we wanna look at differently. 233

233

We can't just decrement it by one 234

234

as we are with insertion sort 235

235

because we're assuming a gap of one here. 236

236

And then when we drop out of this loop, 237

237

we assign newElement to intArray i. 238

238

And here, when we drop out of the loop, 239

239

we assign newElement to intArray j. 240

240

So I think if you take a look at these two sets of code, 241

241

here's insertion sort again and here's shell sort, 242

242

you can see that we're doing the same thing 243

243

inside here as we're doing with insertion sort. 244

244

It's just that we're examining elements 245

245

that are farther away, except on the final iteration. 246

246

On the final iteration, when the gap is one, 247

247

what we're doing in here is exactly the same thing 248

248

as what we're doing in here. 249

249

And so the final iteration when the gap is one, 250

250

we're essentially doing it in insertion sort. 251

251

And that's what shell sort does, 252

252

but of course, with shell sort, 253

253

in the final iteration we've already moved 254

254

several of the elements closer to their sorted positions 255

255

and so there's going to be a lot less shifting 256

256

that has to take place. 257

257

And that's how shell sort improves 258

258

on the insertion sort algorithm. 259

259

And as I mentioned, you can also use the same idea 260

260

to improve on bubble sort. 261

261

You do some preliminary work. 262

262

So instead of examining neighbours and swapping them, 263

263

you'll exam elements that are further apart 264

264

and swap them if necessary. 265

265

And so by the time you get down to the bubble sort 266

266

where you're using a gap of one, 267

267

there'll be a lot less swapping to do. 268

268

So that's shell sort. 269

269

That's what the shell sort algorithm does 270

270

for insertion sort and it can also do it for bubble sort. 271

271

I'll see you in the next video.