1
00:00:01,270 --> 00:00:02,290
Hi everyone.

2
00:00:02,290 --> 00:00:07,600
In the previous video we have discussed these two implementations of the quicksort, right?

3
00:00:07,600 --> 00:00:14,470
We have implemented the quicksort in the way where we recursively call the quicksort only on the lower

4
00:00:14,470 --> 00:00:15,370
size subarray.

5
00:00:15,370 --> 00:00:17,260
That's this implementation over here.

6
00:00:17,260 --> 00:00:23,230
And we have also written the quicksort in the manner where we call it recursively on both the left side

7
00:00:23,230 --> 00:00:25,540
and the right side that is on both the subarrays.

8
00:00:25,540 --> 00:00:32,410
So in this video, let's try to understand the implication of these two implementations on the call

9
00:00:32,410 --> 00:00:32,890
stack.

10
00:00:32,890 --> 00:00:36,370
So over here I have an array 3124.

11
00:00:36,370 --> 00:00:44,140
Now I have written it in such a manner that when we pick the middle element the array is always, uh,

12
00:00:44,350 --> 00:00:47,080
divided in a way that we don't have a left.

13
00:00:47,080 --> 00:00:47,410
Right.

14
00:00:47,410 --> 00:00:49,570
So for example I have three one, two four.

15
00:00:49,570 --> 00:00:52,090
So initially the middle element will be one.

16
00:00:52,090 --> 00:00:56,680
It will be placed at its right position and then everything else will be to its right.

17
00:00:56,680 --> 00:00:58,060
So left will be empty right.

18
00:00:58,060 --> 00:01:02,500
So that's the worst case scenario where we discussed this implementation.

19
00:01:02,500 --> 00:01:02,770
Right.

20
00:01:02,770 --> 00:01:10,840
And to avoid the n o of n space in that case that's where we discussed that we could make this implementation

21
00:01:10,840 --> 00:01:14,650
and only recursively call quicksort on the lower size subarray.

22
00:01:14,650 --> 00:01:18,550
So to get the worst case I have engineered this array over here.

23
00:01:18,550 --> 00:01:19,090
Right.

24
00:01:19,090 --> 00:01:21,910
Especially I have written 3213124.

25
00:01:21,910 --> 00:01:25,480
Because in the partition function we always pick the middle value.

26
00:01:25,480 --> 00:01:25,870
Right.

27
00:01:25,870 --> 00:01:32,710
So if if the partition function was written so that we always pick the left most value, then if we

28
00:01:32,710 --> 00:01:36,790
have the input one, two, three, four, then that would be the worst case, right?

29
00:01:36,790 --> 00:01:38,680
We always pick the left one.

30
00:01:38,680 --> 00:01:41,380
So the left side of that sub array is empty.

31
00:01:41,410 --> 00:01:44,860
Then we recursively call it on two three, four and it goes on like that.

32
00:01:44,860 --> 00:01:47,440
So that was the case where we got a depth of n.

33
00:01:47,440 --> 00:01:49,570
So I just want to simulate that over here.

34
00:01:49,570 --> 00:01:51,340
But I don't want to change this code.

35
00:01:51,340 --> 00:01:53,500
I want to keep it over here as it is.

36
00:01:53,500 --> 00:01:56,770
So let's look at this input array 3124.

37
00:01:56,770 --> 00:01:58,300
And let's look at the call stack.

38
00:01:58,300 --> 00:02:01,870
When we run this over here we have the debugger.

39
00:02:01,870 --> 00:02:03,790
So let me just write debugger over here.

40
00:02:03,790 --> 00:02:08,470
Or you can also rather create a breakpoint over here by clicking this.

41
00:02:08,470 --> 00:02:10,450
So now the code will stop over here.

42
00:02:10,450 --> 00:02:14,110
And then we can just press next next and look at the call stack.

43
00:02:14,110 --> 00:02:14,440
Right.

44
00:02:14,440 --> 00:02:18,070
So that's what we are trying to do over here I'm not walking through the code over here.

45
00:02:18,070 --> 00:02:19,570
We'll do that separately.

46
00:02:19,600 --> 00:02:23,620
We are just trying to look at the call stack between these two implementations.

47
00:02:23,620 --> 00:02:24,760
So let's run it.

48
00:02:25,540 --> 00:02:28,210
All right, so we have caught the debugger.

49
00:02:28,210 --> 00:02:28,960
We are over here.

50
00:02:28,960 --> 00:02:33,160
Now let's look at the call stack and keep track of it as we proceed.

51
00:02:33,160 --> 00:02:36,760
And again let me just increase this so that we can see this properly.

52
00:02:37,830 --> 00:02:38,400
All right.

53
00:02:38,400 --> 00:02:41,850
So we have one quicksort in the call stack.

54
00:02:43,230 --> 00:02:48,420
And whenever I come to partition, I'm just going to come out of the function quickly, right?

55
00:02:48,420 --> 00:02:49,980
So that we don't waste too much time.

56
00:02:49,980 --> 00:02:51,810
So we have quicksort only one time.

57
00:02:51,810 --> 00:02:53,730
Now we have it two times.

58
00:02:55,490 --> 00:02:56,150
All right.

59
00:02:56,390 --> 00:02:59,930
And one is popped off and we have again quicksort over here.

60
00:03:01,820 --> 00:03:03,530
We are in the partition function.

61
00:03:03,530 --> 00:03:04,730
I come out of it.

62
00:03:04,760 --> 00:03:06,920
Now we have two on the call stack.

63
00:03:06,920 --> 00:03:09,410
Now we have three quicksort's in the call stack.

64
00:03:09,410 --> 00:03:10,010
Right.

65
00:03:12,920 --> 00:03:13,220
All right.

66
00:03:13,220 --> 00:03:15,920
One is popped off again, one is added.

67
00:03:17,080 --> 00:03:19,510
We are in the partition function, so I come out of it.

68
00:03:19,540 --> 00:03:21,430
Now we have three quicksort's.

69
00:03:22,220 --> 00:03:27,110
Now you can see we have four quicksort's right in the call stack.

70
00:03:27,110 --> 00:03:30,140
Now the size of the input was only four.

71
00:03:30,140 --> 00:03:30,500
Right.

72
00:03:30,500 --> 00:03:36,290
So we have we have discussed that in the case where we call recursively on both the sides, the worst

73
00:03:36,440 --> 00:03:39,260
case complexity is O of n right.

74
00:03:39,260 --> 00:03:42,320
The worst case complexity is O of n.

75
00:03:42,320 --> 00:03:48,200
And we see that over here because we have four quicksort's in the call stack.

76
00:03:48,200 --> 00:03:51,770
So the space complexity in this case is O of n.

77
00:03:51,770 --> 00:03:57,860
Now by doing this implementation where for the same input array, by doing this implementation where

78
00:03:57,860 --> 00:04:04,310
we recursively call only on the lower size subarray, we saw that we can reduce the space complexity

79
00:04:04,310 --> 00:04:07,160
to O of log n right o of.

80
00:04:08,670 --> 00:04:09,660
Login.

81
00:04:10,490 --> 00:04:11,030
Right.

82
00:04:12,330 --> 00:04:14,430
Now in this case n is equal to four.

83
00:04:14,430 --> 00:04:18,210
So log n is equal to what's log n log four.

84
00:04:18,240 --> 00:04:18,810
Right.

85
00:04:18,810 --> 00:04:20,520
So log four is equal to two.

86
00:04:20,550 --> 00:04:23,160
So over here n is equal to four.

87
00:04:23,790 --> 00:04:28,080
So that's what we have seen over here we have quicksort four times in the call stack.

88
00:04:28,080 --> 00:04:29,670
So we have seen this case.

89
00:04:29,670 --> 00:04:34,440
Now let's try to implement let's try to try to run this case this quicksort over here.

90
00:04:34,440 --> 00:04:39,660
This implementation where we recursively call the function the quicksort function only on the lower

91
00:04:39,660 --> 00:04:40,710
sized subarray.

92
00:04:40,710 --> 00:04:45,390
And we should be getting a call stack depth of only two, which is log n.

93
00:04:45,390 --> 00:04:49,110
And that's the improvement that we are looking for by doing this implementation.

94
00:04:49,110 --> 00:04:49,440
All right.

95
00:04:49,440 --> 00:04:51,060
So let's just come out of this.

96
00:04:59,290 --> 00:05:00,910
All right, so we are out of it.

97
00:05:04,070 --> 00:05:07,880
Now what we will do is let's comment this quicksort over here.

98
00:05:11,680 --> 00:05:12,880
And let's.

99
00:05:14,510 --> 00:05:16,610
Remove the comments over here.

100
00:05:16,640 --> 00:05:17,090
Okay.

101
00:05:17,090 --> 00:05:18,830
So we will call this quicksort.

102
00:05:18,830 --> 00:05:21,500
And again we will look at the call stack.

103
00:05:21,860 --> 00:05:27,950
And our expectation is that the depth the maximum depth should only be log n which is equal to two.

104
00:05:27,980 --> 00:05:32,390
So let's run our code and take a look at the call stack in this case.

105
00:05:34,330 --> 00:05:36,700
So we are at the debugger now.

106
00:05:39,370 --> 00:05:42,310
And we call quicksort one time.

107
00:05:44,590 --> 00:05:47,200
We go to the partition function and I come out of it.

108
00:05:47,200 --> 00:05:51,190
So we have only one quicksort in the whole stack at this point.

109
00:05:51,670 --> 00:05:54,370
Now we have two quicksort's in the call stack.

110
00:05:59,120 --> 00:06:00,860
And one is popped out.

111
00:06:03,540 --> 00:06:05,520
Again, we are in the partition function.

112
00:06:05,520 --> 00:06:06,930
We come out of it.

113
00:06:08,180 --> 00:06:11,900
We have only two quick thoughts at this time in the call stack.

114
00:06:16,750 --> 00:06:19,030
Wherein the partition function, I come out of it.

115
00:06:19,030 --> 00:06:20,650
You can see that we've popped out one.

116
00:06:20,650 --> 00:06:26,320
We have only one quicksort in the call stack now, and we have now two quicksort in the call stack.

117
00:06:30,610 --> 00:06:32,260
And that's the end.

118
00:06:32,290 --> 00:06:38,410
See, the array is sorted and you can see that at any point we only had two quick sorts in the call

119
00:06:38,410 --> 00:06:38,680
stack.

120
00:06:38,680 --> 00:06:38,980
Right.

121
00:06:38,980 --> 00:06:41,980
So that's why this implementation is much better.

122
00:06:41,980 --> 00:06:47,920
And we have achieved a space complexity of O of log n instead of O of n.