1
00:00:01,620 --> 00:00:02,400
Hi, everyone.

2
00:00:02,430 --> 00:00:06,200
So in this video, what we will do, we will write the code for the partition function.

3
00:00:06,630 --> 00:00:09,690
So I told you there are many ways you can write the partition function.

4
00:00:09,690 --> 00:00:12,230
And I discussed one of the approaches with you guys.

5
00:00:12,570 --> 00:00:15,260
So I hope you guys can code that approach yourself.

6
00:00:15,450 --> 00:00:17,130
So I am discussing one more approach.

7
00:00:18,810 --> 00:00:22,450
So let's discuss one more approach for writing the partition function.

8
00:00:22,980 --> 00:00:23,760
So what do we do?

9
00:00:24,300 --> 00:00:30,780
So let's take one example, eight five, two, one, seven and three and this is four.

10
00:00:31,380 --> 00:00:33,240
So four is our world index.

11
00:00:33,330 --> 00:00:34,710
This is the START index.

12
00:00:35,070 --> 00:00:36,390
This is the end index.

13
00:00:36,660 --> 00:00:39,490
So four we call for as our pivot.

14
00:00:39,540 --> 00:00:41,010
So this is called pivot element.

15
00:00:41,490 --> 00:00:41,950
Simple.

16
00:00:42,270 --> 00:00:44,180
So what we will do, you will take two variables.

17
00:00:45,270 --> 00:00:49,680
So you will take very variables, which essentially are the starting position.

18
00:00:49,980 --> 00:00:53,340
You will take variables, which is initially at the starting position.

19
00:00:53,340 --> 00:00:56,310
Simple, then you will I strategy.

20
00:00:56,730 --> 00:00:58,170
So you will move forward.

21
00:00:58,170 --> 00:00:58,800
Basically you will.

22
00:00:58,800 --> 00:01:05,099
I totally agree with you till this point only did elementary so and minus one.

23
00:01:05,489 --> 00:01:06,390
This is right.

24
00:01:06,420 --> 00:01:08,520
So this is and minus one.

25
00:01:10,020 --> 00:01:15,060
So basically, you will write something like this, Jagels due will start from start, sorry, so Jay

26
00:01:15,810 --> 00:01:17,640
starting Elementalist is starting next.

27
00:01:18,830 --> 00:01:29,530
Gibbsville, Tildy, and minus one, not this element of it, not end and C++, so C they are two situations.

28
00:01:29,540 --> 00:01:30,800
There are two possible cases.

29
00:01:30,800 --> 00:01:34,270
Either the element will be greater than four or the element will be less than four.

30
00:01:34,790 --> 00:01:38,640
So if the element is basically greater, then four, then do nothing.

31
00:01:39,350 --> 00:01:42,640
So it is basically a good then for do nothing.

32
00:01:43,610 --> 00:01:44,620
It is good and four.

33
00:01:44,990 --> 00:01:48,140
So if element is good then four do nothing.

34
00:01:48,200 --> 00:01:51,810
So it is good then for doing nothing then just present here.

35
00:01:52,340 --> 00:01:54,150
So five is good then four do nothing.

36
00:01:54,680 --> 00:01:56,810
So now Gibbsville come here.

37
00:01:57,710 --> 00:01:59,670
So now two is basically less than four.

38
00:02:00,170 --> 00:02:02,740
So when you encounter the situation, what do you do.

39
00:02:02,990 --> 00:02:05,330
You will strap G with I.

40
00:02:07,310 --> 00:02:14,380
So you will slap and you will set by engine.

41
00:02:14,400 --> 00:02:16,340
So strap to an eight.

42
00:02:16,820 --> 00:02:21,860
So it will come here to will come here and what you will do.

43
00:02:21,860 --> 00:02:23,600
So you will move your way forward.

44
00:02:24,960 --> 00:02:30,990
So after slapping, you will do a placeless, simple and what is the condition for slapping the element

45
00:02:30,990 --> 00:02:33,770
is less than full and forward is what we would eliminate.

46
00:02:35,340 --> 00:02:38,020
So the next element is basically so present now.

47
00:02:38,100 --> 00:02:40,110
So one is also smaller than four.

48
00:02:40,710 --> 00:02:42,510
So again, you will do the slapping with the eye.

49
00:02:42,840 --> 00:02:47,430
So I is five now, so five will come here and one will come here.

50
00:02:48,870 --> 00:02:50,250
So I will move forward.

51
00:02:50,250 --> 00:02:54,130
So I is now present here and just now presented.

52
00:02:54,810 --> 00:02:55,860
So seven is a good then.

53
00:02:55,860 --> 00:02:58,370
Fourth element is a good then for doing nothing.

54
00:02:59,430 --> 00:03:00,710
So Jay will move forward.

55
00:03:01,530 --> 00:03:03,450
So three is basically less than four.

56
00:03:03,480 --> 00:03:04,360
So you will swap.

57
00:03:04,400 --> 00:03:07,610
So we will set by engy so strap three with it.

58
00:03:07,950 --> 00:03:13,200
So it will come here and three will come here and we will do eight plus plus.

59
00:03:14,580 --> 00:03:15,870
So finally what is it Eddie.

60
00:03:16,200 --> 00:03:21,040
So your G will reach at end and you will stop and your for loop will stop.

61
00:03:21,330 --> 00:03:28,800
So what is already matter is two, then one, then three, then five, then seven, then eight and then

62
00:03:28,800 --> 00:03:29,100
four.

63
00:03:31,080 --> 00:03:32,240
And we're designing.

64
00:03:32,250 --> 00:03:33,990
So just that this index.

65
00:03:34,200 --> 00:03:38,500
So you'll come out of the for loop and basically your eye is present.

66
00:03:39,060 --> 00:03:40,100
So where is I.

67
00:03:40,140 --> 00:03:42,080
So I is present at the next five.

68
00:03:42,090 --> 00:03:44,860
So I use this index element five.

69
00:03:46,350 --> 00:03:52,680
So now what do you need to do the last step after coming out of the loop, after coming out of the loop,

70
00:03:52,950 --> 00:03:54,330
you will step forward.

71
00:03:54,340 --> 00:03:56,700
You will have the pivot element with this element.

72
00:03:57,060 --> 00:03:59,370
So four will come here and five will come in.

73
00:04:01,200 --> 00:04:08,010
So what is your final area, your final days to one, three, then four, then seven, eight and five.

74
00:04:08,250 --> 00:04:11,100
So now you can see four, is that correct?

75
00:04:11,640 --> 00:04:15,710
All the elements less than for all the elements good than for simple.

76
00:04:16,860 --> 00:04:20,829
So at last, what do you need to do one more time so that you will step off?

77
00:04:21,660 --> 00:04:25,770
So this was a five and this was the last element in your friend.

78
00:04:27,240 --> 00:04:30,120
And then we need to return the spirit index.

79
00:04:30,120 --> 00:04:34,650
So it makes for what is next for I, I so I will return I.

80
00:04:37,590 --> 00:04:38,840
So this is the other way.

81
00:04:38,910 --> 00:04:42,080
OK, this is the approach to writing the petition function.

82
00:04:42,390 --> 00:04:47,700
So I think approach one was easy so you can write the code for the approach one I am writing the code

83
00:04:47,700 --> 00:04:50,330
for approach to, so let's write the code.

84
00:04:53,040 --> 00:04:54,750
So we need two variables.

85
00:04:54,750 --> 00:04:59,480
I think I will be at the starting position starting next.

86
00:04:59,530 --> 00:05:02,160
Initially, Jay will also be at the starting next.

87
00:05:06,030 --> 00:05:09,010
So now we will use a follow up to our over the area.

88
00:05:09,130 --> 00:05:15,000
So G so we will use Jane's inside the for loop.

89
00:05:17,670 --> 00:05:25,470
So Jay will start from starting Next G less than articles two and minus one and minus one angioplasties.

90
00:05:26,070 --> 00:05:27,650
And what is our favorite element?

91
00:05:27,840 --> 00:05:30,200
So the last element is called the pivot element.

92
00:05:30,720 --> 00:05:35,510
So our pivot is basically aof and simple.

93
00:05:36,180 --> 00:05:39,960
So if the element is less than the pivot element, we will trap.

94
00:05:39,990 --> 00:05:47,010
So if the current element, which is agea is less than the pivot element, I will do the swapping.

95
00:05:47,850 --> 00:05:50,880
So I will swap High-Energy.

96
00:05:53,240 --> 00:05:59,420
And I will move forward and will discuss that at the end, we need to set one more time.

97
00:05:59,840 --> 00:06:04,790
We need to satisfy and offend and we will return.

98
00:06:06,830 --> 00:06:10,550
So this is the thing that we discussed so you can see.

99
00:06:12,200 --> 00:06:18,630
At the end, we need to step at the end, we are stepping in tonight for the partition and so we are

100
00:06:18,680 --> 00:06:19,020
turning.

101
00:06:19,490 --> 00:06:21,850
And if the element is smaller, we are stepping.

102
00:06:22,220 --> 00:06:23,260
So we are stepping.

103
00:06:23,630 --> 00:06:30,230
So if it is less than pivot, so element is to then for do nothing, but it is less than the pivot element

104
00:06:30,230 --> 00:06:31,070
you need to strap.

105
00:06:31,550 --> 00:06:33,200
You need to step in to do a plus.

106
00:06:33,200 --> 00:06:37,220
Plus I'm doing a plus plus and the pivot element basically the last element.

107
00:06:37,490 --> 00:06:39,290
So the last element is the pivot element.

108
00:06:39,500 --> 00:06:42,920
And I told you where do we go to land minus one.

109
00:06:42,930 --> 00:06:44,810
So we will trade only on this.

110
00:06:47,740 --> 00:06:51,130
So let's test one more time how our function will work.

111
00:06:56,400 --> 00:07:04,530
So the elements let's take the previous one example, so eight five two one seven.

112
00:07:07,470 --> 00:07:08,340
Three and four.

113
00:07:11,180 --> 00:07:19,930
So what I'm doing here I is they're starting next, this is your day, this is your pivot is off.

114
00:07:19,970 --> 00:07:25,500
And so this is a pivot element for discoverability.

115
00:07:26,110 --> 00:07:27,540
It will go to the minus one.

116
00:07:27,560 --> 00:07:29,990
So Jay Z starting position, it will vote till three.

117
00:07:30,860 --> 00:07:31,900
It will go till three.

118
00:07:33,380 --> 00:07:36,940
So element is less than pivot and pivot.

119
00:07:36,950 --> 00:07:40,760
No element is less then pivot.

120
00:07:40,760 --> 00:07:43,130
So pivot is for the survivors less than for No.

121
00:07:45,830 --> 00:07:48,800
So, too, is less than four, if two is less than four.

122
00:07:50,450 --> 00:07:57,590
So I will do the swapping, so strap it will come here to will come here and I plus.

123
00:07:57,590 --> 00:07:57,950
Plus.

124
00:07:59,940 --> 00:08:07,290
OK, C++, now let's check for the next element, so the G will also move forward, we are doing C++,

125
00:08:07,290 --> 00:08:08,790
so G comes here.

126
00:08:09,690 --> 00:08:11,350
So one is less than four.

127
00:08:11,520 --> 00:08:12,740
So one is less than four.

128
00:08:12,750 --> 00:08:13,890
Again, do the swapping.

129
00:08:15,580 --> 00:08:21,040
So five will come here, I will move forward.

130
00:08:22,180 --> 00:08:28,540
I placeless, this is a and we will move forward plus plus.

131
00:08:30,490 --> 00:08:32,260
So when is good for do nothing?

132
00:08:32,559 --> 00:08:34,570
Seven is ago then for do nothing.

133
00:08:35,230 --> 00:08:36,280
So plus plus.

134
00:08:39,760 --> 00:08:48,280
So basically, elementary is less than four, so three is less than four do the slapping part, so three

135
00:08:48,280 --> 00:08:51,210
will come here and it will come here.

136
00:08:52,270 --> 00:08:53,380
So I plus plus.

137
00:08:55,700 --> 00:09:02,300
And they are doing C++, so G will come here and it will come out of the followup.

138
00:09:03,490 --> 00:09:09,910
So after coming out of the loop, I'm swiping I and the last element, so I'm stepping five and four,

139
00:09:10,420 --> 00:09:11,710
so so have these two elements.

140
00:09:13,230 --> 00:09:15,610
Four will come here and the five will come here.

141
00:09:16,800 --> 00:09:18,260
So finally, what is my area?

142
00:09:20,850 --> 00:09:28,410
So two, then one, then three, then four, then seven, then eight and then five, and I'm returning,

143
00:09:28,410 --> 00:09:30,470
I so I is present at this.

144
00:09:30,480 --> 00:09:33,930
So this is a which is zero one, two and three.

145
00:09:34,290 --> 00:09:40,000
So I will return the partition and I'm returning the partition and next and you can see so this is all

146
00:09:40,030 --> 00:09:44,800
elements less than four and all the elements were then four, then quicksort on the side.

147
00:09:45,180 --> 00:09:46,720
So this is the starting area.

148
00:09:46,740 --> 00:09:48,090
This is B minus one.

149
00:09:48,330 --> 00:09:50,910
This is B, this is B plus one.

150
00:09:51,060 --> 00:09:54,200
And this is and so I play quicksort on this area.

151
00:09:54,240 --> 00:09:55,470
I play quicksort on this area.

152
00:09:55,470 --> 00:09:56,850
Bodanis will get sorted.

153
00:09:57,870 --> 00:09:58,410
Simple.

154
00:09:58,680 --> 00:10:00,000
So that's how it is working.

155
00:10:00,150 --> 00:10:01,950
So I want to explain one more thing.

156
00:10:01,950 --> 00:10:03,360
That it is not necessary.

157
00:10:03,720 --> 00:10:07,500
It is not necessary that I take the last element as my favourite element.

158
00:10:07,980 --> 00:10:09,760
I can take any element, Desmonte.

159
00:10:09,850 --> 00:10:13,750
Belittlement, so you can also take the starting element as well.

160
00:10:14,130 --> 00:10:16,650
So instead of an element, we do what you can do.

161
00:10:16,890 --> 00:10:19,560
You can select the starting element as it pivot.

162
00:10:20,430 --> 00:10:23,130
And so what will happen, however, for look will change.

163
00:10:23,370 --> 00:10:28,580
So G will start, G will start from start plus one G will go till the last element.

164
00:10:28,620 --> 00:10:32,570
OK, so we can also pick the first element as a pivot element.

165
00:10:32,580 --> 00:10:36,180
It is not necessary to pick the last element as pivot.

166
00:10:36,210 --> 00:10:42,150
OK, so you can choose first element or you can choose the last element as a pivot element.

167
00:10:42,900 --> 00:10:43,400
Simple.

168
00:10:43,710 --> 00:10:45,620
So this is all about quicksort.

169
00:10:45,780 --> 00:10:47,370
This is the working of quicksort.

170
00:10:47,700 --> 00:10:49,260
So this is it from this video.

171
00:10:49,380 --> 00:10:50,730
I will see you in the next one.

172
00:10:50,910 --> 00:10:51,480
Thank you.