1
00:00:01,460 --> 00:00:02,210
Hi, everyone.

2
00:00:02,240 --> 00:00:08,240
So in this video, we are going to discuss about the quicksort algorithm, so this is also a recursive

3
00:00:08,240 --> 00:00:13,130
algorithm, just like the heart and quicksort algorithm is also very fast.

4
00:00:14,750 --> 00:00:16,760
So now let's discuss the algorithm.

5
00:00:16,760 --> 00:00:18,130
What is quicksort algorithm?

6
00:00:18,440 --> 00:00:20,810
So given an array and I want to sort this out.

7
00:00:21,260 --> 00:00:23,120
So let's take a random area.

8
00:00:23,140 --> 00:00:29,510
So this is eight five two two one, seven, three and four.

9
00:00:29,710 --> 00:00:31,070
So is I don't know.

10
00:00:32,299 --> 00:00:35,040
Now, I want to sort this out with the help of quicksort.

11
00:00:35,360 --> 00:00:38,380
So what Quicksort says is pick the last element.

12
00:00:39,620 --> 00:00:41,990
So the name of the last element is basically pivot.

13
00:00:42,470 --> 00:00:45,860
So what you will do, you will rearrange your elements.

14
00:00:47,210 --> 00:00:51,390
So you will rearrange the elements such that so Ford will be present here.

15
00:00:51,800 --> 00:00:55,520
So all the elements greater then for all the elements.

16
00:00:55,860 --> 00:01:01,610
Good four will be present on the right hand side, all the elements, less than four will present on

17
00:01:01,610 --> 00:01:02,420
the left hand side.

18
00:01:02,780 --> 00:01:05,330
So to one entry, they are smaller than four.

19
00:01:05,330 --> 00:01:10,060
So two, one and three will be present on the left hand side and eight, five and seven.

20
00:01:10,310 --> 00:01:11,220
So they are larger.

21
00:01:11,240 --> 00:01:12,990
So the president on the right hand side.

22
00:01:13,010 --> 00:01:15,680
So seven, eight and five.

23
00:01:15,710 --> 00:01:17,840
OK, so these parts are not sorted.

24
00:01:19,050 --> 00:01:21,760
These parts left and right hand side of what?

25
00:01:21,770 --> 00:01:22,640
They are not sorted.

26
00:01:23,120 --> 00:01:26,440
So what do you need to do after picking the pivot?

27
00:01:26,840 --> 00:01:33,380
So after taking the pivot element, you will rearrange the element in such a way that forward will be

28
00:01:33,380 --> 00:01:34,890
present at the correct position.

29
00:01:34,910 --> 00:01:39,980
So this is the calculation of forward in this today because all the elements, less than four, are

30
00:01:39,980 --> 00:01:41,240
present on the left hand side.

31
00:01:41,300 --> 00:01:43,400
OK, so this is the calculation of four.

32
00:01:43,460 --> 00:01:44,370
So what you need to do?

33
00:01:44,390 --> 00:01:45,740
I am repeating myself again.

34
00:01:46,860 --> 00:01:54,330
So this is our area which we want to sort, and the last element is X, so what I will do, I will pick

35
00:01:54,330 --> 00:01:58,080
X and the last element is called pivot in quicksort.

36
00:01:58,420 --> 00:02:04,470
So after picking the X material, you will put X in its current position.

37
00:02:04,470 --> 00:02:05,590
So all the elements good.

38
00:02:05,620 --> 00:02:08,009
The next will be present on the right hand side.

39
00:02:08,250 --> 00:02:11,770
All the elements less than X represent on the left hand side.

40
00:02:12,750 --> 00:02:15,030
So this thing rearranging.

41
00:02:15,030 --> 00:02:17,760
So this rearranging thing is basically called partition.

42
00:02:19,010 --> 00:02:21,140
So this is called partition in quicksort.

43
00:02:23,150 --> 00:02:27,590
So this is called this rearranging of elements is called partition function.

44
00:02:27,710 --> 00:02:31,460
OK, so this is called partition function.

45
00:02:31,490 --> 00:02:32,820
So here the spelling is wrong.

46
00:02:34,100 --> 00:02:35,510
So this is called partition.

47
00:02:35,950 --> 00:02:42,710
So after partitioning so let's say the Nexus B, let's say the index of Alimentarius, B, let's say

48
00:02:42,710 --> 00:02:46,420
its index is basically B, so after partitioning.

49
00:02:46,430 --> 00:02:48,120
So first step is basically partition.

50
00:02:48,800 --> 00:02:55,010
So after partitioning, what you will do, you will apply quicksort on this area, you will apply a

51
00:02:55,010 --> 00:02:56,230
quicksort on this area.

52
00:02:57,450 --> 00:03:03,090
So after a plane quicksort on this area, since it's a recursive algorithm, so this will be so this

53
00:03:03,090 --> 00:03:03,780
is a start.

54
00:03:04,710 --> 00:03:09,120
This is and so this will be the last element will be minus one.

55
00:03:09,570 --> 00:03:13,510
This is the starting this is B plus one and this is end.

56
00:03:13,860 --> 00:03:17,920
OK, so what we will do, you will apply quicksort on this area.

57
00:03:17,970 --> 00:03:19,120
So this area will be sorted.

58
00:03:19,140 --> 00:03:20,420
So it will become one, two, three.

59
00:03:21,540 --> 00:03:23,380
You will apply quicksort on this area.

60
00:03:23,400 --> 00:03:24,650
So this area will be sorted.

61
00:03:24,660 --> 00:03:30,300
So it will become five, seven and eight and four is present at position B..

62
00:03:30,610 --> 00:03:32,370
So now your computer is sorted.

63
00:03:34,200 --> 00:03:34,700
Simple.

64
00:03:36,360 --> 00:03:38,250
So that's how quixotry Waldenbooks.

65
00:03:38,430 --> 00:03:41,040
Similarly for this area, you will apply quicksort.

66
00:03:41,940 --> 00:03:44,010
This is a starting, this is the end.

67
00:03:44,250 --> 00:03:45,980
So you will apply quicksort on this area.

68
00:03:48,110 --> 00:03:50,300
And similarly, you will apply quicksort on this area.

69
00:03:50,930 --> 00:03:53,310
So this is the end and this is B plus one.

70
00:03:54,080 --> 00:03:57,450
So basically it's write the code, let's write the basics.

71
00:03:57,620 --> 00:04:00,530
I will only write the basic code and you will write the complete code.

72
00:04:02,970 --> 00:04:09,660
So what I want to do is that there will be right, because I will change the area itself, the name

73
00:04:09,660 --> 00:04:10,890
of the function is quicksort.

74
00:04:12,030 --> 00:04:17,640
I will take the area, I will take the starting next.

75
00:04:17,640 --> 00:04:20,660
I will take the next and what we need to do.

76
00:04:21,720 --> 00:04:24,270
So what we need to do, what is our approach?

77
00:04:26,970 --> 00:04:30,660
So our approach is very simple, we will pick the last element.

78
00:04:34,770 --> 00:04:37,020
So this is the work of the partition function.

79
00:04:38,950 --> 00:04:44,230
So partitioning function will put let's say the element is X, so actually present here, all the elements

80
00:04:44,230 --> 00:04:49,000
go to the next present on the right side, all the elements less than X will be president on the left

81
00:04:49,000 --> 00:04:49,420
hand side.

82
00:04:49,720 --> 00:04:54,180
So this is the working of partition function and partition function will return the index.

83
00:04:54,670 --> 00:05:00,520
So let's say the Nexus B. So partition function will return the units and we call it partition index.

84
00:05:02,700 --> 00:05:04,010
Let's call it partitioning.

85
00:05:04,290 --> 00:05:10,110
OK, so what to do, you need to apply quicksort on this area, you need to apply quicksort on this

86
00:05:10,110 --> 00:05:10,380
area.

87
00:05:10,860 --> 00:05:12,330
So this is the starting next.

88
00:05:12,390 --> 00:05:13,600
This is the end of next.

89
00:05:14,050 --> 00:05:15,360
This is the starting next.

90
00:05:15,390 --> 00:05:19,470
This is B minus one just starting next for this arizpe plus one.

91
00:05:19,470 --> 00:05:20,790
And the ending is.

92
00:05:20,790 --> 00:05:25,060
And so quicksort algorithm is a recursive algorithm.

93
00:05:25,080 --> 00:05:30,570
So first of all, the best case case is if zero element or one element, so start good, then order

94
00:05:30,570 --> 00:05:34,480
close to zero or one element in that case that is already sorted.

95
00:05:34,500 --> 00:05:35,220
So do nothing.

96
00:05:35,370 --> 00:05:39,750
We will simply better done otherwise, but only to do so.

97
00:05:39,750 --> 00:05:42,120
And B, I will call the function partition.

98
00:05:44,050 --> 00:05:45,640
So I will call the function partition.

99
00:05:45,670 --> 00:05:50,730
I will give Adi, I will give you starting next and I will give the ending.

100
00:05:52,660 --> 00:05:57,960
So this partition function, so I will write the code for this partition function.

101
00:05:58,390 --> 00:06:03,220
I will write the code for partition functions of partition function will return the next be OK, it

102
00:06:03,220 --> 00:06:04,360
will return the next B.

103
00:06:05,080 --> 00:06:09,270
So after getting B, what we will do, we need to apply quicksort on the left.

104
00:06:09,610 --> 00:06:10,810
We need to apply quixotically.

105
00:06:10,840 --> 00:06:11,090
Right.

106
00:06:11,860 --> 00:06:14,950
So let's call the quicksort function.

107
00:06:18,290 --> 00:06:25,400
Quicksort, so left-to-right starting next is a start and a Nexus B minus one and what is the right

108
00:06:25,400 --> 00:06:25,680
area?

109
00:06:26,450 --> 00:06:31,830
So Eddie starting next is B plus one and the next is end and that's all.

110
00:06:32,330 --> 00:06:36,170
So now what we need to do, we need to write the code for the partition function.

111
00:06:39,800 --> 00:06:46,310
So we need to write the code for this partition function, it will take at it will take new starting

112
00:06:46,310 --> 00:06:48,200
and it will take the next.

113
00:06:50,650 --> 00:06:57,580
So what I'm doing is so what I'm doing here, I'm calling the function partition, I'm calling the function

114
00:06:57,580 --> 00:06:59,140
partition, I'm giving at it start.

115
00:06:59,140 --> 00:07:02,790
And so I'm giving this area I'm giving the start.

116
00:07:02,860 --> 00:07:06,480
Next, I will give the index since that is are passed by reference.

117
00:07:06,700 --> 00:07:13,240
So it will rearrange my area, it will rearrange all the elements such that x the last element says

118
00:07:13,270 --> 00:07:15,520
that X is present at its correct position.

119
00:07:15,550 --> 00:07:19,030
All the elements will present at the left hand side will be smaller.

120
00:07:19,210 --> 00:07:21,740
All the elements on the right side will be greater.

121
00:07:22,090 --> 00:07:26,560
So this is the working of the partition function and it will return the index B so it will return the

122
00:07:26,560 --> 00:07:30,330
index of X, it will then be simple.

123
00:07:30,640 --> 00:07:34,170
So after getting B, what I'm doing, I'm calling quicksort on side.

124
00:07:35,470 --> 00:07:40,480
So A start and B minus one start and B minus, I'm calling partition on this area.

125
00:07:40,720 --> 00:07:46,740
So this is B plus one and so B plus one and OK, so that is the working of quicksort function.

126
00:07:46,990 --> 00:07:53,530
So the only thing remaining to do is so now the only thing remaining to do is basically write the code

127
00:07:53,530 --> 00:07:57,920
for partition function so it will write the code properly, then your algorithm will work.

128
00:07:58,420 --> 00:08:01,130
So I will not write the code for the partition function.

129
00:08:01,300 --> 00:08:06,250
You have to write the code it yourself, OK, you have to write the code for partition function yourself.

130
00:08:06,490 --> 00:08:09,300
So let me explain you the logic and then you will write the code.

131
00:08:10,330 --> 00:08:12,450
So basically there are many ways of writing the code.

132
00:08:13,090 --> 00:08:16,860
So basically there are many approaches to write the partition function.

133
00:08:17,170 --> 00:08:22,980
So let me discuss one approach so that the elements five.

134
00:08:22,990 --> 00:08:26,620
Let's make a two one, seven, three and four.

135
00:08:29,030 --> 00:08:34,900
So this is the area this is the starting next and this is the end, and it's simple.

136
00:08:35,990 --> 00:08:38,960
So this is the pivot element I told you so.

137
00:08:38,960 --> 00:08:40,450
The name of this element desperate.

138
00:08:41,900 --> 00:08:44,770
So in this alternate what the correct position for.

139
00:08:47,650 --> 00:08:55,060
In this auditorium, what will be the correct position of for so elemental, so we need to count, we

140
00:08:55,060 --> 00:09:00,760
need to count how many elements are smaller than elements, so count smaller, which will be you will

141
00:09:00,890 --> 00:09:04,290
read the area and we will count which elements are smaller than four.

142
00:09:04,660 --> 00:09:07,030
So two smaller ones smaller, three smaller.

143
00:09:07,040 --> 00:09:08,670
So these elements will come before.

144
00:09:09,160 --> 00:09:11,800
So basically three so countermelodies.

145
00:09:11,800 --> 00:09:12,740
Three, what do we do.

146
00:09:13,090 --> 00:09:13,720
So you will.

147
00:09:14,290 --> 00:09:14,650
You will.

148
00:09:14,650 --> 00:09:14,940
Right.

149
00:09:14,940 --> 00:09:17,130
Three plus the starting index.

150
00:09:17,140 --> 00:09:20,200
So this is the starting index which is currently zero.

151
00:09:20,770 --> 00:09:22,060
So zero blistery.

152
00:09:22,480 --> 00:09:25,960
So the right index for position four is basically three.

153
00:09:28,640 --> 00:09:35,190
Simple so that, you know, the correct position for four correct position for forestry, you know this.

154
00:09:35,210 --> 00:09:39,370
OK, first of all, you will find out three by rating over the area.

155
00:09:40,640 --> 00:09:45,830
So after finding out the three, you saw the value of start to zero for this area right now.

156
00:09:46,220 --> 00:09:47,690
So triple zero is three.

157
00:09:48,350 --> 00:09:52,880
And what you will do, you will strap so four and so zero one, two and three.

158
00:09:53,270 --> 00:09:54,730
So you will step forward with one.

159
00:09:56,300 --> 00:09:57,980
So when will we present that last?

160
00:09:59,990 --> 00:10:06,440
And here the elements are eight, five and two, and it had elements are seven and three.

161
00:10:07,070 --> 00:10:08,540
So first step is very clear.

162
00:10:08,540 --> 00:10:15,740
You will count how many elements are smaller by taking over the area and then you will find out the

163
00:10:15,740 --> 00:10:16,520
correct position.

164
00:10:16,760 --> 00:10:18,590
So the correct position is basically.

165
00:10:19,520 --> 00:10:20,690
So this is called pivot.

166
00:10:21,190 --> 00:10:26,160
OK, this is called pivot index, which you are returning, which you are returning.

167
00:10:26,210 --> 00:10:30,170
OK, so count smaller, plus the starting index.

168
00:10:30,590 --> 00:10:32,300
So you will return this value.

169
00:10:32,360 --> 00:10:33,860
OK, we will return this value.

170
00:10:34,370 --> 00:10:35,570
We will return in the next three.

171
00:10:37,260 --> 00:10:41,530
So after getting the next three, you will strap what is the value presented next to you?

172
00:10:41,550 --> 00:10:43,670
So when is president so swappable enfold?

173
00:10:43,680 --> 00:10:46,340
So when will the president at last and forward is presented?

174
00:10:46,650 --> 00:10:50,130
OK, so now what we will do, we will take two variables.

175
00:10:50,160 --> 00:10:51,620
So I will take one variable here.

176
00:10:51,660 --> 00:10:55,920
I so I is present at start and I will take one variable here.

177
00:10:56,400 --> 00:10:59,710
G G will represent that and simple.

178
00:11:00,120 --> 00:11:04,800
So now compare it with four so each would be present on the right hand side.

179
00:11:05,400 --> 00:11:06,400
So I will stop here.

180
00:11:06,720 --> 00:11:08,520
Now compare one with the four.

181
00:11:08,670 --> 00:11:10,770
So one should be present on the left hand side.

182
00:11:11,770 --> 00:11:17,200
So strap I enjoy, so I will strap Angie.

183
00:11:20,250 --> 00:11:28,100
I will slap it with one so no one is present here, it is present here, so I will move forward.

184
00:11:28,110 --> 00:11:30,720
So now I is present at this.

185
00:11:31,170 --> 00:11:33,990
So now this is a and G will move in this direction.

186
00:11:34,360 --> 00:11:36,870
So this is G now compare five.

187
00:11:37,110 --> 00:11:40,350
So five should be present on the right hand side completely.

188
00:11:40,560 --> 00:11:43,650
So they should be present on the left hand side, all four.

189
00:11:44,040 --> 00:11:45,110
So again we will swap.

190
00:11:45,720 --> 00:11:47,190
So again we will swap.

191
00:11:47,400 --> 00:11:50,280
So three will come here and five will come here.

192
00:11:51,190 --> 00:11:54,200
Simple, so Jay will move in this direction.

193
00:11:54,220 --> 00:11:57,620
So this is Gino, I will move in this direction.

194
00:11:57,640 --> 00:12:00,630
So this is I know so to do is correct.

195
00:12:00,640 --> 00:12:03,610
OK, to shoot the the left hand side and to the left hand side.

196
00:12:03,610 --> 00:12:05,100
So do not move forward.

197
00:12:05,500 --> 00:12:08,200
So this is your I checked seven so seven.

198
00:12:08,200 --> 00:12:09,070
Is that correct.

199
00:12:09,370 --> 00:12:10,830
So do nothing and move back.

200
00:12:11,110 --> 00:12:14,800
So we will reach here and you can see what is my final area.

201
00:12:15,430 --> 00:12:16,150
You will stop.

202
00:12:18,360 --> 00:12:24,120
So the final rule is basically one, then three, then two, then four, seven, five and eight.

203
00:12:24,690 --> 00:12:25,590
So now you can see.

204
00:12:27,170 --> 00:12:33,020
This is the building next to me, so I will read Dante and all the elements, less than four percent

205
00:12:33,020 --> 00:12:37,150
on the left hand side, all the elements good then for are present on the right hand side.

206
00:12:37,490 --> 00:12:40,280
So that is how you can write the code for partisan function.

207
00:12:40,550 --> 00:12:43,160
So this is approachable and you can write the code for this.

208
00:12:43,580 --> 00:12:47,360
There are many other approaches to write the partisan function, so this is one of them.

209
00:12:47,390 --> 00:12:50,930
OK, so now you can see the side is not sorted.

210
00:12:50,930 --> 00:12:52,130
This out is not sorted.

211
00:12:52,310 --> 00:12:55,810
So for sorting these two areas, I will call quicksort for the city.

212
00:12:56,240 --> 00:12:57,910
I will call quicksort for this area.

213
00:12:58,100 --> 00:13:02,310
So Bodanis will be sorted and our completed will become sorted.

214
00:13:02,330 --> 00:13:04,750
OK, so what is the stopping criteria.

215
00:13:04,970 --> 00:13:08,300
So stopping criteria is basically so I is moving in this direction.

216
00:13:08,630 --> 00:13:11,060
Just moving in this direction so.

217
00:13:11,970 --> 00:13:18,170
I should be basically less than Britannicus, so the next is basically three, so I should be less than

218
00:13:18,220 --> 00:13:21,720
be the next and should bigger than be with the next.

219
00:13:24,130 --> 00:13:26,290
So this will be your condition and develop.

220
00:13:28,550 --> 00:13:35,060
This is a condition develop and then you can compare you will compare the elements I would be to next

221
00:13:35,570 --> 00:13:40,970
with four and you will compare the elements with Ford and then you will swear you will do the slapping

222
00:13:40,970 --> 00:13:41,300
part.

223
00:13:41,340 --> 00:13:44,080
OK, so you can write the code for the partition function.

224
00:13:45,350 --> 00:13:46,800
So this is it from this video.

225
00:13:46,820 --> 00:13:48,110
I will see you in the next one.

226
00:13:48,260 --> 00:13:48,830
Thank you.