Original subtitles

1 1

(bright music) 2

2

(keyboard clicking) 3

3

In this video, we're going to look at Quick Sort. 4

4

And Quick Sort is another divide and conquer algorithm, 5

5

just like merge sort. 6

6

And just like merge sort, we can write it recursively, 7

7

and we often do. 8

8

So how does Quick Sort work? 9

9

Well, Quick Sort 10

10

chooses a pivot element 11

11

and then it divides the array into two halves 12

12

and this division is a logical division. 13

13

So it chooses a pivot element. 14

14

It divides the array into two halves. 15

15

On the left half, it puts elements that are less 16

16

than the pivot element. 17

17

And in the right half, for the right subarray, 18

18

it puts elements that are greater than the pivot element. 19

19

And so the pivot element will be in the middle, 20

20

between the two arrays. 21

21

Everything less than the pivot element will be to the left 22

22

and everything greater to the pivot element 23

23

will be to the right. 24

24

And this is called the partitioning step. 25

25

So think about this for a minute, 26

26

if all the elements less than the pivot 27

27

are placed at its left 28

28

and all the elements greater than the pivot 29

29

are placed to its right, 30

30

that means that after we've finished the partitioning step, 31

31

the pivot is in its correct sorted position in the array. 32

32

But, and this is important to note, 33

33

the left and right subarrays aren't necessarily sorted. 34

34

We know all the elements in the left subarray 35

35

are smaller than the pivot 36

36

and we know that all the elements in the right subarray 37

37

are larger than the pivot, 38

38

but those left and right subarrays aren't sorted. 39

39

And so once we've done this partitioning, 40

40

we then do the same thing for the left array 41

41

and the same thing for the right array. 42

42

In the left array, we're gonna choose a pivot. 43

43

We're gonna put all the items in the left array 44

44

that are smaller than the pivot to the left. 45

45

All the elements in the left subarray 46

46

that are larger than the pivot to the right. 47

47

And then we're gonna do the same thing 48

48

with the right subarray. 49

49

And then we're gonna repeat the process. 50

50

So essentially, it's divide and conquer 51

51

because at each stage, 52

52

we're sort of doing what we did with merge sort. 53

53

We're partitioning the array into two 54

54

around this pivot element. 55

55

And just as with merge sort, 56

56

we'll end up partitioning the array into a series 57

57

of one element arrays. 58

58

Now because eventually, every element will be chosen 59

59

as the pivot, 60

60

eventually every element will be 61

61

in its correct sorted position. 62

62

Now unlike merge sort, this is all done in place, 63

63

so we don't have to create any temporary arrays. 64

64

So one advantage of Quick Sort 65

65

is you don't need a lot of memory to do this sort. 66

66

If you were sorting a really large array, 67

67

you would be doing the sorting in place with Quick Sort, 68

68

but with merge sort, you'd have to create 69

69

a bunch of temporary arrays. 70

70

So let's take a look at this. 71

71

Let's go through it with our usual array. 72

72

In the implementation I'm going to show you, 73

73

we're always going to choose the first element 74

74

in the array, or the subarray, as the pivot. 75

75

So we're going to set the pivot to 20. 76

76

We're going to set the start index to zero 77

77

and the end index to seven. 78

78

And we're gonna make i equal start 79

79

and j equal end. 80

80

So we start with minus, minus j. 81

81

J was, if we go back, j is gonna equal seven, 82

82

because it equal n. 83

83

So minus, minus j is gonna equal six. 84

84

And we're gonna go from right to left, 85

85

looking for the first element 86

86

that's less than the pivot element. 87

87

Minus 22 is less than the pivot element. 88

88

The pivot element is 20, and so we assign 89

89

minus 22 to position zero. 90

90

Now don't worry that we've overwritten 20 91

91

because remember, we'll have saved 20 in a pivot field. 92

92

Now at this point, we switch to i. 93

93

And we add one to i. 94

94

Now if we go back a couple of slides, 95

95

i started at zero. 96

96

So when we add one to i, 97

97

we're going to be i equal to one. 98

98

And this time, we're going to go from left to right 99

99

and we're gonna look for the first element 100

100

that's greater than the pivot. 101

101

35 is greater than the pivot 102

102

and so we're going to assign it to position j. 103

103

And currently, j is six. 104

104

And so this is going to happen. 105

105

Now notice that we've not lost any data 106

106

because we already moved what was at position six 107

107

down to position zero. 108

108

And so by alternating between going from right to left 109

109

and left to right, 110

110

we can be sure that we won't lose any data. 111

111

We're not going to overwrite any positions 112

112

that haven't already handled. 113

113

So essentially, j moves from right to left, 114

114

looking for values that are smaller than the pivot. 115

115

And i moves from left to right, 116

116

looking for values that are larger than the pivot. 117

117

And by doing these alternate assignments, 118

118

we're never going to overwrite a position 119

119

that we haven't already handled. 120

120

So at this point, j is equal to six, 121

121

and i is equal to one. 122

122

And we're now going to check whether the values 123

123

of i and j have crossed each other. 124

124

If i is less than j, they haven't crossed each other 125

125

and so, once again, we switch back to j. 126

126

And we look for the first element 127

127

that's less than the pivot. 128

128

So we're gonna subtract one from j. 129

129

And one is less than the pivot value 130

130

which is 20. 131

131

And so we're going to assign to position i. 132

132

And remember, i is one. 133

133

So we assign it to position i. 134

134

And notice, again, that we haven't lost any data 135

135

because we've already moved 35 from position one. 136

136

So now we switch back to i 137

137

and we're going to look for the first element 138

138

that's greater than the pivot. 139

139

And this is going to take us all the way to 55 140

140

because minus 15 is less than the pivot 141

141

and seven is less than the pivot. 142

142

And so we eventually hit 55 143

143

and that's greater than the pivot. 144

144

So at this point, we're going to assign 55 145

145

to position j. 146

146

J is five, 147

147

so we assign 55 to position five. 148

148

And once again, because were doing this alternating 149

149

between i and j, between going from right to left 150

150

and left to right, we haven't lost any data 151

151

because we already moved the value of one 152

152

from position five. 153

153

So now, we check to see whether i 154

154

and j have crossed each other. 155

155

At this point, i is four and j is five. 156

156

So they have not crossed each other. 157

157

And so we switch back to j 158

158

and we look for the first element that's 159

159

less than the pivot. 160

160

Now we're gonna find that at position three, 161

161

but at this point, j has crossed i. 162

162

Because i is equal to four, 163

163

so j has kind of jumped over i 164

164

and is less than i and so we stop. 165

165

We don't do anything. 166

166

Now if you'll notice at this point, 167

167

the value of i will be the sorted position 168

168

of the pivot value. 169

169

So right now, i is four. 170

170

And so we're gonna assign 20 to four. 171

171

And notice that everything to the left of 20 172

172

is smaller than 20 173

173

and everything to the right of 20 is larger than 20. 174

174

And not only that, 20 is in its correct sorted position 175

175

in the entire array. 176

176

If we were to sort this array, 177

177

20 would end up at position four. 178

178

So we've completed our first partition 179

179

and now we're going to repeat this process 180

180

for the left partition. 181

181

So for indices zero to three, 182

182

and the right partition, indices five and six. 183

183

And we're going to do this until the entire array is sorted 184

184

because by doing it for the left and right, 185

185

and of course, once we finish those, 186

186

we're gonna partition their left and right. 187

187

And so eventually, every single element 188

188

gets to be the pivot element. 189

189

And so eventually, every single element 190

190

will end up at its correct sorted position. 191

191

So as I said, Quick Sort is an in-place algorithm. 192

192

It takes place within the array 193

193

and that's an advantage over merge sort. 194

194

Just like merge sort, it's O(nlogn) and that's to the base 2 195

195

because we're repeatedly partitioning 196

196

the array into two halves. 197

197

Now one thing about Quick Sort is, 198

198

in the worst case, it's actually a quadratic algorithm. 199

199

But in the average case, 200

200

it performs with a time complexity of O(nlogn) 201

201

and most of the time, it performs better than merge sort. 202

202

Now Quick Sort is an unstable algorithm. 203

203

And I think you can probably guess why 204

204

because when we're alternating between i and j, 205

205

we're swapping, potentially, things from the 206

206

left to things to the right 207

207

and things to the right over to the left 208

208

so we can have elements jumping over each other, 209

209

there's no guarantee that the relative positioning 210

210

of duplicate items will be preserved. 211

211

Now it's important to note that the choice of pivot 212

212

can have an effect on the time complexity, 213

213

depending on the data that's being sorted. 214

214

All right, so that's it for how Quick Sort works. 215

215

Let's move onto the implementation. 216

216

I'll see you in the next video.