1
00:00:00,630 --> 00:00:01,620
Welcome back.

2
00:00:01,620 --> 00:00:04,980
So we have successfully returned the quicksort function.

3
00:00:05,010 --> 00:00:07,740
Now let's quickly walk through the code over here.

4
00:00:07,740 --> 00:00:11,070
Now primarily we'll be walking through these two parts of the code.

5
00:00:11,070 --> 00:00:13,110
One is the partition function that we wrote.

6
00:00:13,110 --> 00:00:14,640
And then the quicksort function.

7
00:00:14,640 --> 00:00:15,030
Right.

8
00:00:15,030 --> 00:00:20,430
And especially we are going to walk through only the quicksort function, where we recursively call

9
00:00:20,430 --> 00:00:22,710
quicksort on the lower sized subarray.

10
00:00:22,710 --> 00:00:27,180
And walking through the other function of quicksort is also pretty straightforward.

11
00:00:27,180 --> 00:00:30,570
So we will walk through only this function in this video.

12
00:00:30,570 --> 00:00:33,810
Now let's get started with walking through the partition function.

13
00:00:33,810 --> 00:00:37,800
Now let's say the input array is 31245.

14
00:00:37,800 --> 00:00:42,090
Now let's take this one case and see what happens.

15
00:00:42,090 --> 00:00:44,670
What would be returned at the end of the partition function.

16
00:00:44,670 --> 00:00:47,850
Now for this, let me write the indices of this array over here.

17
00:00:48,420 --> 00:00:53,550
Now initially middle is calculated right middle is math.floor start plus n by two.

18
00:00:53,580 --> 00:00:54,840
So zero plus four.

19
00:00:54,840 --> 00:00:57,930
That gives me four four divided by two gives me two.

20
00:00:57,960 --> 00:01:00,030
So middle is calculated as two.

21
00:01:00,030 --> 00:01:06,930
And using the math dot floor function, if it's say 2.5 or so, let's say there was one more element

22
00:01:06,930 --> 00:01:11,730
then zero plus five by two would be 2.5, and 2.5 will be changed to two.

23
00:01:11,760 --> 00:01:14,190
So we are just rounding it using math dot floor.

24
00:01:14,190 --> 00:01:16,920
So over here we find middle is equal to two.

25
00:01:16,950 --> 00:01:18,120
Now what do we do.

26
00:01:18,120 --> 00:01:20,550
We swap the start and the middle.

27
00:01:20,550 --> 00:01:21,480
So start over.

28
00:01:21,480 --> 00:01:22,470
Here is zero right.

29
00:01:22,470 --> 00:01:24,690
So this is the element at zero.

30
00:01:24,690 --> 00:01:26,460
And this is the element in middle right.

31
00:01:26,460 --> 00:01:27,060
These two.

32
00:01:27,090 --> 00:01:29,160
So we are going to swap these two over here.

33
00:01:29,160 --> 00:01:30,720
So that's what's happening over here.

34
00:01:30,720 --> 00:01:32,310
Now let's swap them.

35
00:01:33,440 --> 00:01:37,430
All right, so after swapping them we get two, one, three four, five.

36
00:01:37,430 --> 00:01:40,160
And we did this so that we take the pivot out.

37
00:01:40,160 --> 00:01:46,070
And then we just want to arrange the remaining elements in a particular order, where all the values

38
00:01:46,070 --> 00:01:50,300
less than the pivot is towards the left, and values greater than the pivot is towards the right.

39
00:01:50,300 --> 00:01:53,180
And then we will place the pivot at the right position.

40
00:01:53,180 --> 00:01:53,780
All right.

41
00:01:53,810 --> 00:01:57,080
Now over here pivot is equal to right start which is equal to two.

42
00:01:57,110 --> 00:02:00,050
So at the present moment pivot is equal to two.

43
00:02:00,530 --> 00:02:04,610
Now we said I is equal to start plus one and j is equal to end.

44
00:02:04,610 --> 00:02:07,550
So we get I over here and j over here.

45
00:02:07,550 --> 00:02:13,010
Now we keep doing this over here as long as I is less than equal to J.

46
00:02:13,010 --> 00:02:15,440
So in this case I is less than equal to j.

47
00:02:15,440 --> 00:02:16,280
This is true.

48
00:02:16,280 --> 00:02:19,730
So we check whether array of I is less than equal to pivot.

49
00:02:19,730 --> 00:02:23,780
So if the value over here is less than this then we move I ahead.

50
00:02:23,780 --> 00:02:25,190
So one is less than two.

51
00:02:25,220 --> 00:02:28,070
So we move I ahead and we come to three.

52
00:02:28,070 --> 00:02:29,960
Now three is not less than two.

53
00:02:29,990 --> 00:02:31,520
So I stops over here.

54
00:02:31,520 --> 00:02:32,690
Now what about J.

55
00:02:32,690 --> 00:02:39,080
If array of j is greater than pivot then we keep moving j in this direction right j minus minus over

56
00:02:39,080 --> 00:02:40,130
here five.

57
00:02:40,130 --> 00:02:41,420
Is it greater than two?

58
00:02:41,450 --> 00:02:42,710
Yes that's true four.

59
00:02:42,740 --> 00:02:43,670
Is it greater than two.

60
00:02:43,670 --> 00:02:43,970
Yes.

61
00:02:43,970 --> 00:02:47,570
So J comes over here again four is greater than two.

62
00:02:47,600 --> 00:02:49,700
So we move J is three greater than two.

63
00:02:49,730 --> 00:02:50,180
Yes.

64
00:02:50,180 --> 00:02:52,700
So it moves from here also.

65
00:02:52,700 --> 00:02:53,900
And then it comes to one.

66
00:02:53,900 --> 00:02:55,100
Is one greater than two.

67
00:02:55,100 --> 00:02:55,490
No.

68
00:02:55,490 --> 00:02:59,180
So J stops over here right J stops over here at this point.

69
00:02:59,180 --> 00:03:04,340
So we have reached over here and we got I and J in these respective positions.

70
00:03:04,340 --> 00:03:06,440
Now we check whether I is less than J.

71
00:03:06,440 --> 00:03:07,190
In this case.

72
00:03:07,190 --> 00:03:08,180
That's not true.

73
00:03:08,180 --> 00:03:08,390
Right.

74
00:03:08,390 --> 00:03:09,530
So this is not true.

75
00:03:09,530 --> 00:03:11,660
Therefore we come out of this right.

76
00:03:11,660 --> 00:03:12,680
We come out of this.

77
00:03:12,680 --> 00:03:15,800
And again I is not equal to not less than or equal to J.

78
00:03:15,800 --> 00:03:18,800
So we come out of this while loop and we are over here.

79
00:03:18,800 --> 00:03:19,040
Right.

80
00:03:19,040 --> 00:03:19,820
We are over here.

81
00:03:19,820 --> 00:03:23,240
And we swap the elements at start and j.

82
00:03:23,240 --> 00:03:26,870
So at J we have one and at start which is zero we have two.

83
00:03:26,900 --> 00:03:29,660
So these two elements are swapped over here right.

84
00:03:29,660 --> 00:03:33,560
So we get the array as 12345.

85
00:03:33,560 --> 00:03:34,130
Right.

86
00:03:34,130 --> 00:03:36,200
And let me just write the indices.

87
00:03:36,200 --> 00:03:37,850
What is the index that we are returning.

88
00:03:37,850 --> 00:03:39,440
We are returning j right.

89
00:03:39,440 --> 00:03:42,650
J over here is this element which is at index one.

90
00:03:42,650 --> 00:03:45,800
So we are returning the pivot index as one.

91
00:03:45,800 --> 00:03:47,960
So that's what's happening over here right.

92
00:03:47,960 --> 00:03:49,100
So what happened.

93
00:03:49,100 --> 00:03:50,480
We got this array.

94
00:03:50,480 --> 00:03:52,880
We found the middle element as the pivot.

95
00:03:52,880 --> 00:03:57,020
And we placed the middle element at the right position which is over here.

96
00:03:57,020 --> 00:03:58,730
And we are returning the pivot index.

97
00:03:58,730 --> 00:04:01,730
So this is what's happening in the partition function.

98
00:04:01,730 --> 00:04:04,310
Now it just so happens that the array is already sorted.

99
00:04:04,310 --> 00:04:06,710
But the the algorithm does not know.

100
00:04:06,710 --> 00:04:08,600
The computer does not know that it's already sorted.

101
00:04:08,600 --> 00:04:09,050
Right.

102
00:04:09,050 --> 00:04:09,680
All right.

103
00:04:09,680 --> 00:04:12,320
So we have walked through the partition function.

104
00:04:12,320 --> 00:04:16,460
Now let's proceed and look at what is happening in the quicksort function.

105
00:04:16,460 --> 00:04:19,550
Now let's say we start with 31245.

106
00:04:20,200 --> 00:04:21,430
Now start over.

107
00:04:21,430 --> 00:04:27,460
Here is three and end is five, which is over here and here right now we and then start is the index.

108
00:04:27,460 --> 00:04:31,480
So start is zero and end is 01234.

109
00:04:31,480 --> 00:04:33,370
So end is four which is the index.

110
00:04:33,370 --> 00:04:34,780
Now start is less than end.

111
00:04:34,780 --> 00:04:38,920
So we come inside and then we call the partition function which we already did.

112
00:04:38,920 --> 00:04:39,280
Right.

113
00:04:39,280 --> 00:04:43,930
And we saw that when we pass this into the partition function we get this array.

114
00:04:43,930 --> 00:04:46,390
This is the array at the present moment.

115
00:04:46,390 --> 00:04:48,700
And the pivot index is equal to one.

116
00:04:48,700 --> 00:04:52,780
So this element has been correctly fixed at its correct position.

117
00:04:52,780 --> 00:04:57,700
Now we come over here we have to find which sub array that is left or right.

118
00:04:57,700 --> 00:04:59,620
Which of these is the smaller one.

119
00:04:59,620 --> 00:05:03,310
And we have to recursively call quicksort on the smaller sub array.

120
00:05:03,310 --> 00:05:09,670
So we do pivot index minus start which is one -0 and end minus pivot index which is four minus one.

121
00:05:09,670 --> 00:05:11,200
So one and then three.

122
00:05:11,200 --> 00:05:12,580
So one is less than three.

123
00:05:12,580 --> 00:05:17,110
So we come over here and we call quicksort on the left side right.

124
00:05:17,110 --> 00:05:22,270
So over here we pass the array and start will be zero right and end.

125
00:05:22,270 --> 00:05:25,540
Also in this case will be zero which is pivot index minus one.

126
00:05:25,540 --> 00:05:26,980
So we pass this.

127
00:05:26,980 --> 00:05:31,630
And this element is fixed at its correct position which is here itself.

128
00:05:31,630 --> 00:05:33,250
And we come out of this call.

129
00:05:33,250 --> 00:05:33,520
Right.

130
00:05:33,520 --> 00:05:38,410
So then we come over here and start is set to pivot index plus one over here.

131
00:05:38,410 --> 00:05:40,930
So start becomes this value over here.

132
00:05:40,930 --> 00:05:43,270
And there is nothing in the call stack at this moment.

133
00:05:43,270 --> 00:05:43,690
Right.

134
00:05:43,690 --> 00:05:49,150
And then we come out of this and then we come over here which is the iterative part of the quicksort

135
00:05:49,150 --> 00:05:49,630
function.

136
00:05:49,630 --> 00:05:54,640
We check whether start is less than end, which is true at this point because start is over here and

137
00:05:54,640 --> 00:05:55,330
end is over here.

138
00:05:55,330 --> 00:05:55,930
End is over here.

139
00:05:55,930 --> 00:05:56,230
Right.

140
00:05:56,230 --> 00:05:57,250
So this is true.

141
00:05:57,250 --> 00:06:03,040
So we again call the partition function for this part of the array.

142
00:06:03,040 --> 00:06:03,310
Right.

143
00:06:03,310 --> 00:06:06,370
So we pass this as the start and this as the end.

144
00:06:06,370 --> 00:06:07,480
And the array is passed.

145
00:06:07,480 --> 00:06:10,690
And again we call the partition function which will do the same thing right.

146
00:06:10,690 --> 00:06:12,520
It will find the middle value.

147
00:06:12,520 --> 00:06:15,340
It will swap the middle value and the starting value.

148
00:06:15,340 --> 00:06:16,660
And then it will sort the others.

149
00:06:16,660 --> 00:06:20,740
And then it will put back the uh middle value at the correct position.

150
00:06:20,740 --> 00:06:24,460
So in this manner we have successfully done the quicksort.

151
00:06:24,460 --> 00:06:27,190
So we have walked through the code of the partition function.

152
00:06:27,190 --> 00:06:30,010
And we have walked through the code of the quicksort.

153
00:06:30,010 --> 00:06:30,520
Right.

154
00:06:30,520 --> 00:06:38,110
And we have seen that the time complexity of quicksort is equal to O of n log n.

155
00:06:38,110 --> 00:06:40,270
And that's the best and average case.

156
00:06:40,270 --> 00:06:42,970
And it is O of n square in the worst case.

157
00:06:42,970 --> 00:06:50,530
And to avoid the worst case, especially in cases where we are given a sorted array, we pick the middle

158
00:06:50,530 --> 00:06:51,970
element as the pivot.

159
00:06:51,970 --> 00:06:58,570
And we have seen that the space complexity of the quicksort is equal to O of log n, and to ensure this,

160
00:06:58,600 --> 00:07:05,860
we have written the code such that the quicksort is recursively called only on the lower sized array

161
00:07:05,860 --> 00:07:07,330
partition array subarray.