Original subtitles

1 1

(techno music) 2

2

All right, so in the last video, 3

3

we learned the insertion sort algorithm 4

4

and you saw the implementation 5

5

or at least one implementation, 6

6

and I said that insertion sort is a quadratic algorithm 7

7

and it is, but if the sequence of values 8

8

that we're sorting is nearly sorted, 9

9

then insertion sort runs in almost linear time 10

10

and it does that because it doesn't have to do 11

11

as much shifting. 12

12

Think about it. 13

13

If the most of the values are already sorted, 14

14

then only a few values will actually have to be inserted 15

15

into the sorted partition 16

16

and the amount of shifting will be reduced. 17

17

Now a computer scientist named Donald Shell 18

18

realised that if we could cut down 19

19

on the amount of shifting 20

20

that insertion sort would run a lot faster 21

21

and so he came up with something 22

22

that's known as the Shell sort algorithm 23

23

and that's what we're going to look at in this video. 24

24

So how does Shell sort work? 25

25

Well, it's a variation of insertion sort 26

26

and what it does is insertion sort chooses 27

27

which element to insert using a gap value of one. 28

28

So every time insertion sort runs, 29

29

it picks off the first unsorted value 30

30

and then it compares that value to its neighbour 31

31

and it keeps shifting the neighbours to the right 32

32

until it finds the correct insertion point 33

33

for the element that it's inserting. 34

34

Shell sort starts out using a larger gap value, 35

35

so instead of comparing elements to their neighbours, 36

36

it compares elements that are farther apart 37

37

from each other in the array. 38

38

And then as the algorithm runs, 39

39

it reduces the gap that it's using. 40

40

And the goal is to reduce 41

41

the amount of shifting that's required. 42

42

So as I said, as the algorithm progresses, 43

43

the gap value is reduced. 44

44

So Shell sort traverses the array with a certain gap value 45

45

and after it's done its first traversal 46

46

with the initial gap value, 47

47

it decreases the gap and it does it again 48

48

and it does this and this is very important, 49

49

it keeps reducing the gap value until the gap value is one. 50

50

Now when the gap value is one, 51

51

we're essentially doing an insertion sort. 52

52

So the last iteration of the gap value 53

53

will actually perform an insertion sort. 54

54

But at that point, 55

55

the array will be more sorted than it was at the beginning. 56

56

And so essentially what Shell sort does 57

57

is it does some preliminary work 58

58

using gap values that are greater than one 59

59

and that preliminary work puts the elements in the array 60

60

and perhaps closer to their sorted positions 61

61

and then at the very last iteration 62

62

when the gap value becomes one, 63

63

it does an insertion sort. 64

64

But that final insertion sort will be working with values 65

65

that have had some preliminary sorting done on them. 66

66

And because of that, 67

67

there will be a lot less shifting required. 68

68

So one question is well, what do we use for the gap value? 69

69

How do we figure out what to start with 70

70

and how to reduce it? 71

71

And you're going to see 72

72

that there is a tonne of theories about this. 73

73

We're going to go out now to the Wikipedia article 74

74

about Shell sort. 75

75

So here we are at the Wikipedia article 76

76

that I've linked to in the resources 77

77

and here's a table with different initial gap values 78

78

and how to reduce the gap, 79

79

what sequence of gap values to use. 80

80

And as you can see, there's quite a number of them. 81

81

The important thing to note 82

82

is that the way that you calculate the gap 83

83

can influence the time complexity. 84

84

And so here we have a time complexity column 85

85

and depending on what gap we're using, 86

86

the time complexity is different. 87

87

We have a logarithmic time complexity here. 88

88

Here's a quadratic time complexity. 89

89

And so the gap value you choose can influence 90

90

how many steps the algorithm requires so keep that in mind. 91

91

Let's go back to the slides. 92

92

Okay, so there are a number of ways 93

93

we can calculate the gap value. 94

94

One really common sequence that's used for the gap value 95

95

and the gap is also called the interval 96

96

is the Knuth sequence. 97

97

I think that's how it's pronounced. 98

98

I've never pronounced it before or said it out loud 99

99

so I don't know if the K is silent or not, 100

100

but it's the Knuth sequence. 101

101

And this says that we calculate the gap 102

102

using three k minus one over two. 103

103

And the initial value that we want to use 104

104

is based on the length of the array. 105

105

What we want is we want to use the value of k 106

106

that's going to calculate to a value 107

107

that's as close as possible to the length of the array 108

108

without going over. 109

109

And so if we had an array of let's say 20 elements, 110

110

we would wanna start with k equal to three. 111

111

If we were to start with k equals four, 112

112

the gap would be 40 113

113

and that's greater than the length of the array 114

114

so that won't work. 115

115

And so when you want to use this sequence, 116

116

you want to start with the value of k 117

117

that's going to result in a gap value 118

118

that is as close to the array's length as possible 119

119

without going over. 120

120

Now in the implementation I'm going to show you, 121

121

we're not going to use this sequence, 122

122

but it's a common way of calculating the interval or the gap 123

123

so I thought I'd show it to you. 124

124

We're going to do something simpler than that. 125

125

So what we're going to do is we're going to base our gap 126

126

on the array's length and we're going to initialise the gap 127

127

to array.length over two. 128

128

And then on each iteration, 129

129

we're going to divide the gap value by two until we hit one. 130

130

Now our array only has seven elements in it 131

131

and so the first gap value is going to be seven over two 132

132

which is three and then the second gap value 133

133

will be three over two which is one 134

134

so we're actually only gonna have two iterations 135

135

for this array. 136

136

So on the first iteration, we'll use a gap value of three. 137

137

And then on the final iteration, 138

138

and this is always true for Shell sort, 139

139

the gap value will be one. 140

140

And at that point, we'll be doing an insertion sort. 141

141

But because we've done a previous iteration 142

142

and we've moved some of the elements around, 143

143

some of the elements will be closer 144

144

to their sorted positions. 145

145

So let's go through this. 146

146

So we're gonna start with a gap value of three 147

147

because we're gonna use array.length over two. 148

148

We're gonna initialise i to the gap and j to i. 149

149

And as we did before with insertion sort, 150

150

we're gonna save the value 151

151

that we want to work with into newElement. 152

152

And then what we do is we compare the element 153

153

at index j minus gap 154

154

so that will be three minus three is zero with newElement. 155

155

So our gap is three and we're starting with element three 156

156

so we basically wanna compare it. 157

157

Because the gap is three, 158

158

we wanna compare it to the element 159

159

that's three positions away 160

160

and so we compare seven with 20. 161

161

Seven is less than 20 162

162

and so what we're going to do 163

163

is we're going to assign 20 to where seven was. 164

164

So instead of doing what we were doing with insertion sort, 165

165

which is we're comparing to the neighbours 166

166

and shifting up one, 167

167

we're comparing using a gap of three and we shift by three 168

168

and so 20 has been shifted up three places. 169

169

And then we're going to set j to j minus gap which is zero 170

170

and we've hit the front of the array at this point 171

171

and so what we're going to do is assign newElement 172

172

to position zero. 173

173

So what we've basically done 174

174

is we're kind of doing an insertion sort 175

175

but we're using a gap of three. 176

176

So what we're gonna want to do next now is move i to four 177

177

and j becomes i which is four, 178

178

the newElement is 55 and we're gonna compare 55 to 35 179

179

because that's three elements away. 180

180

55 is greater than 35 so we don't do anything. 181

181

Everything remains as it is. 182

182

And now i will be five, j will be five, 183

183

we're going to compare one to minus 15 184

184

'cause minus 15 is three elements away. 185

185

Okay, so there's nothing to do 186

186

because one is greater than minus 15. 187

187

And so now we're gonna move to minus 22 188

188

and we're going to assign that to newElement 189

189

and we're gonna compare it to the element 190

190

that's three positions away from it 191

191

and minus 22 is less than 20 192

192

so we're going to assign 20 to position six. 193

193

Now at this point, we're gonna subtract the gap from j 194

194

and then we're going to compare minus 22 195

195

against what's at position zero 196

196

because we wanna go three elements away again. 197

197

Minus 22 is less than seven 198

198

so we're going to shift seven into position three. 199

199

And at this point, we've hit the front of the array. 200

200

There are no more elements to compare minus 22 against 201

201

and so we assign minus 22 to position zero. 202

202

And at that this point, we've hit the end of the array 203

203

and so we have finished our first iteration 204

204

with gap equal to three. 205

205

Now notice that the array is more sorted now 206

206

than it was before 207

207

and we've moved minus 22 208

208

all the way to the front of the array 209

209

and we did that with one assignment. 210

210

And so in insertion sort, pure insertion sort, 211

211

at some point we would have had to have shifted 212

212

minus 22 down or rather in the implementation I showed you 213

213

every single element would have to have been shifted up 214

214

to make room for minus 22. 215

215

But in this sort of pre-sorting phase, 216

216

when we're using a gap of three, 217

217

minus 22 is moved very quickly down 218

218

to the front of the array. 219

219

We've also moved 20 closer to its sorted position. 220

220

20 started at the front of the array 221

221

and now it's only two positions away 222

222

from where it usually ends up in the sorted array. 223

223

So you can see how doing this preliminary work 224

224

before we get to insertion sort 225

225

will cut down on how much shifting we have to do. 226

226

So at this point, we're gonna update the gap. 227

227

We're gonna divide three by two and we'll get one 228

228

and so at this point, 229

229

we will actually do an insertion sort 230

230

because the gap is going to be one 231

231

so we're gonna be comparing everything to its neighbours 232

232

and when we shift we're gonna be shifting up by one. 233

233

And so at this point, we'll do an insertion sort, 234

234

but we're doing an insertion sort on an array 235

235

that has had some preliminary work done on it 236

236

and so there's gonna be a lot less shifting 237

237

and that's what Shell sort is all about. 238

238

So Shell sort is an in-place algorithm 239

239

just like insertion sort. 240

240

We're working within the original array. 241

241

Now as you saw, 242

242

it's really difficult to nail down the time complexity 243

243

because it's going to depend on the gap. 244

244

It's gonna depend on the method that you're using 245

245

to choose the gap. 246

246

In the worse case, it can be quadratic. 247

247

We saw that when we went out to the table in Wikipedia, 248

248

but it can also perform much better than that. 249

249

It doesn't require as much shifting as insertion sort. 250

250

So as I said, it usually performs better 251

251

than insertion sort. 252

252

However, it's an unstable algorithm. 253

253

Insertion sort is stable, 254

254

but Shell sort is unstable and you can see why. 255

255

It's because in the pre-insertion sort phase 256

256

when we're comparing elements 257

257

that are far away from each other, 258

258

it's very possible that if we have a duplicate element, 259

259

the rightmost element will be shifted 260

260

in front of the leftmost element. 261

261

So the fact that we're examining elements 262

262

that are further away from each other 263

263

can lead to the relative positions of duplicate items 264

264

not being preserved. 265

265

Now one last note before we go to the implementation. 266

266

You can also improve bubble sort using Shell sort 267

267

and it would be the same type of idea. 268

268

You would use a gap interval. 269

269

Remember in bubble sort, 270

270

we're always comparing elements to their neighbours 271

271

and then we're swapping and bubbling elements up. 272

272

Well, it's the same sort of idea. 273

273

So in bubble sort, if we use a gap of one, 274

274

that means we compare it to the neighbours 275

275

and everything gets swapped up one position. 276

276

Things get bubbled up. 277

277

If we do some preliminary work 278

278

and in this case rather than just shifting elements, 279

279

we'd actually swap them, we can improve bubble sort. 280

280

So you can apply Shell sort to insertion sort 281

281

and bubble sort and improve both algorithms that way. 282

282

With insertion sort, 283

283

you're cutting down on the number of shifting. 284

284

And with bubble sort, 285

285

you'd be cutting down on the number of swaps 286

286

that you have to do. 287

287

Okay, so that's it for taking a look at 288

288

how the algorithm works. 289

289

Let's implement it. 290

290

I'll see you in the next video.