1
00:00:00,800 --> 00:00:01,670
Hi everyone.

2
00:00:01,670 --> 00:00:06,320
In this video let's go ahead and code the quicksort which we have discussed.

3
00:00:06,530 --> 00:00:14,630
And we will first code the version where we will recursively call the quicksort on the lower sized subarray.

4
00:00:15,380 --> 00:00:16,700
All right so we discussed this.

5
00:00:16,700 --> 00:00:21,710
So this will help to ensure that the space complexity is O of log n.

6
00:00:21,710 --> 00:00:23,480
So we will implement this first.

7
00:00:23,480 --> 00:00:28,310
And then let's also implement the case where we call the quicksort recursively on both the sides.

8
00:00:28,310 --> 00:00:31,040
And we will compare the call stack in both the cases.

9
00:00:31,040 --> 00:00:31,730
All right.

10
00:00:31,730 --> 00:00:38,120
Now to do this to implement the quicksort we will need a function to partition a given array right.

11
00:00:38,120 --> 00:00:40,610
So this will find the pivot.

12
00:00:40,610 --> 00:00:45,050
It will it will decide a pivot and it will find the correct position of that pivot.

13
00:00:45,050 --> 00:00:48,980
So this function will take in an array and it will take in a start.

14
00:00:48,980 --> 00:00:50,600
And it will take in an end.

15
00:00:50,600 --> 00:00:51,020
Right.

16
00:00:51,020 --> 00:00:53,840
So this is one function that we will need to write.

17
00:00:53,840 --> 00:00:56,450
And then we will need to write the quicksort function.

18
00:00:57,080 --> 00:00:59,120
This also will take in an array.

19
00:00:59,120 --> 00:01:01,700
And it will have a start and an end.

20
00:01:01,700 --> 00:01:02,330
Right.

21
00:01:03,110 --> 00:01:07,700
And inside this we will decide how to recursively call quicksort.

22
00:01:07,700 --> 00:01:09,380
All right so let's get started.

23
00:01:09,380 --> 00:01:12,380
And initially uh also let me write this part.

24
00:01:12,380 --> 00:01:14,960
Once we are done with this we will define an array.

25
00:01:14,960 --> 00:01:21,200
Let's say it's uh 54032 or let's say one.

26
00:01:21,200 --> 00:01:23,840
And then we will call quicksort on this array.

27
00:01:23,840 --> 00:01:24,380
Right.

28
00:01:26,730 --> 00:01:32,550
And after this we will console log the array and this should give us the sorted array.

29
00:01:32,550 --> 00:01:33,690
So that's the intent.

30
00:01:33,720 --> 00:01:38,850
Now to start with let's go ahead and write the partition function.

31
00:01:38,850 --> 00:01:40,710
Now it takes in an array.

32
00:01:40,710 --> 00:01:44,130
Let's say that if the start is not specified we take it as zero.

33
00:01:44,130 --> 00:01:49,290
And if the end is not specified we take this as array dot length minus one.

34
00:01:49,530 --> 00:01:49,860
All right.

35
00:01:49,860 --> 00:01:51,390
And the same is true for this function.

36
00:01:51,390 --> 00:01:54,330
Also because over here we are just calling the quicksort right.

37
00:01:54,330 --> 00:01:57,600
So if the start is not passed let's take it as zero.

38
00:01:57,600 --> 00:02:02,280
And if the end is not passed let's take it as array dot length minus one.

39
00:02:02,550 --> 00:02:03,000
All right.

40
00:02:03,000 --> 00:02:05,340
And again one more point over here.

41
00:02:05,340 --> 00:02:10,830
We will when we write the partition function we will write the version where we pick the middle value

42
00:02:10,830 --> 00:02:11,790
as the pivot.

43
00:02:11,790 --> 00:02:12,270
All right.

44
00:02:12,270 --> 00:02:18,990
So this will ensure that in case the array which is passed to B which is to be sorted is already sorted,

45
00:02:18,990 --> 00:02:22,890
then we don't want to have the time complexity of O of n square.

46
00:02:22,890 --> 00:02:23,280
Right.

47
00:02:23,280 --> 00:02:28,080
And we discussed that to avoid that, it's recommended that we pick the middle value as the pivot.

48
00:02:28,080 --> 00:02:30,540
So in this implementation we will do it like that.

49
00:02:30,960 --> 00:02:36,750
So for this we just need to make a minor tweak to what we discussed in the logic section.

50
00:02:36,750 --> 00:02:37,050
Right.

51
00:02:37,050 --> 00:02:39,960
So let's implement that and discuss that over here as well.

52
00:02:39,960 --> 00:02:40,560
All right.

53
00:02:40,560 --> 00:02:42,990
So first we will write the partition function.

54
00:02:42,990 --> 00:02:47,250
Now once we are inside the partition function first let's find the middle value.

55
00:02:47,250 --> 00:02:51,030
Because as we discussed we are going to take the middle value as the pivot.

56
00:02:51,030 --> 00:02:55,110
So the middle index can be found by math dot floor.

57
00:02:55,560 --> 00:02:57,990
And we will take the middle of start and end.

58
00:02:57,990 --> 00:02:59,520
So start plus end.

59
00:03:00,350 --> 00:03:01,730
Divided by two.

60
00:03:02,060 --> 00:03:04,310
And I will need one more bracket over here.

61
00:03:05,460 --> 00:03:05,790
All right.

62
00:03:05,790 --> 00:03:11,400
So we get the middle value of the start and the respective end when we call the partition function.

63
00:03:11,400 --> 00:03:14,820
Now what we do is to take the middle.

64
00:03:14,820 --> 00:03:18,810
Like when we discussed it in the video, we always took the pivot value as the first element.

65
00:03:18,810 --> 00:03:19,140
Right.

66
00:03:19,140 --> 00:03:24,720
So to make it the same case, let's swap the middle value and the first value.

67
00:03:24,720 --> 00:03:28,500
So I need a swap function where I will be passing the array.

68
00:03:28,500 --> 00:03:34,230
And I will pass the start value and the middle index right the start index and the middle index.

69
00:03:34,230 --> 00:03:36,180
So let's write the swap function.

70
00:03:36,180 --> 00:03:39,330
That's going to be a simple function right function swap.

71
00:03:40,870 --> 00:03:45,400
And this will take in an array and it will take two indices.

72
00:03:45,960 --> 00:03:48,090
And let's have a temporary variable.

73
00:03:48,090 --> 00:03:53,880
Let temp is equal to array at I and we can say array.

74
00:03:54,950 --> 00:03:57,650
At I is equal to r I a j.

75
00:03:59,050 --> 00:04:00,880
And then we say area J.

76
00:04:03,030 --> 00:04:04,350
Is equal to temp.

77
00:04:04,710 --> 00:04:06,030
So we have swapped these two values.

78
00:04:06,030 --> 00:04:07,590
So it's a simple swap function.

79
00:04:07,590 --> 00:04:09,210
So we call this over here.

80
00:04:09,210 --> 00:04:14,640
And we change the position of the middle value and the start.

81
00:04:14,640 --> 00:04:15,630
So what's happening over here.

82
00:04:15,630 --> 00:04:17,550
Let's also parallelly analyze it.

83
00:04:17,550 --> 00:04:20,250
Let's say over here we have this array which is passed.

84
00:04:20,250 --> 00:04:23,220
And we want to uh we want to sort it.

85
00:04:23,220 --> 00:04:28,050
So in this case the partition let's say it's a sorted array okay.

86
00:04:28,050 --> 00:04:32,610
So we are actually doing this to avoid the case where the passed array is sorted.

87
00:04:32,610 --> 00:04:33,690
So let's say this is the array.

88
00:04:33,690 --> 00:04:34,350
It's sorted.

89
00:04:34,350 --> 00:04:35,250
So what do we do.

90
00:04:35,250 --> 00:04:37,860
We find the middle value and that's three.

91
00:04:37,860 --> 00:04:41,970
And we swap the middle value and the start value.

92
00:04:41,970 --> 00:04:44,790
So after doing the swap the array will look like this.

93
00:04:44,790 --> 00:04:45,840
We have three over here.

94
00:04:45,840 --> 00:04:47,940
Then one then two.

95
00:04:47,970 --> 00:04:51,210
Sorry we have three over here where we had one.

96
00:04:51,210 --> 00:04:55,650
Then we have two and where we had three we'll have one because we just swapped these two right.

97
00:04:55,650 --> 00:04:56,670
So we have one over here.

98
00:04:56,670 --> 00:04:58,740
Then we have four and then we have five.

99
00:04:58,740 --> 00:05:00,030
Now it looks like this.

100
00:05:00,030 --> 00:05:03,450
And then we will proceed with the same way that we discussed in the logic.

101
00:05:03,450 --> 00:05:09,570
That is we will take this value as the pivot and we will change the values of change the position of

102
00:05:09,570 --> 00:05:12,120
these values over here by comparing and swapping.

103
00:05:12,120 --> 00:05:15,180
And then finally we will put the pivot in the correct position.

104
00:05:15,180 --> 00:05:17,190
So this is the only change that we are doing.

105
00:05:17,190 --> 00:05:18,600
We are identifying the middle.

106
00:05:18,600 --> 00:05:21,390
And then we are swapping the middle and the start position.

107
00:05:21,390 --> 00:05:24,450
And then it goes on as we discussed in the video before.

108
00:05:24,450 --> 00:05:25,710
So let's go ahead.

109
00:05:26,190 --> 00:05:28,290
Now let's have a variable pivot.

110
00:05:28,290 --> 00:05:32,580
So let pivot is equal to array at start right.

111
00:05:32,580 --> 00:05:35,040
Because now we have moved it to the start.

112
00:05:35,040 --> 00:05:37,620
So the pivot value over here is three right.

113
00:05:37,620 --> 00:05:38,490
Start is zero.

114
00:05:38,490 --> 00:05:41,940
So the pivot value is three right zero which is three.

115
00:05:42,090 --> 00:05:42,630
All right.

116
00:05:42,660 --> 00:05:44,130
Now let's have two pointers.

117
00:05:44,130 --> 00:05:45,330
Let's call it I and J.

118
00:05:45,330 --> 00:05:48,630
So let I be the first value after start right.

119
00:05:48,630 --> 00:05:50,400
We just need to compare these values.

120
00:05:50,400 --> 00:05:51,450
So this is start.

121
00:05:51,450 --> 00:05:53,430
So this is where I should be right.

122
00:05:53,430 --> 00:05:55,080
Which is the next value after I.

123
00:05:55,110 --> 00:05:57,690
So I should be equal to start plus one.

124
00:05:58,650 --> 00:05:59,190
All right.

125
00:05:59,190 --> 00:06:00,780
And Jay will be the end.

126
00:06:00,780 --> 00:06:01,020
Right.

127
00:06:01,020 --> 00:06:03,690
So let Jay is equal to end.

128
00:06:04,110 --> 00:06:08,580
Now we just need to keep moving them and swapping them as appropriate.

129
00:06:08,580 --> 00:06:09,990
So let's have a while loop.

130
00:06:09,990 --> 00:06:12,750
While I less than equal to J.

131
00:06:12,750 --> 00:06:16,170
We will keep checking and swapping if required.

132
00:06:16,170 --> 00:06:16,680
All right.

133
00:06:16,680 --> 00:06:21,000
And while the value at array I while array I.

134
00:06:22,760 --> 00:06:24,560
Is less than the pivot.

135
00:06:24,560 --> 00:06:27,980
If that is true, then it's its position is fine, right?

136
00:06:27,980 --> 00:06:32,810
So if the value at I is less than the pivot, we can even write less than equal to pivot.

137
00:06:32,810 --> 00:06:36,530
As long as this is true let's keep moving I I plus plus.

138
00:06:37,690 --> 00:06:43,720
And for Jay when it comes to Jay while the value at Ray Jay.

139
00:06:45,130 --> 00:06:47,170
Is greater than the pivot.

140
00:06:48,160 --> 00:06:48,850
It's fine.

141
00:06:48,850 --> 00:06:51,640
So we can just keep moving, which is J minus.

142
00:06:51,640 --> 00:06:52,270
Minus.

143
00:06:52,570 --> 00:06:58,840
Now by the end of this code, we will have identified the I and J where the values are not in order

144
00:06:58,840 --> 00:06:59,920
and we need to swap them.

145
00:06:59,920 --> 00:07:00,220
Right.

146
00:07:00,220 --> 00:07:04,540
So we before we swap them we need to check whether I is less than J.

147
00:07:04,540 --> 00:07:08,470
We have seen this in the video right at the end when we need to stop, right?

148
00:07:08,470 --> 00:07:10,090
I j will be less than I.

149
00:07:10,120 --> 00:07:12,280
So if that is the case we don't swap.

150
00:07:12,280 --> 00:07:15,280
So if I is less than J then we will just swap, right?

151
00:07:15,280 --> 00:07:18,190
We will swap and we are calling our swap function.

152
00:07:18,190 --> 00:07:21,370
We will pass the array and we will pass I and J.

153
00:07:21,820 --> 00:07:22,390
All right.

154
00:07:22,390 --> 00:07:28,060
Now at the end, as we saw in the video, all we need to do is we need to swap after we are out of this

155
00:07:28,060 --> 00:07:28,600
while loop.

156
00:07:28,600 --> 00:07:34,540
Right after we are out of this while loop J will be less than I, right J will be less than I because

157
00:07:34,540 --> 00:07:38,020
it will go on as long as j I is less than equal to j.

158
00:07:38,020 --> 00:07:43,690
So if j is less than I or I is greater than j, we will come out of it, and at that point we just need

159
00:07:43,690 --> 00:07:48,280
to swap the position of J and the start.

160
00:07:48,280 --> 00:07:53,020
Because at start at start we have our, uh, pivot, right?

161
00:07:53,020 --> 00:07:56,590
Our pivot is at start because we swap the middle and the start.

162
00:07:56,590 --> 00:07:58,660
So at the start we have our pivot.

163
00:07:58,660 --> 00:08:00,760
So we need to swap the pivot and J.

164
00:08:00,760 --> 00:08:04,630
And we get the pivot in the correct index where it should be.

165
00:08:04,630 --> 00:08:07,810
And the index where the pivot has been placed is j.

166
00:08:07,810 --> 00:08:09,820
So we return j at the end.

167
00:08:09,820 --> 00:08:14,350
And that's the end of our swap function sorry our partition function.

168
00:08:14,350 --> 00:08:16,450
So we have written the partition function.

169
00:08:16,450 --> 00:08:18,910
Now let's proceed to write the quicksort.

170
00:08:19,420 --> 00:08:24,370
Now as we said over here we are going to first write the version where we will recursively call the

171
00:08:24,370 --> 00:08:26,170
quicksort on the lower sized array.

172
00:08:26,320 --> 00:08:26,800
All right.

173
00:08:26,800 --> 00:08:27,880
So let's get started.

174
00:08:27,880 --> 00:08:33,430
Now in this implementation you will see that as we discussed there is an iterative part and there is

175
00:08:33,430 --> 00:08:35,200
a recursive part.

176
00:08:35,200 --> 00:08:40,450
So for the iterative part we have a while loop while start less than end.

177
00:08:43,350 --> 00:08:44,730
And we will do something right.

178
00:08:44,730 --> 00:08:45,630
We will do something.

179
00:08:45,630 --> 00:08:48,540
So let me just quickly explain what's happening over here.

180
00:08:48,540 --> 00:08:51,720
Now for this, let's have let me comment this part.

181
00:08:51,720 --> 00:08:53,490
And over here I have an array.

182
00:08:53,490 --> 00:08:54,810
And these are all elements.

183
00:08:54,810 --> 00:08:57,030
And let's say P is the pivot.

184
00:08:57,980 --> 00:09:00,860
And then let's say we have few more elements over here.

185
00:09:00,860 --> 00:09:05,450
So we will identify that this is the lower sized array sub array.

186
00:09:05,450 --> 00:09:08,900
And we will recursively call quicksort over here which will happen inside.

187
00:09:08,900 --> 00:09:09,350
All right.

188
00:09:09,380 --> 00:09:14,030
Now once we are done with this we will change the start to this part over here.

189
00:09:14,030 --> 00:09:16,790
So start will be here and end will be here.

190
00:09:16,790 --> 00:09:18,770
And our call stack is now clear.

191
00:09:18,770 --> 00:09:19,010
Right.

192
00:09:19,010 --> 00:09:20,270
There's nothing waiting over there.

193
00:09:20,270 --> 00:09:23,120
And then we again call quicksort.

194
00:09:23,120 --> 00:09:23,330
Right.

195
00:09:23,330 --> 00:09:30,170
By finding the pivot of this part, by finding the pivot of this sub array, we um we find the pivot.

196
00:09:30,170 --> 00:09:33,650
And then on the left side of that we will call we will call quicksort.

197
00:09:33,650 --> 00:09:35,900
So we will that's what we are trying to do.

198
00:09:35,900 --> 00:09:40,100
So once we are out of this we want it to go to the right side right.

199
00:09:40,100 --> 00:09:44,300
So this will be taken care by the while loop which is taken care iteratively.

200
00:09:44,300 --> 00:09:45,560
Now as we write it.

201
00:09:45,560 --> 00:09:50,240
And again after we are done with writing the code, we will also walk through the code and it will become

202
00:09:50,240 --> 00:09:50,840
more clear.

203
00:09:50,840 --> 00:09:54,380
But over here this is the part played by the while loop.

204
00:09:54,380 --> 00:09:59,510
Alright, so let's go ahead and write the remaining part of the code and we will again see and try to

205
00:09:59,510 --> 00:10:00,980
understand it in a better manner.

206
00:10:00,980 --> 00:10:03,380
So once we are one, start is less than n.

207
00:10:03,380 --> 00:10:06,770
So initially let's say the whole array is passed to start is less than end.

208
00:10:06,770 --> 00:10:07,340
All right.

209
00:10:07,340 --> 00:10:10,340
So we call the partition function which we wrote.

210
00:10:10,340 --> 00:10:13,790
So let's say we have a variable pivot.

211
00:10:13,790 --> 00:10:14,780
Let's call it id.

212
00:10:16,040 --> 00:10:21,710
Pivot index for index, and this will store the value that is returned by the partition function, which

213
00:10:21,710 --> 00:10:23,150
is the position of the pivot.

214
00:10:23,150 --> 00:10:23,510
Right.

215
00:10:23,510 --> 00:10:27,350
So partition array and start and end.

216
00:10:28,500 --> 00:10:28,920
All right.

217
00:10:28,920 --> 00:10:35,160
So after we have called this, as we discussed over here and in the previous video, we will recursively

218
00:10:35,160 --> 00:10:38,190
call the quicksort on the lower sized subarray.

219
00:10:38,190 --> 00:10:42,870
So we need to find out whether the left or the right subarray is the lower sized subarray.

220
00:10:42,870 --> 00:10:47,160
So for this let's uh find the size of the two subarrays.

221
00:10:47,160 --> 00:10:51,120
And then we will decide where we should recursively call the quicksort.

222
00:10:51,180 --> 00:10:57,030
Now over here notice that this this length over here is nothing but start minus pivot index.

223
00:10:57,030 --> 00:10:57,210
Right.

224
00:10:57,210 --> 00:10:58,740
So it will give us this length over here.

225
00:10:58,740 --> 00:11:01,890
And this length over here is end minus pivot index.

226
00:11:01,890 --> 00:11:04,980
So we just need to check which among these two is smaller.

227
00:11:04,980 --> 00:11:07,200
So let's write a if function for that.

228
00:11:07,200 --> 00:11:09,330
So if pivot id.

229
00:11:11,220 --> 00:11:14,430
Minus start, which is the left subarray.

230
00:11:14,430 --> 00:11:21,180
If the size of that is less than n minus pivoted x, which is the size of the right subarray right.

231
00:11:21,180 --> 00:11:26,460
So if the left one is the lower sized subarray, then we will call quicksort over here.

232
00:11:26,460 --> 00:11:27,780
So quicksort.

233
00:11:29,180 --> 00:11:30,830
And we will pass the array.

234
00:11:31,190 --> 00:11:32,990
Now for the left side.

235
00:11:32,990 --> 00:11:33,320
Right.

236
00:11:33,320 --> 00:11:37,160
The start will be the same, but the end will be pivoted minus one.

237
00:11:37,160 --> 00:11:41,510
So we will have start comma pivoted minus one.

238
00:11:41,870 --> 00:11:42,320
All right.

239
00:11:42,320 --> 00:11:47,390
Now this will this is a recursive call on the lower uh size sub array.

240
00:11:47,390 --> 00:11:47,750
Right.

241
00:11:47,750 --> 00:11:50,960
So again let me just write comments over here so that it becomes clear.

242
00:11:50,990 --> 00:11:52,160
It becomes clear.

243
00:11:52,160 --> 00:11:54,800
So recursively call quicksort.

244
00:11:56,200 --> 00:11:57,940
On lower sized.

245
00:11:58,950 --> 00:11:59,550
SubArray.

246
00:12:01,340 --> 00:12:01,760
All right.

247
00:12:01,760 --> 00:12:08,630
Now, after we are out of this, right after it's done and we come out of this, we need to change our

248
00:12:08,630 --> 00:12:14,150
start to this, this one over here so that when we come over here, we see start is less than end.

249
00:12:14,150 --> 00:12:17,150
And again we partition this part and it goes on.

250
00:12:17,150 --> 00:12:17,480
Right.

251
00:12:17,480 --> 00:12:25,220
So over here, after we are out of this we have to say start is equal to pivot ID plus one.

252
00:12:26,090 --> 00:12:26,540
All right.

253
00:12:26,570 --> 00:12:33,050
Now, if this is not the lower sized subarray, if that, that means if this is the lower sized subarray.

254
00:12:33,050 --> 00:12:36,410
So then we have to write the else part over here.

255
00:12:36,410 --> 00:12:38,300
And then we call quicksort on that part.

256
00:12:38,300 --> 00:12:40,820
So quicksort again we pass the array.

257
00:12:40,850 --> 00:12:45,560
Now notice if we are passing this part right the start is pivoted plus one.

258
00:12:45,560 --> 00:12:47,180
And the end is still the same.

259
00:12:47,180 --> 00:12:48,920
So over here we write pivot id.

260
00:12:50,410 --> 00:12:54,370
Plus one as the start and we pass end as end itself.

261
00:12:54,370 --> 00:12:57,580
Now let's say this was the smaller subarray.

262
00:12:57,580 --> 00:12:59,380
So let's say this had only two elements.

263
00:12:59,380 --> 00:13:03,250
Now after we are out of this we need to sort this part also.

264
00:13:03,250 --> 00:13:03,430
Right.

265
00:13:03,430 --> 00:13:05,350
And that would be taken care by the while loop.

266
00:13:05,350 --> 00:13:09,970
So for this we need to set the end to pivot ID minus one.

267
00:13:09,970 --> 00:13:11,590
So we do that over here.

268
00:13:11,590 --> 00:13:15,250
End is equal to pivot ID minus one.

269
00:13:15,250 --> 00:13:16,630
And we come over here.

270
00:13:16,630 --> 00:13:20,290
Then this partition will be called on this subarray over here.

271
00:13:21,300 --> 00:13:23,340
Because start is still less than end.

272
00:13:23,370 --> 00:13:23,790
Right.

273
00:13:23,790 --> 00:13:24,960
So that's the end.

274
00:13:24,960 --> 00:13:27,990
So that comes that that brings us to the end of this function.

275
00:13:27,990 --> 00:13:28,920
And we are done.

276
00:13:28,920 --> 00:13:31,920
Now let's test our code and see whether it's working.

277
00:13:32,340 --> 00:13:34,080
So we have a test case over here.

278
00:13:34,080 --> 00:13:37,740
Now let's run it and see what we get.

279
00:13:41,220 --> 00:13:41,580
All right.

280
00:13:41,580 --> 00:13:43,800
So okay this there is the spelling is wrong.

281
00:13:43,800 --> 00:13:45,420
So this has to be capital S.

282
00:13:45,420 --> 00:13:47,310
So let me change that over here.

283
00:13:47,610 --> 00:13:49,140
And let's run it again.

284
00:13:49,140 --> 00:13:53,310
And you can see we get 01345 which is sorted.

285
00:13:53,310 --> 00:13:56,130
So yes our code is working right.

286
00:13:56,130 --> 00:13:59,730
So again notice we have taken the pivot as the middle value.

287
00:13:59,730 --> 00:14:04,830
And we have implemented the case where we recursively call quicksort on the lower sized subarray.

288
00:14:04,980 --> 00:14:05,550
All right.

289
00:14:05,580 --> 00:14:08,250
Now let me just come comment this over here.

290
00:14:09,810 --> 00:14:15,750
And let's go ahead and implement the quicksort where we call it on both the sides.

291
00:14:15,780 --> 00:14:17,550
So let's write that over here.

292
00:14:17,550 --> 00:14:21,420
And let me call that function as quicksort again.

293
00:14:21,420 --> 00:14:23,460
So function quicksort.

294
00:14:24,450 --> 00:14:27,060
And oh, here also we pass in the array.

295
00:14:28,060 --> 00:14:29,560
And we have start.

296
00:14:29,800 --> 00:14:31,120
Let's initialize it to zero.

297
00:14:31,120 --> 00:14:36,580
If the value is not given and n is equal to array dot length minus one.

298
00:14:37,350 --> 00:14:37,770
All right.

299
00:14:37,770 --> 00:14:38,910
Now over here.

300
00:14:38,910 --> 00:14:45,120
When we wrote the case in the previous solution, we had an iterative part as well as a recursive part,

301
00:14:45,120 --> 00:14:48,240
but we don't have that over here in this implementation.

302
00:14:48,240 --> 00:14:48,540
All right.

303
00:14:48,540 --> 00:14:49,290
So let me just check.

304
00:14:49,290 --> 00:14:50,130
We have enough length.

305
00:14:50,130 --> 00:14:50,370
Yes.

306
00:14:50,370 --> 00:14:51,870
It's coming inside the video.

307
00:14:51,870 --> 00:14:52,410
All right.

308
00:14:52,410 --> 00:14:53,520
Now over here.

309
00:14:54,380 --> 00:14:58,010
What we do is we will check if start is less than end.

310
00:14:59,320 --> 00:14:59,710
All right.

311
00:14:59,710 --> 00:15:02,680
So if start if the start is less than end.

312
00:15:02,680 --> 00:15:04,510
So we keep doing this right.

313
00:15:04,510 --> 00:15:06,910
And we will call the quicksort.

314
00:15:06,910 --> 00:15:09,130
First we will call the partition function.

315
00:15:09,130 --> 00:15:09,970
So let's do that.

316
00:15:09,970 --> 00:15:11,650
Let pivot id.

317
00:15:12,840 --> 00:15:14,880
Is equal to partition.

318
00:15:16,040 --> 00:15:17,540
And we pass the array.

319
00:15:18,490 --> 00:15:20,500
And we pass the start and end.

320
00:15:20,890 --> 00:15:21,190
All right.

321
00:15:21,190 --> 00:15:24,940
So this will give us the pivot and it will give us the pivot index.

322
00:15:24,940 --> 00:15:28,570
And then we call quicksort again iteratively on both the sides.

323
00:15:28,570 --> 00:15:33,310
So array and again over here the left side will have the same start.

324
00:15:33,310 --> 00:15:38,770
So start and the end of the left side will be pivot minus one right pivot index minus one.

325
00:15:38,770 --> 00:15:41,020
So pivot id minus one.

326
00:15:41,020 --> 00:15:45,610
Similarly for the right side we will have the start as pivot id plus one.

327
00:15:45,610 --> 00:15:48,550
So let me write that over here quicksort array.

328
00:15:50,360 --> 00:15:53,060
And the start is pivoted plus one.

329
00:15:54,480 --> 00:15:56,460
And the end is still the same.

330
00:15:56,460 --> 00:15:56,640
Right.

331
00:15:56,640 --> 00:16:03,060
So comma and now we have iteratively called quicksort on both the subarrays right.

332
00:16:03,060 --> 00:16:05,400
And then finally we just need to return the array right.

333
00:16:05,400 --> 00:16:08,430
Because this will be a recursive call.

334
00:16:08,430 --> 00:16:11,070
So we need to return the array right.

335
00:16:11,070 --> 00:16:14,910
So over here what will happen is we will get the pivot in this case.

336
00:16:14,910 --> 00:16:18,360
And we will call quicksort on the left part right.

337
00:16:18,840 --> 00:16:21,960
So that again will find the pivot index.

338
00:16:21,960 --> 00:16:23,340
And it will keep calling.

339
00:16:23,340 --> 00:16:29,460
And once this part is sorted we come back over here and it calls quicksort again iteratively on the

340
00:16:29,460 --> 00:16:30,060
right side.

341
00:16:30,060 --> 00:16:30,540
All right.

342
00:16:30,540 --> 00:16:34,260
And then again we over here we get back the array.

343
00:16:34,260 --> 00:16:38,040
And when we call it right because we have we are returning an array.

344
00:16:38,040 --> 00:16:40,410
Similarly over here also we keep returning the array.

345
00:16:40,410 --> 00:16:42,240
Again we are doing this in place.

346
00:16:42,240 --> 00:16:44,250
So we are not creating any new array.

347
00:16:44,250 --> 00:16:49,140
So over here also you can notice that I have array as 54031.

348
00:16:49,140 --> 00:16:51,480
And then we call quicksort on the array.

349
00:16:51,480 --> 00:16:53,400
And then we are just console logging the array.

350
00:16:53,400 --> 00:16:58,800
That means this array over here which was looking like this is now changed once we have sorted it.

351
00:16:58,800 --> 00:16:59,370
All right.

352
00:16:59,370 --> 00:17:05,460
So this is the implementation where we are recursively calling quicksort on both the left and the right

353
00:17:05,460 --> 00:17:05,940
sides.

354
00:17:05,940 --> 00:17:09,060
Now let's run this and see whether this is working.

355
00:17:09,060 --> 00:17:11,670
So let me clear my console and I'm running it.

356
00:17:11,670 --> 00:17:14,340
And you can see yes it's working 01345.

357
00:17:14,340 --> 00:17:15,930
We are getting this also sorted.

358
00:17:15,930 --> 00:17:21,960
Now in the next video let's try to compare the call stack in both these implementations.