Original subtitles

1 1

(upbeat music) 2

2

Okay so let's implement the quick sort algorithm 3

3

using the implementation we went through on the slides. 4

4

We're going to code two methods, one called quick sort 5

5

and one called partition. 6

6

So let's start with the quick sort method first. 7

7

So we'll say public static void, quick sort 8

8

and we're gonna pass the array we wanna sort, 9

9

the start index, and the end index. 10

10

And as we saw on the slides, the end index 11

11

will be one greater than the last valid index in the array. 12

12

So the first thing we're gonna do is check whether 13

13

end minus start is less than two. 14

14

Because if end minus start is less than two, 15

15

we're dealing with a one element array, 16

16

so we don't have to do anything, we just return. 17

17

If we're dealing with more than one element 18

18

than what we want to do is figure out where the pivot 19

19

will belong in the sorted array. 20

20

In other words, what will be the index of the pivot 21

21

when the array is sorted, what is it's sorted position 22

22

and so we're gonna say int pivot index equals 23

23

and we're gonna partition this array. 24

24

And we'll write the partition method in a minute. 25

25

So what this will return is the position 26

26

of the element in the sorted array, 27

27

so it's corrected sorted position. 28

28

So in the slides we had 20 as the pivot 29

29

and eventually the pivot ended up in position four 30

30

and so what this would return is four, 31

31

so it's basically returning the position 32

32

at the pivot and at that position everything to the left 33

33

of the pivot will be smaller than the pivot 34

34

and everything to the right will be larger. 35

35

And after that, we want to do the same thing 36

36

with the left array and the right array. 37

37

So all the elements that are smaller than the pivot 38

38

and all the elements that are larger than the pivot. 39

39

So we're gonna call quick sort, 40

40

with start as the start index and the pivot index 41

41

as the end and then we're gonna call a quick sort 42

42

with the same input away, pivot index plus one 43

43

as the start index and end as the end index. 44

44

So what we're saying here is in this step, 45

45

we have put the pivot into it's correct sorted position 46

46

and we have repositioned the elements such as everything 47

47

to the left of the pivot is smaller than the pivot 48

48

and everything to the right of the pivot is greater 49

49

than the pivot and then we wanna do the quick sort the left 50

50

sub-array and we wanna quick sort the right sub-array. 51

51

And once we've done that, the entire array will be sorted. 52

52

Now of course these are recursive calls, 53

53

so what actually happens is when we call this quick sort 54

54

it will deal with the left sub-array 55

55

but then it's going to make a recursive call 56

56

to then deal with the left array of that sub-array, 57

57

et cetera until it's completely handled, 58

58

the left sub-array and then and only then, 59

59

will we start working on the right sub-array. 60

60

So keep in mind what happens with recursion 61

61

and if you need to go back and review the video 62

62

on recursive methods. 63

63

Okay so let's write the partition method. 64

64

So we'll say public static int, this is going to return 65

65

the correct position of the pivot 66

66

in the sorted array, partition, we're gonna accept 67

67

an input array, a start index and an end index. 68

68

So I'm gonna put a note here that says this is using 69

69

the first element as the pivot, as we saw in the slides. 70

70

So we're gonna start out by saying that the pivot 71

71

is equal to input start. 72

72

Now of course this is the start element in the array 73

73

or sub-array that we're passing. 74

74

So it's not necessarily index zero. 75

75

Later on in our example, we have put 20 here 76

76

as the first pivot index and so the right sub-array 77

77

would be starting at index five and so that one 78

78

would actually be the pivot when we call 79

79

partition with this right sub-array. 80

80

And then as we did in the slides, 81

81

we're gonna set I to start and we're gonna set J to end. 82

82

And now we're going to do the traversal, 83

83

so remember that I is going to traverse from left to right 84

84

and J is going to be traversing from right to left 85

85

and we want to stop when I and J cross each other. 86

86

So we're gonna while I less than J 87

87

because if I is greater than J, it means they have crossed. 88

88

Okay, so what we're going to do in here 89

89

is we're first going to use J to look for elements 90

90

that are less than the pivot. 91

91

So we're gonna say while I is less than J 92

92

because we wanna stop if I and J cross, 93

93

so if J crosses I we wanna stop 94

94

and while input minus minus J 95

95

is greater than equal to the pivot, 96

96

that's all we wanna do. 97

97

This is any empty loop, I'm gonna put a note here 98

98

to say note empty loop body. 99

99

And so we're not doing anything within the body of the loop 100

100

so we're just basically using the loop to keep decrementing 101

101

J until we either find an element that's less 102

102

than the pivot or J crosses I. 103

103

So what do we do when we fall out of this loop then? 104

104

Well we've gotta make sure we didn't 105

105

fall out of it because J crossed I. 106

106

So if J hasn't crossed I, if I is still less than J, 107

107

then we want to move the element at J 108

108

into position I because basically we have found 109

109

the first element that is less than the pivot 110

110

and so we wanna move that towards the front of the array. 111

111

And so we're gonna say input I equals input J. 112

112

And if you're confused about this, go back and review 113

113

the last video with the slides, 114

114

but essentially we're saying we've used J 115

115

to find the first element that is less than the pivot 116

116

and we wanna put all the elements that are less 117

117

than the pivot to the left of the pivot 118

118

and so we're going to move that element at J, 119

119

the one that we found that's smaller than the pivot, 120

120

we're gonna move it to position I 121

121

and on the first iteration I is actually at zero. 122

122

So if you'll remember the slides, the first pivot value 123

123

was 20 and we're moving backwards and we found minus 22 124

124

and we moved minus 22 into position zero. 125

125

Okay so now we wanna alternate and go to I. 126

126

We wanna traverse the array from left to right, 127

127

looking for the first element that's greater than the pivot. 128

128

So we're gonna say while I is less than J, 129

129

'cause once again we wanna stop if I crosses J 130

130

and input plus plus I is less than or equal to the pivot 131

131

and once again this is an empty loop 132

132

and I'll put a note there 'cause it's easy to miss. 133

133

And so this time we're gonna be moving from left to right 134

134

and we're looking for a value that's greater than the pivot 135

135

because when we find a value that's greater than the pivot 136

136

we wanna move it to the right of the pivot. 137

137

And so once again, we're gonna check when we drop out 138

138

of the loop whether we've dropped out because I 139

139

has crossed J and if that's not the case 140

140

then we've dropped out because we found an element 141

141

that's greater than the pivot 142

142

and so we wanna move it to position J. 143

143

Input J equals input I and it's okay to do that, 144

144

we're not gonna be losing any data 145

145

because in the previous loop, we've already moved 146

146

what was at input J and so at this point, 147

147

it's safe to assign to input I and in the next iteration 148

148

of this loop it's safe to overwrite input I 149

149

because we've already moved it. 150

150

So it's the fact that we're alternating 151

151

between I and J and which direction we're traversing in 152

152

that lets us do these types of assignments 153

153

without losing any data. 154

154

Now one important thing to note here, 155

155

we're using the prefix decrement 156

156

and the prefix increment operator so what this means 157

157

is when we execute this statement, we'll decrement J 158

158

and then we'll use the result as the index 159

159

and recall that end will always be one greater 160

160

than the last index of the array 161

161

and so if we didn't decrement we'd get an index outta bounds 162

162

exception, if we pass the entire array in 163

163

or we'd actually be indexing one element past the end 164

164

of the sub-array that we wanna work with. 165

165

And it's the same thing here, when we first come in, 166

166

I is start, I is the pivot, we wanna start with the first 167

167

element after the pivot and so we're always gonna be, 168

168

we wanna increment first and then use the index. 169

169

And then on subsequent iterations, we'll want to increment 170

170

first because we've already handled what's at I. 171

171

So whenever we enter this loop, we've already handled 172

172

the element at I and so we wanna increment 173

173

and then use the index, we don't wanna use I 174

174

or we're gonna be looking at something we've already handled 175

175

and that's not gonna work. 176

176

Okay, so when we drop out of this loop, 177

177

I has crossed J and that means that we've finished moving 178

178

elements that are smaller than the pivot to the left 179

179

sub-array and elements that are larger 180

180

than the pivot to the right sub-array 181

181

and so at this point, the value of J will be the index 182

182

where we want to insert the pivot 183

183

and so that's all we have left to do 184

184

and so we'll say input J, J not I, equals the pivot 185

185

and then we have to return J because remember what we're 186

186

returning from this method is the index where we inserted 187

187

the pivot because that's how we're dividing the array 188

188

and we need that to then call quick sort for the left array 189

189

and quick sort for the right array. 190

190

And you'll notice that when we called quick sort 191

191

for the left array, we passed the pivot index 192

192

because as I said, the end index is always going to be 193

193

one greater than the last valid index in the partition 194

194

in the array, the sub-array that we wanna partition next 195

195

and so we really, for the left sub-array, 196

196

we'll go from index start to pivot index minus one. 197

197

And so we pass pivot index 'cause we wanna pass one greater 198

198

than the last index we're interested in. 199

199

And that's it, that's our quick sort algorithm. 200

200

Keep in mind that this is recursive so when we come in here 201

201

we call quick sort on the first left sub-array, 202

202

this is not gonna return until the first left sub-array, 203

203

this sub-array here, remember the first pivot element is 20 204

204

and we end up inserting it here, so the first left sub-array 205

205

that we're gonna call this with is this sub-array here. 206

206

This quick sort call is not gonna return 207

207

until this entire thing has been quick sorted 208

208

and so by the time this call returns, 209

209

all of this will be sorted and the same thing goes 210

210

for this quick sort, by the time it returns, 211

211

this whole sub-array will have been sorted. 212

212

So let's run this to make sure it actually works. 213

213

And of course I did not, doesn't work because 214

214

I haven't actually called quick sort. 215

215

So we're getting here the unsorted array. 216

216

So we're gonna call quick sort, we're gonna pass 217

217

our int array, we're gonna pass zero for start 218

218

and we're gonna pass, should be int array, 219

219

zero for start and int array dot length as the end index. 220

220

So let's give this another shot. 221

221

And now we have our sorted array. 222

222

It always helps when you actually call the sort method. 223

223

So minus 22, minus 15, one, seven, 20, 35, and 55. 224

224

So if you're having trouble understanding what's 225

225

going on here, go back to the slides 226

226

and the key point to remember is that we're alternating 227

227

between I and J, we're alternating between traversing 228

228

from right to left, looking for smaller elements 229

229

and going from left to right looking for larger elements 230

230

and because we're alternating, we can do all of this 231

231

in place without losing any data. 232

232

And if you're having trouble understanding the recursive 233

233

nature of it, go back and review the video on recursion. 234

234

So that's it for quick sort, that's the second divide 235

235

and conquer algorithm we've see, 236

236

but we're not out of sort algorithms yet. 237

237

So I'll see you in the next video.