So here we are back in our original solution that implemented quicksort, we are only making a tweak
to the quicksort function in order to transform it into the quick select function.
So I'm just going to modify this function, the first thing we need to do is switch quicksort to quick
select.
And what we also need to add is a fourth argument, which represents the index that we're looking for.
So I'm just going to call it index to find.
What we want to change is everything after we found the partition index, because, remember, the partitioning
code is the exact same.
The only difference now is what we do with the partition index.
So the first thing we check is, does this partition index that we have equal the index that we're looking
for?
So our index to find.
If this is equal, then we want to return from this quick select function, the number at that index,
because we have our answer.
So here we're just going to return array at partition index.
If this is not the case and our partisan index does not equal the index fund, well, now we have to
check.
Is the partition index smolla?
Then our index, the fine.
So here we can say in our elusive statement that if the index to find.
Is less than hour partition index.
If it is, then what we're doing is we are returning.
US calling quick select.
On the subway right to the left of our partition index.
So here, remember, we have to pass the original array.
We're going to pass the same left.
The right value is now going to be our partition index, minus one, if you remember.
And then we also have to remember to pass our index to find.
Else we know that if it's not equal and if it's not less, then then we know that our index to find
in this block must now be greater than our partition index.
So here we want to return.
US performing our quick select search through the right side.
Of the partition index, so it's Ray and now here the left is going to be the partition index plus one.
And then our right stays the same and our index to find is still the one that we're looking for.
And then we just close off our function, it's a little tight, but this is all it is, it's really
just this additional if else, if else block that we added.
But the logic is very straightforward and this will now give us a better runtime.
So let's reanalyze the time and space complexity.
So before we know that when we were running our algorithm, we also have to change this, actually.
Let me just quickly make this adjustment here, because we're no longer calling quicksort.
We're now calling Quick Select and we're also passing in the index to find.
So let's look at this again, space and time complexity.
When we think about the quick select time complexity before we saw that our time was, oh, of end,
long end, what is it now?
Well, let's think about it.
What we're doing is we're finding some partisan element.
This means that our time complexity still depends on our partition function and our partition function
still scans through the entire array at least once.
So this means that this function right here is of end the partition function.
As far as the actual quick select function goes, though, let's think about what it is that it does
every time once we get a partition, in a best case scenario, we've managed to eliminate half of the
search space because let's say we're looking for the fifth element right here.
We know that K equals two.
So we know that we're looking for this position element.
Let's say what we place is the three.
Well, what we can say is we've eliminated half of the search space already.
We're even so we can't get exactly half.
But it's close enough to have if we've eliminated half of the search space, we only have an over two
space left to search for.
So this means that eventually what happens is that you can see time, complexity as PN plus and over
to and then that, let's say best case, this space gets divided in half again, plus an over four and
then an over eight and onwards and onwards until we eventually find our answer.
And in the best case scenario, if this is the case, what this adds up to is o to to end.
There's a mathematical proof for this that I'm going to show you inside of your resourcefulness.
I'm going to link it for you.
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
best case of time complexity, the problem is that in the worst case time complexity, we end up with
the exact same worse time complexity of quicksort because we still have the same problem of picking
our partition poorly.
Let's say every time we pick our partition, we end up picking the smallest value.
And let's say that the value that we're looking for, for the largest is equal to the first largest
value.
Let's just say, for example, K equals one.
Now, let's also assume that the array that we receive is sorted, but not in the order that we're expecting,
let's say that it's sorted but from largest to smallest.
And this is actually a perfectly valid array that we could receive, even though the question says unordered,
this is not ordered in the order that we want, which is ascending order.
This comes to us in descending order.
And our array has no way of telling of this entire array is in descending order.
But this actually poses the biggest problem for quicksort and quick select.
This will give us our worst case and I'm going to show you why.
So let's imagine that we pick our pivot as we always do, which is we choose the rightmost element.
In this case, it's going to be the smallest element of one.
What happens here is that we are going to see that we will sort using I and J.
We're going to check across this entire array and it's going to say, OK, every value that we see is
greater than one.
So I never moves.
By the time the GAO reaches PEH, we're going to swamp our pivot element into I.
I've never moved.
So the six on this one are going to swap positions.
And then we're going to scan and do this part of the array, because we've sort it out as our pivot
element.
There's nothing on the left to search for or select through.
There's only this side now.
So once again, we are going to reinitialize J except this time this six is going to be our pivot element.
What it's going to do is it's going to say, OK, it's five less than six.
It is.
So I enjoy swamp, but this position never changes.
So then I and J move forward.
And it's going to check again is for less than six, it is so I enjoy just positions four doesn't move.
This repeats for three, this repeats for two, and this repeats until it hits six, and at this point
I and Jay are both pointing out our pivot element.
So, yes, our pivot swaps with I, but six has never moved.
So now what happens is that we've once again reduced our search space.
To the left side of our pivot element, because there's no elements on the right, and now you'll notice
that this is going to repeat itself, the pivot is now going to be to and what happens is is going to
do the same thing it did with the one it's going to place, the two and the five.
In the end, they're going to swap.
And then we're going to end up searching this space and then the five is going to stay in place while
I and Jay searched for and three and then it's going to search this space and then it's going to search
this space.
And what you'll notice is that we've essentially scanned through the entire rate.
And every single time we searched the entire remaining search space and we did it end times because
we would do it for every single element.
So this is the worst case with quicksort or quick select.
What this means is that the worst time complexity that we can achieve is O of an squared.
So this is actually the exact same worst case for quicksort.
So now that we understand this, we know that time in its best case is of an.
In its worst case, it's Olivant Square, when we present our time complexity for our solution, we
have to remember that anything involving sports or even quick select in this case and square becomes
our worst time complexity.
So you have to mention it.
So what about space?
Well, here originally we knew that our space complexity in our previous solution using quicksort was
O of log, and the reason why I was log in was because inside of our quicksort function, we had to
quicksort running.
You remember that after we found our partition index, we would call the quicksort function again,
but we'd call it twice the first time on the left side and then the second time on the right side of
our partition.
So what happens now is that we are no longer doing that with the quicksort original function that we
had.
The second call of quicksort was waiting for the first call of quicksort to finish, which meant that
our function is still on the call stack.
As we know with the recursive functions, with quicksort like though we see that now what ends up happening
is that we have the optimal situation for tail recursion because both of our base case is in fact all
three of our base cases all return.
The two base cases that end up calling quick select recursively only call quick select, which means
that in a case with recursion, it will pop itself off the call stack, leaving just the original quick
select.
So this means that our call stack gets reduced to tail recursion, which is O of one.
So here we see that we end up with a much better space complexity as well, and that's why this quick
Selex solution is so good.
So understand the quick select algorithm is specifically for solving the sub problem.
What we're searching for, the smallest element inside of a unordered list.
You can easily reframe Kieth smallest to create the largest with the technique that we already learned
by doing the index to find equals array length minus K.
So in both of those cases, if that ever shows up as a sub problem that you have to solve inside of
an array question that's just set off a light in your head that lets you know that there might be a
likelihood that quick select will help solve a large portion of the question.
At the very least, it should contribute to one sub problem in terms of how to get this Kieth smallest
or largest value in some kind of unordered list.
So now that we understand that, let's move on to the next section.