Welcome back.
So we have successfully returned the quicksort function.
Now let's quickly walk through the code over here.
Now primarily we'll be walking through these two parts of the code.
One is the partition function that we wrote.
And then the quicksort function.
Right.
And especially we are going to walk through only the quicksort function, where we recursively call
quicksort on the lower sized subarray.
And walking through the other function of quicksort is also pretty straightforward.
So we will walk through only this function in this video.
Now let's get started with walking through the partition function.
Now let's say the input array is 31245.
Now let's take this one case and see what happens.
What would be returned at the end of the partition function.
Now for this, let me write the indices of this array over here.
Now initially middle is calculated right middle is math.floor start plus n by two.
So zero plus four.
That gives me four four divided by two gives me two.
So middle is calculated as two.
And using the math dot floor function, if it's say 2.5 or so, let's say there was one more element
then zero plus five by two would be 2.5, and 2.5 will be changed to two.
So we are just rounding it using math dot floor.
So over here we find middle is equal to two.
Now what do we do.
We swap the start and the middle.
So start over.
Here is zero right.
So this is the element at zero.
And this is the element in middle right.
These two.
So we are going to swap these two over here.
So that's what's happening over here.
Now let's swap them.
All right, so after swapping them we get two, one, three four, five.
And we did this so that we take the pivot out.
And then we just want to arrange the remaining elements in a particular order, where all the values
less than the pivot is towards the left, and values greater than the pivot is towards the right.
And then we will place the pivot at the right position.
All right.
Now over here pivot is equal to right start which is equal to two.
So at the present moment pivot is equal to two.
Now we said I is equal to start plus one and j is equal to end.
So we get I over here and j over here.
Now we keep doing this over here as long as I is less than equal to J.
So in this case I is less than equal to j.
This is true.
So we check whether array of I is less than equal to pivot.
So if the value over here is less than this then we move I ahead.
So one is less than two.
So we move I ahead and we come to three.
Now three is not less than two.
So I stops over here.
Now what about J.
If array of j is greater than pivot then we keep moving j in this direction right j minus minus over
here five.
Is it greater than two?
Yes that's true four.
Is it greater than two.
Yes.
So J comes over here again four is greater than two.
So we move J is three greater than two.
Yes.
So it moves from here also.
And then it comes to one.
Is one greater than two.
No.
So J stops over here right J stops over here at this point.
So we have reached over here and we got I and J in these respective positions.
Now we check whether I is less than J.
In this case.
That's not true.
Right.
So this is not true.
Therefore we come out of this right.
We come out of this.
And again I is not equal to not less than or equal to J.
So we come out of this while loop and we are over here.
Right.
We are over here.
And we swap the elements at start and j.
So at J we have one and at start which is zero we have two.
So these two elements are swapped over here right.
So we get the array as 12345.
Right.
And let me just write the indices.
What is the index that we are returning.
We are returning j right.
J over here is this element which is at index one.
So we are returning the pivot index as one.
So that's what's happening over here right.
So what happened.
We got this array.
We found the middle element as the pivot.
And we placed the middle element at the right position which is over here.
And we are returning the pivot index.
So this is what's happening in the partition function.
Now it just so happens that the array is already sorted.
But the the algorithm does not know.
The computer does not know that it's already sorted.
Right.
All right.
So we have walked through the partition function.
Now let's proceed and look at what is happening in the quicksort function.
Now let's say we start with 31245.
Now start over.
Here is three and end is five, which is over here and here right now we and then start is the index.
So start is zero and end is 01234.
So end is four which is the index.
Now start is less than end.
So we come inside and then we call the partition function which we already did.
Right.
And we saw that when we pass this into the partition function we get this array.
This is the array at the present moment.
And the pivot index is equal to one.
So this element has been correctly fixed at its correct position.
Now we come over here we have to find which sub array that is left or right.
Which of these is the smaller one.
And we have to recursively call quicksort on the smaller sub array.
So we do pivot index minus start which is one -0 and end minus pivot index which is four minus one.
So one and then three.
So one is less than three.
So we come over here and we call quicksort on the left side right.
So over here we pass the array and start will be zero right and end.
Also in this case will be zero which is pivot index minus one.
So we pass this.
And this element is fixed at its correct position which is here itself.
And we come out of this call.
Right.
So then we come over here and start is set to pivot index plus one over here.
So start becomes this value over here.
And there is nothing in the call stack at this moment.
Right.
And then we come out of this and then we come over here which is the iterative part of the quicksort
function.
We check whether start is less than end, which is true at this point because start is over here and
end is over here.
End is over here.
Right.
So this is true.
So we again call the partition function for this part of the array.
Right.
So we pass this as the start and this as the end.
And the array is passed.
And again we call the partition function which will do the same thing right.
It will find the middle value.
It will swap the middle value and the starting value.
And then it will sort the others.
And then it will put back the uh middle value at the correct position.
So in this manner we have successfully done the quicksort.
So we have walked through the code of the partition function.
And we have walked through the code of the quicksort.
Right.
And we have seen that the time complexity of quicksort is equal to O of n log n.
And that's the best and average case.
And it is O of n square in the worst case.
And to avoid the worst case, especially in cases where we are given a sorted array, we pick the middle
element as the pivot.
And we have seen that the space complexity of the quicksort is equal to O of log n, and to ensure this,
we have written the code such that the quicksort is recursively called only on the lower sized array
partition array subarray.