1
00:00:00,420 --> 00:00:01,530
Welcome back.

2
00:00:01,530 --> 00:00:07,860
In this video let's look at the space complexity of the quicksort and let's see how to optimize it.

3
00:00:08,220 --> 00:00:08,670
All right.

4
00:00:08,700 --> 00:00:13,710
Now the quicksort is an algorithm that works in place right.

5
00:00:13,710 --> 00:00:19,650
And with in place we mean that we are not creating any new array or we are not using any new space in

6
00:00:19,680 --> 00:00:20,430
that respect.

7
00:00:20,430 --> 00:00:20,850
Right.

8
00:00:20,850 --> 00:00:26,490
But we cannot say that the space complexity of the quicksort is O of one or constant space.

9
00:00:26,490 --> 00:00:27,540
Why is that so?

10
00:00:27,540 --> 00:00:33,840
Because the quicksort is a recursive algorithm and we will use space on the call stack.

11
00:00:33,840 --> 00:00:34,230
Right.

12
00:00:34,230 --> 00:00:38,760
So let's take a look at the space utilization on the call stack.

13
00:00:38,760 --> 00:00:43,650
Now what is the maximum size of the call stack that we would be using.

14
00:00:43,650 --> 00:00:47,580
This would happen when the depth of the tree is the maximum.

15
00:00:47,580 --> 00:00:47,910
Right.

16
00:00:47,910 --> 00:00:50,640
When the depth of the recursive calls is the maximum.

17
00:00:50,640 --> 00:00:56,850
And this will happen in the worst case, which we discussed right when we are having n calls, we we

18
00:00:56,850 --> 00:00:59,460
saw the case where we had a sorted array, right?

19
00:00:59,460 --> 00:01:05,610
We saw the case where one, two, three, four, five was passed and then we fixed the pivot over here.

20
00:01:05,610 --> 00:01:07,290
Then we called it over here right.

21
00:01:07,290 --> 00:01:10,410
Similarly again this was fixed.

22
00:01:10,410 --> 00:01:12,060
We called it for this part of the array.

23
00:01:12,060 --> 00:01:13,380
And we kept on doing that.

24
00:01:13,380 --> 00:01:13,560
Right.

25
00:01:13,560 --> 00:01:15,480
So we saw the worst case.

26
00:01:15,480 --> 00:01:18,240
In this case the depth will be n.

27
00:01:18,240 --> 00:01:24,270
And therefore the space complexity of the quicksort in the worst case would be o of n.

28
00:01:24,960 --> 00:01:28,470
Because there would be n calls in the call stack.

29
00:01:28,470 --> 00:01:28,860
All right.

30
00:01:28,890 --> 00:01:34,080
Now this case happens when the array was already sorted or we always picked.

31
00:01:34,080 --> 00:01:35,940
We can say in in another words.

32
00:01:35,940 --> 00:01:40,800
In other words we always picked the minimum or the maximum element as the pivot.

33
00:01:40,830 --> 00:01:41,490
All right.

34
00:01:41,490 --> 00:01:46,020
Now what is the best case scenario of the, um call stack?

35
00:01:46,020 --> 00:01:49,110
The height, the best case scenario of the height of the stack.

36
00:01:49,110 --> 00:01:51,390
When would the height of the stack be minimum?

37
00:01:51,390 --> 00:01:53,040
Let's take a look at that now.

38
00:01:53,040 --> 00:01:59,250
Now this would happen when the the tree the tree is evenly created.

39
00:01:59,250 --> 00:01:59,610
Right.

40
00:01:59,610 --> 00:02:02,130
So we have a depth of log n.

41
00:02:02,130 --> 00:02:03,060
So we saw that.

42
00:02:03,060 --> 00:02:07,680
And that happened in the case when we picked the pivot always as the middle value.

43
00:02:07,680 --> 00:02:10,170
So we have seen both the cases already right.

44
00:02:10,170 --> 00:02:16,920
So in the in the case where we always pick the middle value of the array as the pivot, we had log n

45
00:02:16,920 --> 00:02:17,790
levels, right.

46
00:02:17,790 --> 00:02:25,020
And in this case the space utilization on the call stack will be of order O of log n.

47
00:02:25,020 --> 00:02:25,620
Right.

48
00:02:26,100 --> 00:02:28,740
So we have seen the best case and the worst case.

49
00:02:28,740 --> 00:02:30,270
Now the what was the worst case.

50
00:02:30,270 --> 00:02:31,560
Again let's quickly write it.

51
00:02:31,560 --> 00:02:35,490
If we have the array 12345 we call it for 1 to 5.

52
00:02:35,490 --> 00:02:36,510
So this will call it.

53
00:02:36,510 --> 00:02:40,260
This will fix the position of one and it will call it for 2 to 5 right.

54
00:02:40,260 --> 00:02:42,870
Similarly that will call it for 3 to 5 etc..

55
00:02:42,870 --> 00:02:43,260
Right.

56
00:02:43,260 --> 00:02:44,850
So we fix one.

57
00:02:44,850 --> 00:02:46,080
We call it for 2 to 5.

58
00:02:46,080 --> 00:02:47,910
That's this one over here we fix two.

59
00:02:47,940 --> 00:02:50,730
We call the quicksort for 3 to 5 etc..

60
00:02:50,730 --> 00:02:55,620
And then once we reach an array of size only one we start returning.

61
00:02:55,620 --> 00:03:01,110
So over here we can see that the the depth is n right.

62
00:03:01,110 --> 00:03:03,030
If there are n elements the depth is n.

63
00:03:03,030 --> 00:03:09,720
That's why we say that the maximum size of the stack is O of n, and the minimum size is O of log n.

64
00:03:09,720 --> 00:03:12,900
We have seen the best case where we had the tree right.

65
00:03:12,900 --> 00:03:19,230
We had n elements that was divided into n by two and n by two, and this was divided into n by four

66
00:03:19,230 --> 00:03:20,310
and n by four.

67
00:03:20,310 --> 00:03:22,080
And this kept on going right.

68
00:03:22,080 --> 00:03:24,270
This kept on happening till we reach one.

69
00:03:24,270 --> 00:03:25,500
The size of the array is one.

70
00:03:25,500 --> 00:03:28,230
So this over here will have log n levels.

71
00:03:28,230 --> 00:03:33,600
And that's why we say that the best case space complexity of the quicksort is O of log n.

72
00:03:34,140 --> 00:03:42,720
So we can say that the space complexity of the quicksort ranges from O of log n to O of n.

73
00:03:43,480 --> 00:03:46,960
Now we can make some tweaks to the algorithm.

74
00:03:46,960 --> 00:03:48,790
And this was first proposed.

75
00:03:48,880 --> 00:03:54,790
This was actually, uh, discovered or invented by a computer scientist called Cedric.

76
00:03:55,660 --> 00:04:02,650
Okay, so what he said is that there is a way to limit the auxiliary space, which we are using on the

77
00:04:02,650 --> 00:04:05,410
call stack to always to O of log n.

78
00:04:05,410 --> 00:04:06,280
So let's see that.

79
00:04:06,280 --> 00:04:07,900
Now let me make some space over here.

80
00:04:08,720 --> 00:04:14,930
Now in the way that we have discussed so far, the space complexity of the quicksort will be O of log

81
00:04:14,930 --> 00:04:15,980
n to O of n.

82
00:04:15,980 --> 00:04:19,430
Best case is O of log n, and the worst case is O of n.

83
00:04:19,430 --> 00:04:26,420
Now there is a way to limit the auxiliary space or the space on the call stack to O of log n always.

84
00:04:26,420 --> 00:04:32,210
So let's discuss how to do that, and let's make that tweak in the way we will do the quicksort.

85
00:04:32,210 --> 00:04:35,390
So we will implement all of this when we code the quicksort.

86
00:04:35,420 --> 00:04:40,730
Now to achieve always the auxiliary space of O of log n.

87
00:04:40,730 --> 00:04:47,690
To achieve this space complexity, what we need to do is we need to make the recursive call of the quicksort

88
00:04:47,690 --> 00:04:50,540
only on the lower sized subarray.

89
00:04:50,630 --> 00:04:52,730
Now how did we do it so far?

90
00:04:52,760 --> 00:04:53,600
We.

91
00:04:53,600 --> 00:04:56,480
Let's take a look at the earlier discussed implementation.

92
00:04:56,480 --> 00:04:58,100
We find the pivot right.

93
00:04:58,100 --> 00:05:03,200
And then we recursively call the quicksort on the left side and the right side.

94
00:05:03,320 --> 00:05:04,970
This is how we discussed it previously.

95
00:05:04,970 --> 00:05:08,390
Right now when we go to the coding section we will do it in both ways.

96
00:05:08,480 --> 00:05:17,360
Now when we input an array of size 41234 and it will be sorted if we implemented in the previous method.

97
00:05:17,360 --> 00:05:18,650
Right, which we did over here.

98
00:05:18,650 --> 00:05:22,370
In this way you can see that in the call stack there will be four.

99
00:05:22,880 --> 00:05:25,070
The maximum call stack will be four.

100
00:05:25,100 --> 00:05:27,830
There would be four calls on the function quicksort.

101
00:05:27,830 --> 00:05:34,010
We will see that when we do the coding together, and when we change the implementation to what Sedgewick

102
00:05:34,010 --> 00:05:40,730
proposed and discovered, which is recursively calling the quicksort only on the lower side subarray.

103
00:05:40,730 --> 00:05:43,160
When we do that for the same array, we will see that.

104
00:05:43,160 --> 00:05:48,680
Also when we code it, we will see that it will be reduced to log four and log four.

105
00:05:48,680 --> 00:05:52,160
Again remember it's always to the base two that's equal to two right.

106
00:05:52,160 --> 00:05:54,350
Because two to the power two this.

107
00:05:54,650 --> 00:05:57,860
If we raise this two to this power we will get four.

108
00:05:57,890 --> 00:06:00,980
That's why log four to the base two is equal to two.

109
00:06:00,980 --> 00:06:03,080
And we have discussed logarithm in a separate video.

110
00:06:03,080 --> 00:06:05,360
So I am not discussing that again over here.

111
00:06:05,360 --> 00:06:12,590
Now when we make this tweak over here and implement the quicksort, we will see that the maximum call

112
00:06:12,590 --> 00:06:14,210
stack will be of two calls.

113
00:06:14,210 --> 00:06:14,480
Right.

114
00:06:14,480 --> 00:06:15,560
So we will see that.

115
00:06:16,010 --> 00:06:22,640
So in this way always the space complexity or the auxiliary space can be limited to O of log n.

116
00:06:22,760 --> 00:06:24,320
That's what we will discuss over here.

117
00:06:24,320 --> 00:06:24,890
All right.

118
00:06:24,890 --> 00:06:28,040
So let's see this in great detail.

119
00:06:28,040 --> 00:06:33,230
That is recursively calling the quicksort only on the lower sized subarray.

120
00:06:33,230 --> 00:06:34,940
Let's try to understand this.

121
00:06:34,940 --> 00:06:40,310
Let's look at its let's look at this scenarios best and worst case right.

122
00:06:40,310 --> 00:06:44,120
In terms of space complexity it does not affect the time complexity.

123
00:06:44,120 --> 00:06:46,430
The time complexity remains the same.

124
00:06:46,430 --> 00:06:48,590
This only affects the space complexity.

125
00:06:48,620 --> 00:06:56,660
Now the worst case where we got the space complexity of O of N was when we always picked either the

126
00:06:56,660 --> 00:06:59,900
lower or the larger the largest element.

127
00:06:59,900 --> 00:07:00,200
Right.

128
00:07:00,200 --> 00:07:03,410
So that let's let's for example, take a sorted array.

129
00:07:03,470 --> 00:07:08,240
And if you always pick the first element, we will be always picking the lower element.

130
00:07:08,240 --> 00:07:12,320
And in that case we have seen we will get a space complexity of O of n.

131
00:07:12,320 --> 00:07:16,070
Now this is the worst case as per the previous implementation.

132
00:07:16,070 --> 00:07:23,090
Now let's try to think of the same scenario with the new implementation over here, which is which was

133
00:07:23,090 --> 00:07:24,800
brought for forward by Sedgewick.

134
00:07:24,800 --> 00:07:25,070
Right.

135
00:07:25,070 --> 00:07:29,780
So let me quickly write a pseudocode over here so that we can think through this in a better manner.

136
00:07:29,780 --> 00:07:33,440
And we will take a look at the call stack at each level.

137
00:07:33,440 --> 00:07:36,740
Because there that's where the space utilization happens right.

138
00:07:36,740 --> 00:07:38,750
That's where the auxiliary space is used.

139
00:07:38,750 --> 00:07:43,130
So this is the quicksort function which I have over here.

140
00:07:43,130 --> 00:07:48,830
Now what this does is at every point it will check, it will be passing an array.

141
00:07:48,830 --> 00:07:52,520
And it will pass in a start and end to the function.

142
00:07:53,550 --> 00:07:53,940
Right.

143
00:07:53,940 --> 00:07:58,080
So initially it will be this will be the start and this will be the end.

144
00:07:58,080 --> 00:08:00,930
And it will pass this array to the quicksort function.

145
00:08:00,930 --> 00:08:04,080
Now we will check whether start is less than end right.

146
00:08:04,080 --> 00:08:04,890
So this is true.

147
00:08:04,890 --> 00:08:06,090
Start is less than end.

148
00:08:06,090 --> 00:08:08,010
And then we will find the pivot.

149
00:08:08,010 --> 00:08:10,710
So I'm not writing the full pseudocode over here.

150
00:08:10,710 --> 00:08:16,770
The get pivot part remains the same which is what we've discussed when we discussed the logic of the

151
00:08:16,770 --> 00:08:17,280
quicksort.

152
00:08:17,280 --> 00:08:17,670
Right.

153
00:08:17,670 --> 00:08:24,000
We will make comparisons and we will find the correct place where the pivot has to be placed.

154
00:08:24,000 --> 00:08:27,090
Once the array is sorted and we will get the pivot index.

155
00:08:27,090 --> 00:08:28,710
So this is the pivot index right.

156
00:08:28,710 --> 00:08:30,540
So let me just call it as pie.

157
00:08:30,570 --> 00:08:32,940
So we are getting the pivot index at this point.

158
00:08:32,940 --> 00:08:39,810
And then as per the pseudocode over here if the left subarray is smaller we will do quicksort on the

159
00:08:39,810 --> 00:08:40,500
left subarray.

160
00:08:40,710 --> 00:08:46,440
And once we come out of it we will change the start position to pivot plus one or this pivot index.

161
00:08:46,440 --> 00:08:48,690
I'm just calling it pivot over here plus one.

162
00:08:48,690 --> 00:08:50,910
And again we will come out of it.

163
00:08:50,910 --> 00:08:52,290
And this will keep repeating.

164
00:08:52,290 --> 00:08:52,560
All right.

165
00:08:52,560 --> 00:08:53,430
So this is the.

166
00:08:54,280 --> 00:08:54,850
A function.

167
00:08:54,850 --> 00:08:58,390
So over here notice that we have in this code.

168
00:08:58,390 --> 00:09:01,150
In this pseudo code we have iteration as well as recursion.

169
00:09:01,150 --> 00:09:01,420
Right.

170
00:09:01,420 --> 00:09:05,200
So this part this whole part comes within the while loop.

171
00:09:05,200 --> 00:09:05,890
This part.

172
00:09:05,890 --> 00:09:08,170
So there is an iteration happening over here.

173
00:09:08,170 --> 00:09:10,390
And then inside we have recursion.

174
00:09:10,390 --> 00:09:11,410
So over here we have recursion.

175
00:09:11,410 --> 00:09:12,550
We have recursion over here.

176
00:09:12,550 --> 00:09:18,520
So what we are doing is again as we have mentioned over here, we are making recursive calls only on

177
00:09:18,520 --> 00:09:20,500
the lower sized subarray.

178
00:09:20,500 --> 00:09:22,030
Now let's try to understand this.

179
00:09:22,060 --> 00:09:25,300
We will walk through this example so that we can understand it.

180
00:09:25,300 --> 00:09:28,690
Let me quickly revise what we have discussed so far.

181
00:09:28,690 --> 00:09:36,040
We are trying to see the implication of recursively calling only on the lower sized subarray, especially

182
00:09:36,040 --> 00:09:41,200
in the case where we have this case where we had a space complexity of O of N, right.

183
00:09:41,200 --> 00:09:43,300
So this is the pseudocode.

184
00:09:43,990 --> 00:09:45,970
We have iteration in the while loop.

185
00:09:45,970 --> 00:09:48,370
So this all these things comes inside the while loop.

186
00:09:48,370 --> 00:09:50,620
So there is iteration happening over here.

187
00:09:50,620 --> 00:09:56,140
And then we will recursively call the quicksort function which is this whole function over here only

188
00:09:56,140 --> 00:09:57,370
on the lower size subarray.

189
00:09:57,370 --> 00:09:59,020
So that's what we are discussing.

190
00:09:59,020 --> 00:10:03,190
Now let's say we call quicksort with this array over here 12345.

191
00:10:03,190 --> 00:10:04,600
We pick one as the pivot.

192
00:10:04,600 --> 00:10:05,080
All right.

193
00:10:05,080 --> 00:10:10,720
So we are trying to just take this as the first element as the pivot so that we encounter the worst

194
00:10:10,720 --> 00:10:18,010
case scenario because we want to see how this uh, change in the algorithm affects this worst case scenario.

195
00:10:18,010 --> 00:10:19,480
So that's what we are trying to find out.

196
00:10:19,480 --> 00:10:24,430
So in this case we pass the quicksort we we call the quicksort function.

197
00:10:24,430 --> 00:10:27,850
And the array is 12345 which is this array over here.

198
00:10:27,850 --> 00:10:28,390
Right.

199
00:10:28,390 --> 00:10:31,630
So we we take this element as the pivot.

200
00:10:31,630 --> 00:10:33,940
We find the pivot as one right.

201
00:10:34,390 --> 00:10:36,550
And we fix its index right.

202
00:10:36,550 --> 00:10:37,720
We fix its index.

203
00:10:37,720 --> 00:10:42,100
And then as per the previous implementation we find the left and right right.

204
00:10:42,100 --> 00:10:45,340
So the left in this case would be empty right.

205
00:10:45,340 --> 00:10:48,100
Because there's nothing to less than one.

206
00:10:48,100 --> 00:10:49,240
So the left is empty.

207
00:10:49,240 --> 00:10:51,700
And the right will have this part over here.

208
00:10:51,700 --> 00:10:53,590
So so far there is no change.

209
00:10:53,590 --> 00:10:54,760
And it should be clear.

210
00:10:54,760 --> 00:10:55,090
Right.

211
00:10:55,090 --> 00:10:58,060
So the left is empty and the right has 2 to 5.

212
00:10:58,060 --> 00:11:04,990
Now what happens is over here we will check whether the left subarray is smaller or the right subarray

213
00:11:04,990 --> 00:11:05,620
is smaller.

214
00:11:05,620 --> 00:11:09,310
In this case the left subarray has no elements at all right.

215
00:11:09,310 --> 00:11:12,250
So this one is smaller compared to the right subarray.

216
00:11:12,250 --> 00:11:13,990
So we come over here right.

217
00:11:13,990 --> 00:11:18,670
So we come over here and we call quicksort on the left subarray.

218
00:11:18,730 --> 00:11:21,190
In this case that's just empty right.

219
00:11:21,190 --> 00:11:22,030
It's empty.

220
00:11:22,030 --> 00:11:25,300
So what will happen is we will return right.

221
00:11:25,300 --> 00:11:29,020
So again let me also keep track of the call stack.

222
00:11:29,020 --> 00:11:30,700
So let me make some space over here.

223
00:11:30,700 --> 00:11:36,130
We are going to keep track of the call stack over here because we are calling the quicksort again recursively.

224
00:11:36,130 --> 00:11:39,130
Whatever is over here right will be stored in the call stack.

225
00:11:39,130 --> 00:11:42,070
So let me just denote it as queue 125.

226
00:11:42,070 --> 00:11:44,560
So this one over here is put into the call stack.

227
00:11:44,560 --> 00:11:44,920
Right.

228
00:11:44,920 --> 00:11:48,670
And then we call the quicksort again with this queue I mean quicksort.

229
00:11:48,670 --> 00:11:52,030
And we are over here we call the quicksort again.

230
00:11:52,030 --> 00:11:54,040
Now what happens again.

231
00:11:54,040 --> 00:11:55,510
We have to pass the array.

232
00:11:55,510 --> 00:11:57,850
And we have to pass the start and end end right.

233
00:11:57,850 --> 00:11:59,170
We are not creating any new array.

234
00:11:59,170 --> 00:12:02,050
So the same array will be passed but the indices will change.

235
00:12:02,050 --> 00:12:05,200
So at this point the start what is the start.

236
00:12:05,200 --> 00:12:09,940
We will pass the start which is already there and the end we have we are passing the left right.

237
00:12:09,940 --> 00:12:11,620
Remember when when.

238
00:12:11,620 --> 00:12:14,380
Look at the normal case so that you can understand this.

239
00:12:14,530 --> 00:12:16,900
Let me just, uh, make some space over here.

240
00:12:17,820 --> 00:12:20,970
In the normal case, let's say this is the pivot.

241
00:12:20,970 --> 00:12:25,080
So when we are calling quicksort on this part, the star doesn't change.

242
00:12:25,080 --> 00:12:27,030
But the end earlier the end was over.

243
00:12:27,030 --> 00:12:31,650
Here when we call the quicksort on this part we will make the end as pivot minus one.

244
00:12:32,670 --> 00:12:32,970
Right.

245
00:12:32,970 --> 00:12:36,510
So that we want only this part, the quicksort, to run only on this part.

246
00:12:36,540 --> 00:12:36,960
Right.

247
00:12:36,960 --> 00:12:39,240
So in this case also we are calling it on the left.

248
00:12:39,240 --> 00:12:41,850
But the only thing is that the left is empty.

249
00:12:41,850 --> 00:12:43,770
So again we are calling it with the array.

250
00:12:43,800 --> 00:12:47,730
The start does not change but the end is changed to pivot minus one.

251
00:12:47,730 --> 00:12:49,320
And in this case pivot is zero right.

252
00:12:49,320 --> 00:12:52,230
So start is zero and zero minus one is minus one.

253
00:12:52,230 --> 00:12:55,050
So that's I'm just simplifying it to empty.

254
00:12:55,050 --> 00:12:58,080
So we are calling the quicksort on an empty array.

255
00:12:58,080 --> 00:12:59,130
There's nothing over here.

256
00:12:59,130 --> 00:12:59,520
Right.

257
00:12:59,520 --> 00:13:02,970
And then when we come to the function again this is the quicksort function.

258
00:13:02,970 --> 00:13:05,160
We will check whether start is less than end.

259
00:13:05,160 --> 00:13:07,050
Over here it's zero and minus one.

260
00:13:07,050 --> 00:13:08,790
Zero is not less than minus one.

261
00:13:08,790 --> 00:13:10,440
So we will come out of it right.

262
00:13:10,440 --> 00:13:12,750
So what will happen is we will return.

263
00:13:12,750 --> 00:13:17,460
So we will return to where the quicksort was called recursively.

264
00:13:17,460 --> 00:13:20,640
And when we return the call stack will be removed.

265
00:13:20,640 --> 00:13:20,850
Right.

266
00:13:20,850 --> 00:13:23,130
So this will be removed out of the call stack.

267
00:13:23,860 --> 00:13:25,600
All right, now what happens?

268
00:13:25,600 --> 00:13:26,800
We are over here.

269
00:13:26,800 --> 00:13:27,010
Right?

270
00:13:27,010 --> 00:13:27,880
We came out.

271
00:13:27,880 --> 00:13:28,780
We came out.

272
00:13:28,780 --> 00:13:31,450
So there's no more recursive call on the call stack.

273
00:13:31,450 --> 00:13:36,970
We come to the next line of the code, we come over here and start is changed to pivot plus one.

274
00:13:36,970 --> 00:13:39,790
So we found the place of this as zero right.

275
00:13:39,790 --> 00:13:41,170
So this is the zero index.

276
00:13:41,170 --> 00:13:44,170
This is one this 2345 etc. 1234.

277
00:13:44,170 --> 00:13:44,440
Right.

278
00:13:44,440 --> 00:13:46,960
So the one was fixed at index zero.

279
00:13:46,960 --> 00:13:52,900
So start is changed again I'm just writing it as two so that it's easy again.

280
00:13:52,900 --> 00:13:55,060
Let's just think of it in terms of the elements right.

281
00:13:55,060 --> 00:13:57,940
So start is changed to this element right.

282
00:13:57,940 --> 00:14:00,040
So start is changed to this element.

283
00:14:00,040 --> 00:14:04,060
And then we call the function recursively on this part.

284
00:14:04,060 --> 00:14:05,530
So again what happens.

285
00:14:05,530 --> 00:14:06,280
We come out.

286
00:14:06,280 --> 00:14:08,140
We check whether start is less than n.

287
00:14:08,140 --> 00:14:09,190
Yes it's true.

288
00:14:09,190 --> 00:14:11,320
Again we come and we find the pivot right.

289
00:14:11,320 --> 00:14:12,370
So pivot is two.

290
00:14:12,400 --> 00:14:13,090
It is fixed.

291
00:14:13,090 --> 00:14:14,020
And this happens again.

292
00:14:14,020 --> 00:14:15,430
So let's see what happens again.

293
00:14:15,430 --> 00:14:22,030
So we call the uh the get pivot part the partition function on this part.

294
00:14:22,030 --> 00:14:23,800
So two is the pivot right.

295
00:14:23,800 --> 00:14:26,200
So let's uh clear this up.

296
00:14:26,200 --> 00:14:29,500
So we are calling the quicksort on this part the indices.

297
00:14:29,500 --> 00:14:30,820
Again the whole array is passed.

298
00:14:30,820 --> 00:14:32,650
But the indices are this and this right.

299
00:14:32,650 --> 00:14:35,770
So we are just looking at this part of the array.

300
00:14:35,770 --> 00:14:37,300
And we fix this.

301
00:14:37,330 --> 00:14:38,560
We fix this over here.

302
00:14:38,560 --> 00:14:39,910
And what happens.

303
00:14:40,420 --> 00:14:41,470
Let me write that over here.

304
00:14:41,470 --> 00:14:44,590
We call it we fix the pivot which is two.

305
00:14:44,590 --> 00:14:47,620
We fix its position and its left is now empty.

306
00:14:47,620 --> 00:14:48,010
Right.

307
00:14:48,010 --> 00:14:50,620
We are just looking at this part of the array.

308
00:14:50,620 --> 00:14:55,180
There is nothing to its left right, left is empty and right has three, four, five.

309
00:14:55,180 --> 00:14:56,710
So right has three, four, five.

310
00:14:58,320 --> 00:15:04,170
Now we will look at which is lesser is the lesser left subarray smaller or the right subarray smaller.

311
00:15:04,200 --> 00:15:06,540
Again we see that the left subarray is smaller.

312
00:15:06,540 --> 00:15:10,020
So we call quicksort on the left subarray.

313
00:15:10,050 --> 00:15:11,670
Again it's called on the empty.

314
00:15:11,700 --> 00:15:14,490
When we make this call this this one over here.

315
00:15:14,490 --> 00:15:16,350
This one over here is put into the call stack.

316
00:15:16,350 --> 00:15:19,800
So let's write that over here Q 2 to 5 is put into the call stack.

317
00:15:19,800 --> 00:15:20,220
Right.

318
00:15:20,220 --> 00:15:26,250
And because this is empty again when we check while start less than end it will break and we will return

319
00:15:26,250 --> 00:15:26,460
right.

320
00:15:26,460 --> 00:15:29,400
This will return to the function where it was called.

321
00:15:29,400 --> 00:15:32,760
So when it returns this is removed from the call stack.

322
00:15:32,760 --> 00:15:33,300
Right.

323
00:15:33,900 --> 00:15:35,070
So again it's removed.

324
00:15:35,070 --> 00:15:36,840
So what can you notice over here.

325
00:15:36,930 --> 00:15:40,050
Earlier when we had this we had the call stack.

326
00:15:40,050 --> 00:15:41,580
The call stack looked like this right.

327
00:15:41,580 --> 00:15:45,120
1 to 5 and again 2 to 5.

328
00:15:45,120 --> 00:15:47,760
Again 3 to 5 4 to 5.

329
00:15:48,710 --> 00:15:49,790
And 5 to 5.

330
00:15:49,790 --> 00:15:51,950
So order of n right in the call stack.

331
00:15:51,950 --> 00:15:57,620
But over here you can see it always keeps returning because we are just calling it on the, uh, empty.

332
00:15:57,650 --> 00:15:57,860
Right.

333
00:15:57,860 --> 00:15:58,340
In this case.

334
00:15:58,340 --> 00:15:59,060
In the worst case.

335
00:15:59,060 --> 00:15:59,330
Right.

336
00:15:59,330 --> 00:16:00,290
So it returns.

337
00:16:00,290 --> 00:16:06,290
So you can notice that in the worst case earlier when we got the space complexity of O of n, in this

338
00:16:06,290 --> 00:16:12,050
case, the call stack always has only one element or the call stack is just one element deep.

339
00:16:12,050 --> 00:16:12,470
Right.

340
00:16:12,470 --> 00:16:18,920
So in the case of the worst case, by making this tweak, that is by recursively calling the quicksort

341
00:16:18,920 --> 00:16:25,760
algorithm only on the lower sized subarray, we are getting the call stack to be only one element deep,

342
00:16:25,760 --> 00:16:26,210
right?

343
00:16:26,210 --> 00:16:32,120
But again, you cannot say that the space complexity by making this tweak is O of one.

344
00:16:32,120 --> 00:16:32,960
That would be wrong, right?

345
00:16:32,960 --> 00:16:33,950
This is not O of one.

346
00:16:33,950 --> 00:16:34,550
Why is that?

347
00:16:34,550 --> 00:16:37,280
So let's look at a generic case for this.

348
00:16:37,280 --> 00:16:38,300
Let me clear this.

349
00:16:38,300 --> 00:16:38,840
All right.

350
00:16:38,840 --> 00:16:41,270
Now over here we had our algorithm.

351
00:16:41,270 --> 00:16:43,130
Now let's look at the generic case.

352
00:16:43,130 --> 00:16:45,890
Let's say this is the array which is given to us.

353
00:16:45,890 --> 00:16:48,380
Now what we are doing is we will find the pivot.

354
00:16:48,380 --> 00:16:50,150
So we will find the pivot.

355
00:16:50,150 --> 00:16:52,130
We will fix it at its correct position.

356
00:16:52,130 --> 00:16:54,320
Now we will look at the two subarrays.

357
00:16:54,350 --> 00:16:57,320
Now let's say in this case the left subarray is smaller.

358
00:16:57,320 --> 00:17:00,980
Visually it's also smaller in size right rather than the right subarray.

359
00:17:00,980 --> 00:17:04,160
So we will call quicksort on the smaller subarray.

360
00:17:05,200 --> 00:17:06,520
That's what we do over here.

361
00:17:06,550 --> 00:17:08,530
Now, what about the right side?

362
00:17:08,530 --> 00:17:08,770
Right.

363
00:17:08,770 --> 00:17:10,150
How is it handled now?

364
00:17:10,150 --> 00:17:11,350
Once we are out of this.

365
00:17:11,350 --> 00:17:11,590
Right.

366
00:17:11,590 --> 00:17:15,070
Once we have called this, and once we are out of it, we will change.

367
00:17:15,070 --> 00:17:16,630
Start to pivot plus one.

368
00:17:16,630 --> 00:17:19,150
So start would come over here right.

369
00:17:19,150 --> 00:17:20,770
And end is still over here.

370
00:17:20,770 --> 00:17:22,420
And we will again.

371
00:17:22,420 --> 00:17:24,790
We will while start is less than n.

372
00:17:24,790 --> 00:17:25,630
So this is true.

373
00:17:25,630 --> 00:17:27,250
So again we will call pivot.

374
00:17:27,250 --> 00:17:33,340
So what we are trying to do is for the larger side larger subarray we will find the new pivot over here.

375
00:17:33,340 --> 00:17:37,390
And again we will call quicksort on the smaller side recursively.

376
00:17:37,390 --> 00:17:39,730
So this is what's happening with this algorithm right.

377
00:17:39,730 --> 00:17:45,070
Earlier we were just finding the pivot calling the quicksort recursively on the smaller side again calling

378
00:17:45,070 --> 00:17:47,170
the quicksort recursively on the larger side.

379
00:17:47,170 --> 00:17:51,040
But instead of that what we're doing is on the larger subarray.

380
00:17:51,040 --> 00:17:55,810
What we're doing is we are again finding the new pivot, we are fixing it, and we are calling quicksort

381
00:17:55,810 --> 00:17:58,150
recursively only on the smaller side.

382
00:17:58,150 --> 00:18:00,040
So this is what is happening over here.

383
00:18:00,490 --> 00:18:05,830
Now let's go ahead and look at the worst case scenario of this modified algorithm.

384
00:18:06,470 --> 00:18:12,440
With this tweak in the algorithm, which we discussed, where we only recursively call on the lower

385
00:18:12,440 --> 00:18:13,790
sized sub frame.

386
00:18:13,790 --> 00:18:19,820
The worst case will happen if you always pick the pivot such that it divides the given array into two

387
00:18:19,820 --> 00:18:24,350
equal halves, or if you pick the pivot as the middle value or the median, right?

388
00:18:24,350 --> 00:18:25,880
What would happen in that case?

389
00:18:25,880 --> 00:18:27,950
Let's say the given array is of length n.

390
00:18:27,950 --> 00:18:33,980
We divide it into n by two, n by two, and this over here on the left side, let's say it keeps going

391
00:18:33,980 --> 00:18:36,830
on till we get to a size of one of the array.

392
00:18:36,830 --> 00:18:37,220
Right.

393
00:18:37,220 --> 00:18:41,480
So in this case what is this case where we divide into equal halves.

394
00:18:41,480 --> 00:18:46,820
Right now in this case the stack depth will be log n right.

395
00:18:46,820 --> 00:18:53,750
And therefore in this case the space complexity of this algorithm will be O of log n.

396
00:18:54,930 --> 00:18:56,310
All right, now over here.

397
00:18:56,310 --> 00:18:57,030
What's happening?

398
00:18:57,030 --> 00:18:58,800
Let's quickly draw the stack.

399
00:18:58,800 --> 00:19:02,640
In this case, over here we have n that calls it for n by two.

400
00:19:02,640 --> 00:19:05,610
Then we have n by four and it keeps going till one.

401
00:19:05,610 --> 00:19:09,210
Now this depth as we have seen many times is log n right.

402
00:19:09,210 --> 00:19:16,410
So that's why by making this change we are able to ensure that the auxiliary space used or the call

403
00:19:16,410 --> 00:19:20,130
stack space used is always of order log n.

404
00:19:20,430 --> 00:19:27,300
Without this tweak it was ranging from log n to N, but by making this tweak that is, by recursively

405
00:19:27,300 --> 00:19:33,060
calling the quicksort only on the lower size subarray, we have seen that in the worst case, we have

406
00:19:33,060 --> 00:19:35,550
only a depth of one right in the call stack.

407
00:19:35,550 --> 00:19:40,470
So when we look at the right side, we are no longer we don't have anything in the call stack any longer.

408
00:19:40,470 --> 00:19:41,940
So that's the advantage right.

409
00:19:41,940 --> 00:19:45,210
So again over here also we call the pivot.

410
00:19:45,210 --> 00:19:48,120
And then on the left side we call the quicksort recursively.

411
00:19:48,120 --> 00:19:49,260
That's how this works.

412
00:19:49,260 --> 00:19:51,990
But then there is nothing on the on on the call stack.

413
00:19:51,990 --> 00:19:52,290
Right.

414
00:19:52,290 --> 00:19:53,160
We remove it.

415
00:19:53,160 --> 00:19:59,970
And we have seen in the algorithm we do a fresh start where we look we have the start over here and

416
00:19:59,970 --> 00:20:01,770
over here we find the new pivot.

417
00:20:01,770 --> 00:20:05,460
And we recursively call only on the lower sized subarray.

418
00:20:05,460 --> 00:20:11,010
So by doing this we got that the space complexity is log n o of log n.

419
00:20:11,040 --> 00:20:14,130
The worst case space complexity is O of log n.

420
00:20:14,130 --> 00:20:16,680
So far we have discussed these things.

421
00:20:16,680 --> 00:20:21,360
We have understood the quicksort, we have understood the time complexity, and we have understood that

422
00:20:21,360 --> 00:20:26,640
to avoid the worst case, we can either pick a pivot randomly or the middle value.

423
00:20:26,640 --> 00:20:28,680
And we have understood the space complexity.

424
00:20:28,680 --> 00:20:29,040
Right.

425
00:20:29,040 --> 00:20:34,560
And we have seen we've made a tweak where we can recursively call the quicksort only on the lower size

426
00:20:34,560 --> 00:20:35,010
subarray.

427
00:20:35,010 --> 00:20:40,650
And by doing this we got that the space complexity will always be the worst case.

428
00:20:40,650 --> 00:20:44,220
Worst case space complexity will be O of log n.

429
00:20:44,460 --> 00:20:49,890
So we have seen that the time complexity of the quicksort is O of n log n, right.

430
00:20:49,890 --> 00:20:50,910
That's the best case.

431
00:20:50,910 --> 00:20:52,380
And the average case.

432
00:20:52,380 --> 00:20:59,160
Now to avoid O of n square in the case of sorted data, it's recommended to pick the middle element

433
00:20:59,160 --> 00:21:01,110
or a random element as the pivot.

434
00:21:01,110 --> 00:21:05,730
And we have seen that the space complexity of the quicksort is O of log n.

435
00:21:05,730 --> 00:21:11,520
And for this, to ensure that this is the worst case we have, we have to make the tweak where we do

436
00:21:11,520 --> 00:21:17,340
the recursive call on the quick side quick of the quicksort only on the lower sized subarray, right.

437
00:21:17,340 --> 00:21:23,040
If you don't this if you don't do this in the case where we always pick the pivot as the minimum or

438
00:21:23,040 --> 00:21:25,860
the maximum, we would get O of n space.

439
00:21:25,860 --> 00:21:28,230
And we are avoiding this by making this tweak.

440
00:21:28,230 --> 00:21:30,690
Now let's go ahead and code our solution.

441
00:21:30,690 --> 00:21:36,690
We will also look at the two cases where we do the recursive call only on the lower size, and where

442
00:21:36,690 --> 00:21:41,730
we do it on both the side cases, both the sides left and right, and we will see the difference in

443
00:21:41,730 --> 00:21:42,600
the call stack.