1
00:00:00,390 --> 00:00:08,880
So here we are back in our original solution that implemented quicksort, we are only making a tweak

2
00:00:08,880 --> 00:00:13,530
to the quicksort function in order to transform it into the quick select function.

3
00:00:14,380 --> 00:00:20,890
So I'm just going to modify this function, the first thing we need to do is switch quicksort to quick

4
00:00:20,890 --> 00:00:21,700
select.

5
00:00:22,150 --> 00:00:28,960
And what we also need to add is a fourth argument, which represents the index that we're looking for.

6
00:00:29,200 --> 00:00:31,660
So I'm just going to call it index to find.

7
00:00:32,690 --> 00:00:39,170
What we want to change is everything after we found the partition index, because, remember, the partitioning

8
00:00:39,170 --> 00:00:41,120
code is the exact same.

9
00:00:41,600 --> 00:00:44,590
The only difference now is what we do with the partition index.

10
00:00:45,170 --> 00:00:53,090
So the first thing we check is, does this partition index that we have equal the index that we're looking

11
00:00:53,090 --> 00:00:53,410
for?

12
00:00:53,630 --> 00:00:55,070
So our index to find.

13
00:00:56,250 --> 00:01:04,080
If this is equal, then we want to return from this quick select function, the number at that index,

14
00:01:04,080 --> 00:01:05,190
because we have our answer.

15
00:01:05,640 --> 00:01:09,840
So here we're just going to return array at partition index.

16
00:01:13,060 --> 00:01:17,830
If this is not the case and our partisan index does not equal the index fund, well, now we have to

17
00:01:17,830 --> 00:01:18,250
check.

18
00:01:18,730 --> 00:01:22,060
Is the partition index smolla?

19
00:01:23,960 --> 00:01:25,490
Then our index, the fine.

20
00:01:26,180 --> 00:01:32,030
So here we can say in our elusive statement that if the index to find.

21
00:01:34,280 --> 00:01:37,160
Is less than hour partition index.

22
00:01:39,710 --> 00:01:43,340
If it is, then what we're doing is we are returning.

23
00:01:44,460 --> 00:01:45,930
US calling quick select.

24
00:01:47,770 --> 00:01:50,990
On the subway right to the left of our partition index.

25
00:01:51,430 --> 00:01:54,030
So here, remember, we have to pass the original array.

26
00:01:54,490 --> 00:01:56,170
We're going to pass the same left.

27
00:01:56,650 --> 00:02:02,350
The right value is now going to be our partition index, minus one, if you remember.

28
00:02:03,100 --> 00:02:06,190
And then we also have to remember to pass our index to find.

29
00:02:08,970 --> 00:02:15,200
Else we know that if it's not equal and if it's not less, then then we know that our index to find

30
00:02:15,200 --> 00:02:18,810
in this block must now be greater than our partition index.

31
00:02:18,830 --> 00:02:20,510
So here we want to return.

32
00:02:21,540 --> 00:02:26,190
US performing our quick select search through the right side.

33
00:02:27,100 --> 00:02:35,980
Of the partition index, so it's Ray and now here the left is going to be the partition index plus one.

34
00:02:36,780 --> 00:02:42,710
And then our right stays the same and our index to find is still the one that we're looking for.

35
00:02:44,000 --> 00:02:49,760
And then we just close off our function, it's a little tight, but this is all it is, it's really

36
00:02:49,760 --> 00:02:54,410
just this additional if else, if else block that we added.

37
00:02:54,530 --> 00:03:01,090
But the logic is very straightforward and this will now give us a better runtime.

38
00:03:01,100 --> 00:03:04,060
So let's reanalyze the time and space complexity.

39
00:03:04,640 --> 00:03:09,720
So before we know that when we were running our algorithm, we also have to change this, actually.

40
00:03:09,830 --> 00:03:13,850
Let me just quickly make this adjustment here, because we're no longer calling quicksort.

41
00:03:13,880 --> 00:03:20,030
We're now calling Quick Select and we're also passing in the index to find.

42
00:03:22,750 --> 00:03:25,630
So let's look at this again, space and time complexity.

43
00:03:26,680 --> 00:03:33,970
When we think about the quick select time complexity before we saw that our time was, oh, of end,

44
00:03:33,970 --> 00:03:36,100
long end, what is it now?

45
00:03:36,760 --> 00:03:37,740
Well, let's think about it.

46
00:03:38,440 --> 00:03:41,370
What we're doing is we're finding some partisan element.

47
00:03:42,160 --> 00:03:48,490
This means that our time complexity still depends on our partition function and our partition function

48
00:03:48,580 --> 00:03:52,520
still scans through the entire array at least once.

49
00:03:53,320 --> 00:03:58,780
So this means that this function right here is of end the partition function.

50
00:03:59,970 --> 00:04:06,930
As far as the actual quick select function goes, though, let's think about what it is that it does

51
00:04:06,930 --> 00:04:13,170
every time once we get a partition, in a best case scenario, we've managed to eliminate half of the

52
00:04:13,170 --> 00:04:18,120
search space because let's say we're looking for the fifth element right here.

53
00:04:18,120 --> 00:04:19,500
We know that K equals two.

54
00:04:19,530 --> 00:04:22,020
So we know that we're looking for this position element.

55
00:04:22,560 --> 00:04:24,960
Let's say what we place is the three.

56
00:04:25,560 --> 00:04:29,100
Well, what we can say is we've eliminated half of the search space already.

57
00:04:29,610 --> 00:04:31,740
We're even so we can't get exactly half.

58
00:04:31,740 --> 00:04:38,820
But it's close enough to have if we've eliminated half of the search space, we only have an over two

59
00:04:38,820 --> 00:04:40,420
space left to search for.

60
00:04:41,160 --> 00:04:47,130
So this means that eventually what happens is that you can see time, complexity as PN plus and over

61
00:04:47,130 --> 00:04:53,910
to and then that, let's say best case, this space gets divided in half again, plus an over four and

62
00:04:53,910 --> 00:04:58,640
then an over eight and onwards and onwards until we eventually find our answer.

63
00:04:58,860 --> 00:05:05,310
And in the best case scenario, if this is the case, what this adds up to is o to to end.

64
00:05:05,700 --> 00:05:09,710
There's a mathematical proof for this that I'm going to show you inside of your resourcefulness.

65
00:05:09,720 --> 00:05:10,620
I'm going to link it for you.

66
00:05:11,280 --> 00:05:16,800
But once you have out of the two and you can drop the two and you're left with O of N, which is our

67
00:05:16,800 --> 00:05:24,240
best case of time complexity, the problem is that in the worst case time complexity, we end up with

68
00:05:24,240 --> 00:05:30,390
the exact same worse time complexity of quicksort because we still have the same problem of picking

69
00:05:30,390 --> 00:05:31,440
our partition poorly.

70
00:05:31,980 --> 00:05:37,080
Let's say every time we pick our partition, we end up picking the smallest value.

71
00:05:37,080 --> 00:05:43,410
And let's say that the value that we're looking for, for the largest is equal to the first largest

72
00:05:43,410 --> 00:05:43,740
value.

73
00:05:43,740 --> 00:05:45,660
Let's just say, for example, K equals one.

74
00:05:47,580 --> 00:05:53,900
Now, let's also assume that the array that we receive is sorted, but not in the order that we're expecting,

75
00:05:54,300 --> 00:05:57,780
let's say that it's sorted but from largest to smallest.

76
00:05:58,080 --> 00:06:04,410
And this is actually a perfectly valid array that we could receive, even though the question says unordered,

77
00:06:04,740 --> 00:06:09,420
this is not ordered in the order that we want, which is ascending order.

78
00:06:09,630 --> 00:06:11,850
This comes to us in descending order.

79
00:06:12,090 --> 00:06:18,420
And our array has no way of telling of this entire array is in descending order.

80
00:06:18,660 --> 00:06:22,810
But this actually poses the biggest problem for quicksort and quick select.

81
00:06:23,160 --> 00:06:26,190
This will give us our worst case and I'm going to show you why.

82
00:06:26,910 --> 00:06:32,940
So let's imagine that we pick our pivot as we always do, which is we choose the rightmost element.

83
00:06:33,360 --> 00:06:36,260
In this case, it's going to be the smallest element of one.

84
00:06:36,900 --> 00:06:43,590
What happens here is that we are going to see that we will sort using I and J.

85
00:06:44,640 --> 00:06:51,420
We're going to check across this entire array and it's going to say, OK, every value that we see is

86
00:06:51,420 --> 00:06:52,290
greater than one.

87
00:06:52,290 --> 00:06:53,730
So I never moves.

88
00:06:54,210 --> 00:06:58,380
By the time the GAO reaches PEH, we're going to swamp our pivot element into I.

89
00:06:58,530 --> 00:06:59,490
I've never moved.

90
00:06:59,940 --> 00:07:02,400
So the six on this one are going to swap positions.

91
00:07:05,120 --> 00:07:13,610
And then we're going to scan and do this part of the array, because we've sort it out as our pivot

92
00:07:13,610 --> 00:07:14,060
element.

93
00:07:14,390 --> 00:07:16,760
There's nothing on the left to search for or select through.

94
00:07:16,940 --> 00:07:18,120
There's only this side now.

95
00:07:18,800 --> 00:07:26,650
So once again, we are going to reinitialize J except this time this six is going to be our pivot element.

96
00:07:27,320 --> 00:07:31,300
What it's going to do is it's going to say, OK, it's five less than six.

97
00:07:31,310 --> 00:07:31,720
It is.

98
00:07:31,730 --> 00:07:35,090
So I enjoy swamp, but this position never changes.

99
00:07:35,820 --> 00:07:37,370
So then I and J move forward.

100
00:07:38,620 --> 00:07:44,680
And it's going to check again is for less than six, it is so I enjoy just positions four doesn't move.

101
00:07:45,680 --> 00:07:52,970
This repeats for three, this repeats for two, and this repeats until it hits six, and at this point

102
00:07:52,970 --> 00:07:55,870
I and Jay are both pointing out our pivot element.

103
00:07:56,090 --> 00:07:59,150
So, yes, our pivot swaps with I, but six has never moved.

104
00:07:59,610 --> 00:08:03,710
So now what happens is that we've once again reduced our search space.

105
00:08:04,840 --> 00:08:09,880
To the left side of our pivot element, because there's no elements on the right, and now you'll notice

106
00:08:09,880 --> 00:08:15,070
that this is going to repeat itself, the pivot is now going to be to and what happens is is going to

107
00:08:15,070 --> 00:08:17,710
do the same thing it did with the one it's going to place, the two and the five.

108
00:08:17,710 --> 00:08:19,000
In the end, they're going to swap.

109
00:08:22,420 --> 00:08:27,220
And then we're going to end up searching this space and then the five is going to stay in place while

110
00:08:27,220 --> 00:08:33,340
I and Jay searched for and three and then it's going to search this space and then it's going to search

111
00:08:33,340 --> 00:08:33,880
this space.

112
00:08:33,970 --> 00:08:37,890
And what you'll notice is that we've essentially scanned through the entire rate.

113
00:08:37,900 --> 00:08:44,050
And every single time we searched the entire remaining search space and we did it end times because

114
00:08:44,050 --> 00:08:45,920
we would do it for every single element.

115
00:08:46,240 --> 00:08:49,600
So this is the worst case with quicksort or quick select.

116
00:08:50,050 --> 00:08:56,810
What this means is that the worst time complexity that we can achieve is O of an squared.

117
00:08:57,430 --> 00:09:00,330
So this is actually the exact same worst case for quicksort.

118
00:09:01,150 --> 00:09:05,410
So now that we understand this, we know that time in its best case is of an.

119
00:09:06,510 --> 00:09:13,200
In its worst case, it's Olivant Square, when we present our time complexity for our solution, we

120
00:09:13,200 --> 00:09:18,450
have to remember that anything involving sports or even quick select in this case and square becomes

121
00:09:18,450 --> 00:09:20,240
our worst time complexity.

122
00:09:20,250 --> 00:09:21,270
So you have to mention it.

123
00:09:22,330 --> 00:09:23,500
So what about space?

124
00:09:24,250 --> 00:09:29,530
Well, here originally we knew that our space complexity in our previous solution using quicksort was

125
00:09:29,530 --> 00:09:37,810
O of log, and the reason why I was log in was because inside of our quicksort function, we had to

126
00:09:37,810 --> 00:09:38,940
quicksort running.

127
00:09:39,280 --> 00:09:43,600
You remember that after we found our partition index, we would call the quicksort function again,

128
00:09:43,600 --> 00:09:48,550
but we'd call it twice the first time on the left side and then the second time on the right side of

129
00:09:48,550 --> 00:09:49,300
our partition.

130
00:09:49,930 --> 00:09:57,070
So what happens now is that we are no longer doing that with the quicksort original function that we

131
00:09:57,070 --> 00:09:57,340
had.

132
00:09:57,610 --> 00:10:03,400
The second call of quicksort was waiting for the first call of quicksort to finish, which meant that

133
00:10:03,400 --> 00:10:05,890
our function is still on the call stack.

134
00:10:05,890 --> 00:10:12,610
As we know with the recursive functions, with quicksort like though we see that now what ends up happening

135
00:10:12,610 --> 00:10:21,280
is that we have the optimal situation for tail recursion because both of our base case is in fact all

136
00:10:21,280 --> 00:10:23,350
three of our base cases all return.

137
00:10:23,560 --> 00:10:30,460
The two base cases that end up calling quick select recursively only call quick select, which means

138
00:10:30,460 --> 00:10:36,100
that in a case with recursion, it will pop itself off the call stack, leaving just the original quick

139
00:10:36,100 --> 00:10:36,490
select.

140
00:10:36,970 --> 00:10:42,040
So this means that our call stack gets reduced to tail recursion, which is O of one.

141
00:10:43,130 --> 00:10:49,550
So here we see that we end up with a much better space complexity as well, and that's why this quick

142
00:10:49,550 --> 00:10:51,650
Selex solution is so good.

143
00:10:52,070 --> 00:10:57,530
So understand the quick select algorithm is specifically for solving the sub problem.

144
00:10:57,710 --> 00:11:03,920
What we're searching for, the smallest element inside of a unordered list.

145
00:11:04,610 --> 00:11:09,800
You can easily reframe Kieth smallest to create the largest with the technique that we already learned

146
00:11:09,800 --> 00:11:13,140
by doing the index to find equals array length minus K.

147
00:11:13,760 --> 00:11:19,880
So in both of those cases, if that ever shows up as a sub problem that you have to solve inside of

148
00:11:19,880 --> 00:11:25,520
an array question that's just set off a light in your head that lets you know that there might be a

149
00:11:25,520 --> 00:11:30,290
likelihood that quick select will help solve a large portion of the question.

150
00:11:30,530 --> 00:11:38,900
At the very least, it should contribute to one sub problem in terms of how to get this Kieth smallest

151
00:11:39,080 --> 00:11:42,840
or largest value in some kind of unordered list.

152
00:11:43,670 --> 00:11:47,000
So now that we understand that, let's move on to the next section.