1
00:00:00,830 --> 00:00:01,860
- [Instructor] Hi.

2
00:00:01,860 --> 00:00:03,870
I think in one of the earlier videos,

3
00:00:03,870 --> 00:00:04,850
I mentioned that

4
00:00:06,330 --> 00:00:09,960
we would do a stable version of Quicksort.

5
00:00:09,960 --> 00:00:11,763
And so let's do that.

6
00:00:12,620 --> 00:00:15,900
I'm gonna create a new file

7
00:00:15,900 --> 00:00:17,927
called quicksortStable.

8
00:00:23,830 --> 00:00:24,663
Okay,

9
00:00:25,730 --> 00:00:28,870
and I'm going to include

10
00:00:31,350 --> 00:00:32,183
vector

11
00:00:35,450 --> 00:00:36,737
and IO stream.

12
00:00:42,790 --> 00:00:44,750
Okay, and let's borrow that snippet

13
00:00:44,750 --> 00:00:46,123
for printVector.

14
00:00:49,290 --> 00:00:51,053
That's just for printing a vector.

15
00:00:52,930 --> 00:00:55,170
And now we're going to need

16
00:00:56,455 --> 00:00:57,955
a function for quicksortStable

17
00:00:59,540 --> 00:01:00,373
void

18
00:01:01,567 --> 00:01:02,900
quicksortStable.

19
00:01:06,676 --> 00:01:09,926
And that's gonna take a standard vector

20
00:01:11,700 --> 00:01:13,023
of comparables,

21
00:01:16,460 --> 00:01:18,403
and we'll call that V.

22
00:01:20,110 --> 00:01:22,810
And we should also borrow
this template and code here,

23
00:01:23,720 --> 00:01:24,900
just so you know,

24
00:01:24,900 --> 00:01:27,970
SeaLion collapses that,

25
00:01:27,970 --> 00:01:29,320
and if you click on it,

26
00:01:29,320 --> 00:01:31,973
it'll expand to show the
full template and code.

27
00:01:33,270 --> 00:01:34,103
All right.

28
00:01:34,103 --> 00:01:36,303
So, also we need main.

29
00:01:44,680 --> 00:01:46,290
Okay.

30
00:01:46,290 --> 00:01:48,680
So let's do a stable version of Quicksort.

31
00:01:48,680 --> 00:01:51,800
And as I mentioned,

32
00:01:51,800 --> 00:01:54,950
in order to make Quicksort stable,

33
00:01:54,950 --> 00:01:56,140
it comes at a price.

34
00:01:56,140 --> 00:01:57,150
What is the price?

35
00:01:57,150 --> 00:01:59,210
The price is space.

36
00:01:59,210 --> 00:02:02,190
So we're gonna need to use more space

37
00:02:02,190 --> 00:02:03,990
for this version of Quicksort

38
00:02:03,990 --> 00:02:05,540
than we do with the other version

39
00:02:05,540 --> 00:02:07,603
of Quicksort that I've
already demonstrated.

40
00:02:10,110 --> 00:02:12,440
Now this is going to work very similarly

41
00:02:12,440 --> 00:02:14,790
to the Quicksort we've seen before

42
00:02:14,790 --> 00:02:16,910
but we're going to have
to make some changes,

43
00:02:16,910 --> 00:02:18,650
and you'll see what we're going to do

44
00:02:18,650 --> 00:02:20,940
is we're going to use vectors

45
00:02:20,940 --> 00:02:24,060
to hold our intermediate results,

46
00:02:24,060 --> 00:02:27,040
and that's where the extra
space is gonna come from.

47
00:02:27,040 --> 00:02:30,963
So we'll have a base
case for the recursion.

48
00:02:35,950 --> 00:02:39,350
Okay, and that's going to be if

49
00:02:39,350 --> 00:02:41,260
the vector size

50
00:02:42,873 --> 00:02:44,513
is less than two.

51
00:02:46,590 --> 00:02:48,610
Then we have a single element,

52
00:02:48,610 --> 00:02:49,563
and we just return.

53
00:02:51,240 --> 00:02:53,563
Okay, so there's our base case.

54
00:02:55,140 --> 00:02:56,730
Now we're going to set up our pivot

55
00:02:56,730 --> 00:02:58,510
or what's called the divider

56
00:02:58,510 --> 00:02:59,880
in the book,

57
00:02:59,880 --> 00:03:02,033
comparable pivot.

58
00:03:04,330 --> 00:03:07,990
And in this case, let's pick
from the left-hand side.

59
00:03:07,990 --> 00:03:09,783
So we'll take v sub zero,

60
00:03:11,470 --> 00:03:14,660
and now we're going to need some vectors

61
00:03:14,660 --> 00:03:18,550
to hold our intermediate results.

62
00:03:18,550 --> 00:03:19,650
So standard

63
00:03:21,820 --> 00:03:22,653
vector

64
00:03:24,020 --> 00:03:25,263
of comparables,

65
00:03:27,080 --> 00:03:29,190
and we'll call them smaller,

66
00:03:29,190 --> 00:03:31,540
for the values that are
smaller than the pivot,

67
00:03:32,760 --> 00:03:33,593
equal

68
00:03:34,840 --> 00:03:35,673
and larger.

69
00:03:37,430 --> 00:03:38,860
Okay.

70
00:03:38,860 --> 00:03:41,730
So that's where our
additional space requirement

71
00:03:41,730 --> 00:03:43,410
is gonna come from.

72
00:03:43,410 --> 00:03:46,250
I'm gonna declare an integer i,

73
00:03:46,250 --> 00:03:47,483
that we're going to use,

74
00:03:48,460 --> 00:03:50,630
and it's okay to declare this here.

75
00:03:50,630 --> 00:03:53,400
And then we have a loop for

76
00:03:54,450 --> 00:03:56,973
i equals zero,

77
00:03:58,130 --> 00:04:02,443
i less than the size of the input vector,

78
00:04:05,588 --> 00:04:06,755
++i,

79
00:04:08,810 --> 00:04:12,850
and here's the core of this thing.

80
00:04:12,850 --> 00:04:14,440
If

81
00:04:14,440 --> 00:04:15,740
v sub i

82
00:04:16,890 --> 00:04:18,993
is less than the pivot,

83
00:04:21,400 --> 00:04:24,587
then we push that onto the
vector called "smaller."

84
00:04:34,280 --> 00:04:35,430
Else,

85
00:04:35,430 --> 00:04:36,263
if

86
00:04:37,330 --> 00:04:38,163
v sub i

87
00:04:40,220 --> 00:04:41,800
is greater

88
00:04:41,800 --> 00:04:43,313
than the value of the pivot,

89
00:04:44,800 --> 00:04:46,220
then it's going to go,

90
00:04:46,220 --> 00:04:47,700
I think you know what I'm gonna do here.

91
00:04:47,700 --> 00:04:48,603
Larger.

92
00:04:50,090 --> 00:04:50,923
Push back

93
00:04:52,330 --> 00:04:53,690
v sub i.

94
00:04:53,690 --> 00:04:57,670
So we're putting that
onto the larger vector,

95
00:04:57,670 --> 00:05:01,493
else, and you know what comes here, equal.

96
00:05:02,890 --> 00:05:04,730
That's our equal vector pushback

97
00:05:08,010 --> 00:05:08,843
v sub i.

98
00:05:10,570 --> 00:05:11,640
So you see what we've done.

99
00:05:11,640 --> 00:05:14,990
We're just going to take our elements

100
00:05:14,990 --> 00:05:16,470
from our vector in turn,

101
00:05:16,470 --> 00:05:19,570
and push them into the smaller vector

102
00:05:19,570 --> 00:05:22,260
if there are less than the pivot,

103
00:05:22,260 --> 00:05:23,390
the larger vector,

104
00:05:23,390 --> 00:05:24,700
if they're greater than the pivot

105
00:05:24,700 --> 00:05:25,990
or the equal vector

106
00:05:25,990 --> 00:05:27,490
if they're equal to the pivot.

107
00:05:28,450 --> 00:05:29,450
Okay,

108
00:05:29,450 --> 00:05:31,970
and now what do we need to do?

109
00:05:31,970 --> 00:05:35,420
We need to call Quicksort recursively.

110
00:05:35,420 --> 00:05:37,580
Okay, so we have these vectors.

111
00:05:37,580 --> 00:05:39,330
We wanna work with a smaller vector,

112
00:05:39,330 --> 00:05:42,250
and we want to work
with the larger vector,

113
00:05:42,250 --> 00:05:44,150
because what's in the smaller vector

114
00:05:44,150 --> 00:05:45,690
still needs to be sorted,

115
00:05:45,690 --> 00:05:47,290
and what's in the larger vector

116
00:05:47,290 --> 00:05:48,690
still needs to be sorted,

117
00:05:48,690 --> 00:05:51,580
or I should say the vector named "larger."

118
00:05:51,580 --> 00:05:53,110
All right, so we're just gonna call

119
00:05:53,110 --> 00:05:56,870
recursively quicksortStable, smaller,

120
00:05:56,870 --> 00:05:58,920
I'm to pass that smaller vector

121
00:05:58,920 --> 00:06:00,353
to quicksortStable,

122
00:06:00,353 --> 00:06:02,020
and quicksortStable,

123
00:06:03,020 --> 00:06:05,327
we're gonna pass that
vector called "larger."

124
00:06:08,820 --> 00:06:10,500
And now when we're done,

125
00:06:10,500 --> 00:06:12,113
when those recursive calls return,

126
00:06:12,113 --> 00:06:15,120
then we're ready to copy everything back

127
00:06:15,120 --> 00:06:16,700
to the original vector.

128
00:06:16,700 --> 00:06:18,750
So for,

129
00:06:18,750 --> 00:06:20,883
i equals zero,

130
00:06:21,780 --> 00:06:25,470
i less than smaller size,

131
00:06:28,090 --> 00:06:28,923
sorry.

132
00:06:32,475 --> 00:06:33,308
Okay,

133
00:06:35,235 --> 00:06:36,402
++i,

134
00:06:38,320 --> 00:06:40,980
then we're going to copy values

135
00:06:40,980 --> 00:06:44,470
from the vector named "smaller" into v.

136
00:06:44,470 --> 00:06:47,960
So v i is our index,

137
00:06:47,960 --> 00:06:49,050
smaller i.

138
00:06:53,430 --> 00:06:56,960
And now we need to

139
00:06:56,960 --> 00:06:58,113
work with,

140
00:07:00,003 --> 00:07:01,780
I'm going to show you another trick here.

141
00:07:01,780 --> 00:07:03,330
This is for...

142
00:07:04,860 --> 00:07:06,630
Semicolon

143
00:07:06,630 --> 00:07:08,010
i,

144
00:07:08,010 --> 00:07:12,393
less than smaller size,

145
00:07:15,240 --> 00:07:17,193
plus equal size,

146
00:07:22,198 --> 00:07:23,365
++i.

147
00:07:24,310 --> 00:07:25,910
Now, what have I just done here?

148
00:07:26,970 --> 00:07:31,440
You notice I've omitted
the initialization of i,

149
00:07:31,440 --> 00:07:33,910
and I can do that, that's fine.

150
00:07:33,910 --> 00:07:37,420
This is perfectly legitimate C++.

151
00:07:37,420 --> 00:07:38,640
But what it's doing,

152
00:07:38,640 --> 00:07:43,210
and this is why I declared i up here,

153
00:07:43,210 --> 00:07:44,740
for i equals zero,

154
00:07:44,740 --> 00:07:46,440
We're gonna increment i

155
00:07:46,440 --> 00:07:49,130
up to the size of this smaller index,

156
00:07:49,130 --> 00:07:50,670
and then we're just gonna continue.

157
00:07:50,670 --> 00:07:51,960
So the value of i

158
00:07:51,960 --> 00:07:53,000
is going to roll over

159
00:07:53,000 --> 00:07:55,250
into this loop,

160
00:07:55,250 --> 00:07:58,150
and we're going to continue incrementing

161
00:07:58,150 --> 00:08:00,220
through this value here,

162
00:08:00,220 --> 00:08:03,290
the smaller size plus the equal size.

163
00:08:03,290 --> 00:08:04,940
And then let me just show you

164
00:08:04,940 --> 00:08:06,350
so this will make a little more sense

165
00:08:06,350 --> 00:08:10,070
before I complete the
bodies of those four loops.

166
00:08:10,070 --> 00:08:12,630
For, we're going to do it again,

167
00:08:12,630 --> 00:08:14,430
semicolon,

168
00:08:14,430 --> 00:08:15,263
i,

169
00:08:16,220 --> 00:08:19,060
less than v size,

170
00:08:19,060 --> 00:08:21,350
that's the size of the whole vector.

171
00:08:21,350 --> 00:08:24,000
I could say smaller
plus equal plus larger,

172
00:08:24,000 --> 00:08:26,518
but it's all going to be the same thing,

173
00:08:26,518 --> 00:08:27,685
++i.

174
00:08:29,430 --> 00:08:30,370
And so what we're doing

175
00:08:30,370 --> 00:08:33,310
is we're incrementing
i up until this point,

176
00:08:33,310 --> 00:08:35,410
then we're going to
continue to increment i

177
00:08:35,410 --> 00:08:39,610
as we fill in using values
from the equal vector,

178
00:08:39,610 --> 00:08:43,300
and then we're going to continue using,

179
00:08:43,300 --> 00:08:45,590
filling in the vector v

180
00:08:45,590 --> 00:08:48,240
using values from that larger vector.

181
00:08:48,240 --> 00:08:51,750
And so let's flesh out those bodies here,

182
00:08:51,750 --> 00:08:52,880
v sub i

183
00:08:55,320 --> 00:08:57,250
gets the value of equal

184
00:08:59,210 --> 00:09:00,670
i,

185
00:09:00,670 --> 00:09:02,403
minus the smaller size,

186
00:09:05,690 --> 00:09:06,580
'cause of course,

187
00:09:06,580 --> 00:09:10,970
each vector is to start at zero index.

188
00:09:10,970 --> 00:09:13,853
And then finally, v sub i here,

189
00:09:15,390 --> 00:09:19,307
gets from the vector called "larger,"

190
00:09:21,490 --> 00:09:23,713
but here the index is i,

191
00:09:24,570 --> 00:09:26,400
sorry, i

192
00:09:26,400 --> 00:09:29,113
minus smaller size,

193
00:09:30,600 --> 00:09:34,163
minus equal size,

194
00:09:36,190 --> 00:09:38,000
again because

195
00:09:38,000 --> 00:09:43,000
the larger vector is going
to start at index zero.

196
00:09:43,470 --> 00:09:44,660
And that's it.

197
00:09:44,660 --> 00:09:48,500
That is our stable Quicksort algorithm.

198
00:09:48,500 --> 00:09:50,610
So that's the base case
for the conversion.

199
00:09:50,610 --> 00:09:52,560
I should put this up here.

200
00:09:52,560 --> 00:09:54,163
This is the recursive case.

201
00:09:57,380 --> 00:09:59,000
Okay. And that's it.

202
00:09:59,000 --> 00:10:01,220
So let's test it.

203
00:10:01,220 --> 00:10:02,980
We need to flesh out main here now.

204
00:10:02,980 --> 00:10:04,913
So we need a vector to test,

205
00:10:09,290 --> 00:10:10,440
and we'll make it a vector of int,

206
00:10:10,440 --> 00:10:12,653
as we've been doing so far to test,

207
00:10:13,530 --> 00:10:14,610
and we'll plug in

208
00:10:14,610 --> 00:10:15,443
8,

209
00:10:15,443 --> 00:10:16,430
5,

210
00:10:16,430 --> 00:10:17,330
0,

211
00:10:17,330 --> 00:10:18,430
4,

212
00:10:18,430 --> 00:10:20,290
3,

213
00:10:20,290 --> 00:10:21,123
9,

214
00:10:21,123 --> 00:10:22,210
1,

215
00:10:22,210 --> 00:10:23,150
7,

216
00:10:23,150 --> 00:10:23,983
2,

217
00:10:23,983 --> 00:10:25,030
6,

218
00:10:25,030 --> 00:10:30,030
and that's all of our
digits, zero through nine.

219
00:10:30,090 --> 00:10:33,053
And then we're going to print vector v,

220
00:10:35,230 --> 00:10:38,623
and then we're going to quicksortStable v,

221
00:10:42,970 --> 00:10:45,713
and then print vector v.

222
00:10:49,310 --> 00:10:51,510
So now if we run this,

223
00:10:51,510 --> 00:10:54,680
we will print out this unsorted vector

224
00:10:54,680 --> 00:10:56,510
we'll run quicksortStable,

225
00:10:56,510 --> 00:10:59,320
it'll make all the
necessary recursive calls

226
00:10:59,320 --> 00:11:00,580
as it divvies things up

227
00:11:00,580 --> 00:11:04,563
into those three intermediate vectors.

228
00:11:05,580 --> 00:11:07,830
And then we'll wind up
with a sorted vector,

229
00:11:07,830 --> 00:11:08,960
and we'll print that out.

230
00:11:08,960 --> 00:11:10,363
So let's do that.

231
00:11:11,870 --> 00:11:13,640
Let me make sure this is okay,

232
00:11:13,640 --> 00:11:15,590
we'll call this Quicksort, that's good.

233
00:11:17,180 --> 00:11:18,823
So let's run.

234
00:11:21,820 --> 00:11:23,423
Hopefully there are no typos,

235
00:11:24,440 --> 00:11:25,660
and that's it.

236
00:11:25,660 --> 00:11:27,520
So you see what we've done here.

237
00:11:27,520 --> 00:11:30,110
Here's our input vector,

238
00:11:30,110 --> 00:11:32,270
here's our sorted output vector,

239
00:11:32,270 --> 00:11:33,910
but by putting everything

240
00:11:33,910 --> 00:11:37,430
into these separate vectors with pushback,

241
00:11:37,430 --> 00:11:40,240
we preserve the order
in which they arrived,

242
00:11:40,240 --> 00:11:42,620
and so it's going to preserve the order

243
00:11:43,530 --> 00:11:46,120
as we copy them back out to v

244
00:11:46,120 --> 00:11:48,050
in this portion of the code.

245
00:11:48,050 --> 00:11:51,053
And so this algorithm is gonna be stable,

246
00:11:51,900 --> 00:11:53,410
which is what we wanted.

247
00:11:53,410 --> 00:11:55,180
So that's an implementation

248
00:11:55,180 --> 00:11:58,020
of Quicksort in a stable version.

249
00:11:58,020 --> 00:11:58,853
That's all.