1
00:00:00,860 --> 00:00:03,440
Hi everyone, let's do this problem.

2
00:00:03,440 --> 00:00:05,810
You are given an array of integers.

3
00:00:05,810 --> 00:00:12,050
Write a function that will take this array as input and return the sorted array using quicksort.

4
00:00:12,080 --> 00:00:16,400
Now let's say the given array is 732516.

5
00:00:16,400 --> 00:00:22,730
Now we have to use quicksort to sort this array, and the output should be 123567.

6
00:00:22,730 --> 00:00:24,410
So this is the question.

7
00:00:24,410 --> 00:00:27,080
And quicksort is a very famous algorithm.

8
00:00:27,080 --> 00:00:31,250
Let's go ahead and understand this in a very good manner in this video.

9
00:00:31,250 --> 00:00:34,700
Now the objectives of this video are three.

10
00:00:34,700 --> 00:00:37,970
The first objective is to understand quicksort right.

11
00:00:37,970 --> 00:00:44,240
We will try to see how the logic works so that we can go ahead and write the code of quicksort.

12
00:00:44,240 --> 00:00:45,710
So that is point number one.

13
00:00:45,710 --> 00:00:49,880
The second objective is that we will look at the time complexity of the quicksort.

14
00:00:49,880 --> 00:00:53,630
And we will see how we can avoid the worst case.

15
00:00:53,630 --> 00:00:58,340
Or we will look at recommendations to avoid the worst case of the time complexity.

16
00:00:58,340 --> 00:01:04,970
And finally we will look at the space complexity, and we will make a few tweaks to the way we discuss

17
00:01:04,970 --> 00:01:08,720
the quicksort to be able to optimize the space complexity.

18
00:01:08,720 --> 00:01:13,040
So these are the three things that we will look at and understand in this video.

19
00:01:13,040 --> 00:01:17,960
Now let's go ahead and start with the first point which is to understand the quicksort.

20
00:01:18,440 --> 00:01:18,920
All right.

21
00:01:18,950 --> 00:01:22,280
Now the quicksort is a divide and conquer algorithm.

22
00:01:22,280 --> 00:01:26,480
With this we mean that it divides the given problem into subproblems.

23
00:01:26,480 --> 00:01:30,770
And by solving the subproblems it solves the main problem.

24
00:01:30,770 --> 00:01:32,690
So that's how quicksort works.

25
00:01:32,690 --> 00:01:36,890
Now let me give you a little bit more of an idea of how quicksort works.

26
00:01:36,890 --> 00:01:42,020
We will select one element of the given array and we will call it the pivot.

27
00:01:42,020 --> 00:01:48,380
And then we will go ahead and find its correct position in the sorted array once the array is sorted.

28
00:01:48,380 --> 00:01:50,390
So that's how quicksort works.

29
00:01:50,390 --> 00:01:53,120
Now let's go ahead and understand this in a better manner.

30
00:01:53,120 --> 00:01:57,140
Using an example for this I have 63195.

31
00:01:57,140 --> 00:01:59,600
So let's say this is the array that we need to sort.

32
00:01:59,600 --> 00:02:02,060
And let's go ahead and write the indices.

33
00:02:02,890 --> 00:02:07,270
Now, once we sort this given array, it should look like this, right?

34
00:02:07,270 --> 00:02:08,920
13569.

35
00:02:08,920 --> 00:02:10,570
So over here this is sorted.

36
00:02:10,570 --> 00:02:12,850
Now let's write the indices over here as well.

37
00:02:12,850 --> 00:02:15,790
So we have 0123 and four.

38
00:02:15,790 --> 00:02:22,000
Now we have discussed previously that how we go about in the quicksort is that we select a pivot.

39
00:02:22,000 --> 00:02:23,830
So let's go ahead and do that.

40
00:02:23,830 --> 00:02:26,260
And remember the pivot can be any element.

41
00:02:26,260 --> 00:02:29,350
You can take any element of the given array as the pivot.

42
00:02:29,350 --> 00:02:36,310
And what we try to do is we will find the correct index of where the pivot should be after the sorting

43
00:02:36,310 --> 00:02:36,820
is done.

44
00:02:36,820 --> 00:02:39,880
Now how we go about this is that we will have the pivot.

45
00:02:39,880 --> 00:02:45,760
Let's say this is the pivot element and every element in the given array, which is less than the pivot

46
00:02:45,760 --> 00:02:48,160
element, we will place it to its left.

47
00:02:48,670 --> 00:02:48,970
All right.

48
00:02:48,970 --> 00:02:52,720
So all elements smaller than the pivot would be placed to its left.

49
00:02:52,720 --> 00:02:54,820
Now this part over here is not sorted.

50
00:02:54,820 --> 00:02:57,610
So this is not sorted but we just place it over here.

51
00:02:57,610 --> 00:02:58,030
All right.

52
00:02:58,030 --> 00:03:02,590
And all the elements which are larger than the pivot, we will place it over here.

53
00:03:02,590 --> 00:03:05,080
Again these two parts are not sorted.

54
00:03:05,080 --> 00:03:09,310
But what happens over here is that the pivot will be in its correct place.

55
00:03:09,310 --> 00:03:14,350
Let's take an example in this array over here which is given to us, which is to be sorted.

56
00:03:14,350 --> 00:03:18,430
Let's say we take the element six, which is the first element as the pivot.

57
00:03:18,430 --> 00:03:20,740
So we have six over here, which is the pivot.

58
00:03:20,770 --> 00:03:27,670
Now let's go through the given array and place all the elements which are less than six to its left.

59
00:03:27,670 --> 00:03:28,720
So we have three.

60
00:03:28,750 --> 00:03:30,640
We have one and we have five.

61
00:03:30,640 --> 00:03:32,620
So these three are less than six right.

62
00:03:32,620 --> 00:03:34,750
So we place them to the left of six.

63
00:03:34,750 --> 00:03:36,940
And then what is greater than six.

64
00:03:36,940 --> 00:03:37,750
We have nine.

65
00:03:37,750 --> 00:03:39,820
So we place that to the right of six.

66
00:03:39,820 --> 00:03:42,340
So that's what we discussed over here right now.

67
00:03:42,340 --> 00:03:45,820
Notice that once we have done this this part is not sorted.

68
00:03:45,820 --> 00:03:46,180
Right.

69
00:03:46,180 --> 00:03:48,850
And again this part in this case it's sorted.

70
00:03:48,850 --> 00:03:53,020
But it may or may not be sorted if you had multiple elements let's say we have eight also.

71
00:03:53,020 --> 00:03:54,760
So probably eight also would come over here.

72
00:03:54,760 --> 00:03:56,530
So this part is also not sorted.

73
00:03:56,530 --> 00:04:01,390
But when we look at the indices now let's write it zero, 123 and four.

74
00:04:01,390 --> 00:04:05,710
Notice that the index of six is the correct index.

75
00:04:05,710 --> 00:04:07,600
Once the array is sorted right.

76
00:04:07,600 --> 00:04:10,300
Once the array is sorted, six should be at index three.

77
00:04:10,300 --> 00:04:14,530
And by doing this operation we got six to its correct index.

78
00:04:14,530 --> 00:04:18,880
So this is the basic principle behind which quicksort works.

79
00:04:18,880 --> 00:04:19,360
All right.

80
00:04:19,360 --> 00:04:21,730
Now let's take a bigger example.

81
00:04:21,730 --> 00:04:26,980
And let's walk through the different steps because that's the best way that we can visualize how the

82
00:04:26,980 --> 00:04:27,940
quicksort works.

83
00:04:27,940 --> 00:04:30,040
So let's say this is the given array to us.

84
00:04:30,040 --> 00:04:32,320
And we have to use quicksort.

85
00:04:32,320 --> 00:04:33,340
And we have to sort it.

86
00:04:33,340 --> 00:04:36,940
Now let's walk through one complete pass right.

87
00:04:36,940 --> 00:04:38,560
Let's take one element as pivot.

88
00:04:38,560 --> 00:04:44,860
And let's see all the steps that get into the quicksort so that we get that particular element in its

89
00:04:44,860 --> 00:04:45,670
correct position.

90
00:04:45,670 --> 00:04:50,920
So let's see that now over here let's take 14 as the pivot which is the first element.

91
00:04:51,340 --> 00:04:58,000
Now later in the video we will discuss what is what is the recommended way to select the pivot to solve

92
00:04:58,000 --> 00:04:58,810
some problems.

93
00:04:58,810 --> 00:04:59,230
All right.

94
00:04:59,230 --> 00:05:01,990
For now let's just take the first element as the pivot.

95
00:05:01,990 --> 00:05:03,460
So 14 is the pivot.

96
00:05:03,460 --> 00:05:05,590
And then we will have two pointers.

97
00:05:05,590 --> 00:05:07,060
Let's call it I and J.

98
00:05:07,150 --> 00:05:10,630
So I would be placed over here and j will be placed over here.

99
00:05:10,630 --> 00:05:10,900
Right.

100
00:05:10,900 --> 00:05:13,960
So I is the next element after the first element.

101
00:05:13,960 --> 00:05:15,340
And J is over here.

102
00:05:15,790 --> 00:05:19,720
Now we are going to look at these elements as we saw previously.

103
00:05:19,720 --> 00:05:26,680
And what we want to achieve is that we want to move all the elements which are less than 14 to its left.

104
00:05:27,190 --> 00:05:28,780
So let's write that over here.

105
00:05:28,780 --> 00:05:30,160
We want 14 over here.

106
00:05:30,160 --> 00:05:36,340
Anything less than 14 should be towards its left, and anything greater than 14 should be towards its

107
00:05:36,340 --> 00:05:36,940
right.

108
00:05:36,940 --> 00:05:41,050
So this is what we want to do, so that we get 14 at its correct position.

109
00:05:41,050 --> 00:05:42,700
And 14 is the pivot over here.

110
00:05:42,700 --> 00:05:46,150
So what we do is we have these two pointers over here.

111
00:05:46,150 --> 00:05:53,530
And then we keep moving the pointer I towards the right till we get to an element which is greater than

112
00:05:53,530 --> 00:05:54,250
the pivot.

113
00:05:54,250 --> 00:05:54,970
Why is that.

114
00:05:54,970 --> 00:05:58,510
So we want anything less than 14 to be on its left.

115
00:05:58,510 --> 00:06:01,840
So if something is on its left then we just move forward.

116
00:06:01,840 --> 00:06:02,170
Right.

117
00:06:02,170 --> 00:06:08,920
But when we reach an element which is greater than 14 from this side, we stop because we want to change

118
00:06:08,920 --> 00:06:09,340
it, right?

119
00:06:09,340 --> 00:06:12,640
We want only elements which are less than 14 on its left.

120
00:06:12,640 --> 00:06:14,620
So this is the left pointer.

121
00:06:14,620 --> 00:06:17,770
And we want elements less than 14 on the left.

122
00:06:17,770 --> 00:06:21,700
So the opposite greater the opposite of less is greater.

123
00:06:21,700 --> 00:06:27,880
So when we move the left pointer and when we encounter an element which is the opposite of less which

124
00:06:27,880 --> 00:06:29,200
is greater, we stop.

125
00:06:29,200 --> 00:06:36,880
Similarly we have the I the j pointer over here, and we keep moving this towards the left in this direction,

126
00:06:37,600 --> 00:06:41,920
right till we get to an element which is less than the pivot.

127
00:06:41,920 --> 00:06:44,980
Again, over here in the right we want greater right.

128
00:06:44,980 --> 00:06:46,960
We want items which are greater than 14.

129
00:06:46,960 --> 00:06:50,470
So if we get something which is greater than 14 it's fine.

130
00:06:50,470 --> 00:06:52,060
We just keep moving the J.

131
00:06:52,060 --> 00:06:54,280
But the opposite of greater is less.

132
00:06:54,280 --> 00:06:58,810
So till we get to an element which is opposite of greater, we keep moving the j.

133
00:06:58,840 --> 00:06:59,320
All right.

134
00:06:59,320 --> 00:07:02,530
So in this case initially itself we can see that I.

135
00:07:02,680 --> 00:07:03,580
Is the.

136
00:07:03,580 --> 00:07:06,070
The eye pointer is pointing to an element which is greater.

137
00:07:06,070 --> 00:07:07,000
So we stop.

138
00:07:07,000 --> 00:07:08,230
Eye stops over here.

139
00:07:08,230 --> 00:07:10,180
Now let's say I was 11 over here.

140
00:07:10,180 --> 00:07:11,950
Then we would have moved forward, right.

141
00:07:11,950 --> 00:07:14,110
So 12 is also not greater.

142
00:07:14,110 --> 00:07:15,490
So we are still moved forward.

143
00:07:15,490 --> 00:07:16,990
And we would have stopped at 18.

144
00:07:16,990 --> 00:07:21,040
But in this case the first element itself is greater than the pivot.

145
00:07:21,040 --> 00:07:23,260
So the eye pointer stops over here.

146
00:07:23,260 --> 00:07:24,730
And the j pointer.

147
00:07:24,730 --> 00:07:29,380
The first element where the j pointer is there itself is less than the pivot.

148
00:07:29,380 --> 00:07:31,840
So the j pointer also stops over here.

149
00:07:31,840 --> 00:07:32,230
All right.

150
00:07:32,260 --> 00:07:38,410
Now once we have identified these two positions what we do is we will swap these two again.

151
00:07:38,410 --> 00:07:44,080
Notice what we are trying to do is we are getting all the items which are less than 14 towards the left,

152
00:07:44,080 --> 00:07:46,990
and all the items which are greater than 14 towards the right.

153
00:07:46,990 --> 00:07:50,620
And at the end we will place 14 in its correct position.

154
00:07:50,620 --> 00:07:55,870
At the current moment, 14 is over here and we keep just doing these two parts and then we will move

155
00:07:55,870 --> 00:07:57,220
14 to its correct position.

156
00:07:57,220 --> 00:07:58,840
So that's what we are going to do.

157
00:07:58,840 --> 00:07:59,260
All right.

158
00:07:59,260 --> 00:08:01,840
So let let me just take make some space over here.

159
00:08:01,840 --> 00:08:04,720
So we identified that we need to swap these two.

160
00:08:04,750 --> 00:08:06,460
So let's do that now.

161
00:08:06,460 --> 00:08:11,050
Once we swap these two nine comes over here and 22 comes over here.

162
00:08:11,050 --> 00:08:12,670
Now I and J are over here.

163
00:08:12,670 --> 00:08:14,710
All right again we keep doing this.

164
00:08:14,710 --> 00:08:21,100
We move I in this direction till we encounter an element which is greater than 14.

165
00:08:21,100 --> 00:08:22,180
So let's do that.

166
00:08:22,870 --> 00:08:24,340
So I will reach over here.

167
00:08:24,340 --> 00:08:24,730
Right?

168
00:08:24,730 --> 00:08:27,280
So I will reach over here when I was over here.

169
00:08:27,280 --> 00:08:28,840
That's not greater than 14.

170
00:08:28,840 --> 00:08:31,180
So it moves forward and it comes to 18.

171
00:08:31,180 --> 00:08:32,680
Now 18 is greater than 14.

172
00:08:32,680 --> 00:08:33,880
So we stop over here.

173
00:08:33,880 --> 00:08:40,240
Now when it comes to the j pointer we move it in this direction till we encounter an element which is

174
00:08:40,240 --> 00:08:41,110
less than 14.

175
00:08:41,110 --> 00:08:45,880
Again remember, the easy way to visualize this is that we want 14 over here.

176
00:08:45,880 --> 00:08:48,220
Anything less than 14 should be on the left.

177
00:08:48,220 --> 00:08:51,340
Anything greater than 14 should be on the right right.

178
00:08:51,340 --> 00:08:53,470
So the opposite of less is greater.

179
00:08:53,470 --> 00:08:57,190
So in the less part we keep moving till we get the opposite of this.

180
00:08:57,190 --> 00:08:59,050
So we got something greater than 14.

181
00:08:59,050 --> 00:09:03,880
We stop in the with respect to the j pointer the opposite of greater is less right.

182
00:09:03,880 --> 00:09:09,100
So we move in the left direction in this direction till we get to something which is opposite of greater

183
00:09:09,100 --> 00:09:10,090
which is less.

184
00:09:10,090 --> 00:09:11,140
So let's do that.

185
00:09:11,140 --> 00:09:12,250
So we keep moving.

186
00:09:12,250 --> 00:09:15,610
And when we reach over here we have 1313 is less than 14.

187
00:09:15,610 --> 00:09:16,840
So we stop right.

188
00:09:16,840 --> 00:09:19,450
So again we have identified these two elements.

189
00:09:19,450 --> 00:09:22,270
And what we do is we go ahead and swap these two.

190
00:09:22,270 --> 00:09:22,720
All right.

191
00:09:22,720 --> 00:09:24,790
So let's make some space over here.

192
00:09:24,790 --> 00:09:26,560
We are trying to swap these two right.

193
00:09:26,560 --> 00:09:27,460
So let's do that.

194
00:09:27,460 --> 00:09:33,130
Now when we swap these two you can see we have 13 over here where earlier 18 was.

195
00:09:33,130 --> 00:09:34,900
And then we have 18 over here.

196
00:09:34,900 --> 00:09:35,170
Right.

197
00:09:35,170 --> 00:09:36,340
We have swapped these two.

198
00:09:36,760 --> 00:09:38,590
And the pointers are over here.

199
00:09:38,590 --> 00:09:41,920
I is over here and J is over here again.

200
00:09:41,920 --> 00:09:47,080
We keep moving the I till we encounter an element which is greater than 14.

201
00:09:47,080 --> 00:09:47,350
Right.

202
00:09:47,350 --> 00:09:49,210
Again remember we have 14.

203
00:09:49,210 --> 00:09:51,310
Anything less than 14 should be on the left.

204
00:09:51,310 --> 00:09:53,410
Anything greater than 14 should be on the right.

205
00:09:53,410 --> 00:09:55,240
So opposite of less is greater.

206
00:09:55,240 --> 00:09:58,630
So we keep moving I till we get to something greater than 14.

207
00:09:58,630 --> 00:10:02,740
So when we do that we reach over here because 19 is greater than 14.

208
00:10:02,740 --> 00:10:03,880
So I stops over here.

209
00:10:03,880 --> 00:10:10,420
And with respect to J we keep moving it in this direction till we get to something which is less than

210
00:10:10,420 --> 00:10:10,840
14.

211
00:10:10,840 --> 00:10:11,110
Right.

212
00:10:11,110 --> 00:10:14,470
So when we reach over here we find eight is less than 14.

213
00:10:14,470 --> 00:10:15,760
So J stops over here.

214
00:10:15,760 --> 00:10:18,160
Now we have identified these two again.

215
00:10:18,160 --> 00:10:20,320
We swap right again we swap these two.

216
00:10:20,350 --> 00:10:22,150
So let's write that over here.

217
00:10:22,150 --> 00:10:29,710
We have to swap 19 and eight and the array becomes 14 nine 1213, eight, 11, 19, 18 and 22.

218
00:10:29,710 --> 00:10:34,300
So these two have been swapped and eight is over here and 19 is over here.

219
00:10:34,810 --> 00:10:35,200
All right.

220
00:10:35,200 --> 00:10:38,140
So I is over here and J is over here.

221
00:10:38,140 --> 00:10:44,440
Now we continue we move I till we get to something which is greater than 14.

222
00:10:44,440 --> 00:10:44,650
Right.

223
00:10:44,650 --> 00:10:46,000
Again remember 14.

224
00:10:46,000 --> 00:10:49,930
We want less on the less left side and we want greater on the right.

225
00:10:49,930 --> 00:10:55,660
So when it comes to the I which is the left pointer, move till the opposite of less which is greater

226
00:10:55,660 --> 00:10:56,440
that is reached.

227
00:10:56,440 --> 00:10:56,620
Right.

228
00:10:56,620 --> 00:10:59,200
So we keep moving it and we will reach over here.

229
00:10:59,200 --> 00:10:59,530
Right.

230
00:10:59,530 --> 00:11:03,370
Because 11 is not greater than 14, 19 is greater than 14.

231
00:11:03,370 --> 00:11:04,750
So I will stop over here.

232
00:11:04,750 --> 00:11:09,160
Now when it comes to J we move till the opposite of greater which is less right.

233
00:11:09,160 --> 00:11:10,570
So we move over here.

234
00:11:10,570 --> 00:11:12,670
Now 11 is less than 14.

235
00:11:12,670 --> 00:11:14,320
So J stops over here.

236
00:11:14,320 --> 00:11:20,530
Now at this point we can see that till till now right till over here always I was less than J.

237
00:11:20,530 --> 00:11:21,130
Right.

238
00:11:21,490 --> 00:11:25,060
But over here you can see that I has become greater than J.

239
00:11:25,060 --> 00:11:25,420
Right.

240
00:11:25,420 --> 00:11:29,020
So when this happens, when this happens we stop.

241
00:11:29,910 --> 00:11:30,270
All right.

242
00:11:30,270 --> 00:11:33,510
So we stop moving the I and J pointers.

243
00:11:33,510 --> 00:11:37,440
And at this point all we need to do is to get to this right.

244
00:11:37,440 --> 00:11:41,160
We need to get to this where we have all the items less than 14 on the left.

245
00:11:41,160 --> 00:11:43,920
And then we have 14 and all the items greater than 14.

246
00:11:43,920 --> 00:11:45,210
We have it on the right.

247
00:11:45,210 --> 00:11:48,360
So you can see that all these elements right.

248
00:11:48,360 --> 00:11:52,800
All these elements are less than 14 and these are greater than 14.

249
00:11:52,800 --> 00:11:53,130
Right.

250
00:11:53,130 --> 00:11:59,880
So to achieve this all we need to do is we need to swap these two, this item and this item that is

251
00:11:59,880 --> 00:12:00,420
the pivot.

252
00:12:00,420 --> 00:12:04,500
And the last item which is less than um 14.

253
00:12:04,500 --> 00:12:04,650
Right.

254
00:12:04,650 --> 00:12:05,250
Which is 11.

255
00:12:05,250 --> 00:12:07,440
In this case we need to just swap these two.

256
00:12:07,470 --> 00:12:08,340
So let's do that.

257
00:12:08,340 --> 00:12:09,990
Let's make some space over here.

258
00:12:09,990 --> 00:12:14,760
Now if we swap these two you can see that our arrangement becomes this.

259
00:12:14,760 --> 00:12:17,100
And at this point we just swap these two.

260
00:12:17,100 --> 00:12:17,280
Right.

261
00:12:17,280 --> 00:12:18,150
11 is over here.

262
00:12:18,150 --> 00:12:19,710
And 14 came over here.

263
00:12:20,100 --> 00:12:27,570
Now at this point you can see that all the items to the left of 14, that is these items are less than

264
00:12:27,570 --> 00:12:28,140
14.

265
00:12:28,140 --> 00:12:31,500
And all the items to the right of 14 are greater than 14.

266
00:12:31,500 --> 00:12:31,770
Right.

267
00:12:31,770 --> 00:12:35,880
So we have achieved less than 14 and then greater.

268
00:12:37,060 --> 00:12:41,980
This is what we were trying to achieve and we have successfully achieved it right now.

269
00:12:41,980 --> 00:12:49,450
Remember, 14 was the pivot and we were able to successfully place the pivot in its correct position.

270
00:12:49,450 --> 00:12:53,500
So once the array is sorted, the pivot should be over here, right?

271
00:12:53,500 --> 00:12:54,520
This is the correct place.

272
00:12:54,520 --> 00:12:55,840
This is what we have seen previously.

273
00:12:55,840 --> 00:12:59,470
Also when we took the element six and with a smaller array we had seen it.

274
00:12:59,470 --> 00:12:59,800
Right.

275
00:12:59,800 --> 00:13:04,330
So in this way we have placed the pivot in the correct position.

276
00:13:04,330 --> 00:13:04,930
All right.

277
00:13:05,860 --> 00:13:07,450
Let me make some space over here.

278
00:13:07,450 --> 00:13:09,490
Just clean this up a bit.

279
00:13:09,490 --> 00:13:10,030
All right?

280
00:13:10,060 --> 00:13:16,630
Now, once we have achieved, once we have achieved this, then what we will do is we will recursively

281
00:13:16,630 --> 00:13:17,800
call the quicksort.

282
00:13:17,800 --> 00:13:18,220
All right.

283
00:13:18,220 --> 00:13:21,910
So we have now two sides the left side and the right side.

284
00:13:21,910 --> 00:13:26,620
And we will call the quicksort on these two sides recurse recursively.

285
00:13:26,620 --> 00:13:29,050
So quicksort is a recursive algorithm.

286
00:13:29,050 --> 00:13:30,160
So we will do that.

287
00:13:30,160 --> 00:13:33,580
And by doing this we will be able to sort this array.

288
00:13:33,580 --> 00:13:36,130
So this is the logic behind the quicksort.

289
00:13:36,160 --> 00:13:39,340
So we have successfully learned the first point.

290
00:13:39,340 --> 00:13:40,930
That is we have understood the quicksort.

291
00:13:40,930 --> 00:13:49,060
What we do is we select a pivot and then we do some operations to find the correct position of the pivot,

292
00:13:49,060 --> 00:13:53,110
so that everything less than the pivot is on its left right.

293
00:13:53,110 --> 00:13:54,310
And then we have the pivot.

294
00:13:54,310 --> 00:13:57,280
And anything greater than the pivot is on its right.

295
00:13:57,280 --> 00:14:03,460
And then we recursively call the quicksort right on this part of the array and on this part of the array.

296
00:14:03,460 --> 00:14:04,570
And we keep doing this.

297
00:14:04,570 --> 00:14:06,280
So this is how quicksort works.

298
00:14:06,280 --> 00:14:06,760
All right.

299
00:14:06,760 --> 00:14:12,580
Now before we go ahead we need to make some tweaks right before we go ahead and code our solution.

300
00:14:12,580 --> 00:14:15,550
Now first let's look at the time complexity.

301
00:14:15,550 --> 00:14:18,160
Let's look at the best case and the worst case.

302
00:14:18,160 --> 00:14:22,240
And then let's look at some recommendations to avoid the worst case.