Hi everyone, let's do this problem.
You are given an array of integers.
Write a function that will take this array as input and return the sorted array using quicksort.
Now let's say the given array is 732516.
Now we have to use quicksort to sort this array, and the output should be 123567.
So this is the question.
And quicksort is a very famous algorithm.
Let's go ahead and understand this in a very good manner in this video.
Now the objectives of this video are three.
The first objective is to understand quicksort right.
We will try to see how the logic works so that we can go ahead and write the code of quicksort.
So that is point number one.
The second objective is that we will look at the time complexity of the quicksort.
And we will see how we can avoid the worst case.
Or we will look at recommendations to avoid the worst case of the time complexity.
And finally we will look at the space complexity, and we will make a few tweaks to the way we discuss
the quicksort to be able to optimize the space complexity.
So these are the three things that we will look at and understand in this video.
Now let's go ahead and start with the first point which is to understand the quicksort.
All right.
Now the quicksort is a divide and conquer algorithm.
With this we mean that it divides the given problem into subproblems.
And by solving the subproblems it solves the main problem.
So that's how quicksort works.
Now let me give you a little bit more of an idea of how quicksort works.
We will select one element of the given array and we will call it the pivot.
And then we will go ahead and find its correct position in the sorted array once the array is sorted.
So that's how quicksort works.
Now let's go ahead and understand this in a better manner.
Using an example for this I have 63195.
So let's say this is the array that we need to sort.
And let's go ahead and write the indices.
Now, once we sort this given array, it should look like this, right?
13569.
So over here this is sorted.
Now let's write the indices over here as well.
So we have 0123 and four.
Now we have discussed previously that how we go about in the quicksort is that we select a pivot.
So let's go ahead and do that.
And remember the pivot can be any element.
You can take any element of the given array as the pivot.
And what we try to do is we will find the correct index of where the pivot should be after the sorting
is done.
Now how we go about this is that we will have the pivot.
Let's say this is the pivot element and every element in the given array, which is less than the pivot
element, we will place it to its left.
All right.
So all elements smaller than the pivot would be placed to its left.
Now this part over here is not sorted.
So this is not sorted but we just place it over here.
All right.
And all the elements which are larger than the pivot, we will place it over here.
Again these two parts are not sorted.
But what happens over here is that the pivot will be in its correct place.
Let's take an example in this array over here which is given to us, which is to be sorted.
Let's say we take the element six, which is the first element as the pivot.
So we have six over here, which is the pivot.
Now let's go through the given array and place all the elements which are less than six to its left.
So we have three.
We have one and we have five.
So these three are less than six right.
So we place them to the left of six.
And then what is greater than six.
We have nine.
So we place that to the right of six.
So that's what we discussed over here right now.
Notice that once we have done this this part is not sorted.
Right.
And again this part in this case it's sorted.
But it may or may not be sorted if you had multiple elements let's say we have eight also.
So probably eight also would come over here.
So this part is also not sorted.
But when we look at the indices now let's write it zero, 123 and four.
Notice that the index of six is the correct index.
Once the array is sorted right.
Once the array is sorted, six should be at index three.
And by doing this operation we got six to its correct index.
So this is the basic principle behind which quicksort works.
All right.
Now let's take a bigger example.
And let's walk through the different steps because that's the best way that we can visualize how the
quicksort works.
So let's say this is the given array to us.
And we have to use quicksort.
And we have to sort it.
Now let's walk through one complete pass right.
Let's take one element as pivot.
And let's see all the steps that get into the quicksort so that we get that particular element in its
correct position.
So let's see that now over here let's take 14 as the pivot which is the first element.
Now later in the video we will discuss what is what is the recommended way to select the pivot to solve
some problems.
All right.
For now let's just take the first element as the pivot.
So 14 is the pivot.
And then we will have two pointers.
Let's call it I and J.
So I would be placed over here and j will be placed over here.
Right.
So I is the next element after the first element.
And J is over here.
Now we are going to look at these elements as we saw previously.
And what we want to achieve is that we want to move all the elements which are less than 14 to its left.
So let's write that over here.
We want 14 over here.
Anything less than 14 should be towards its left, and anything greater than 14 should be towards its
right.
So this is what we want to do, so that we get 14 at its correct position.
And 14 is the pivot over here.
So what we do is we have these two pointers over here.
And then we keep moving the pointer I towards the right till we get to an element which is greater than
the pivot.
Why is that.
So we want anything less than 14 to be on its left.
So if something is on its left then we just move forward.
Right.
But when we reach an element which is greater than 14 from this side, we stop because we want to change
it, right?
We want only elements which are less than 14 on its left.
So this is the left pointer.
And we want elements less than 14 on the left.
So the opposite greater the opposite of less is greater.
So when we move the left pointer and when we encounter an element which is the opposite of less which
is greater, we stop.
Similarly we have the I the j pointer over here, and we keep moving this towards the left in this direction,
right till we get to an element which is less than the pivot.
Again, over here in the right we want greater right.
We want items which are greater than 14.
So if we get something which is greater than 14 it's fine.
We just keep moving the J.
But the opposite of greater is less.
So till we get to an element which is opposite of greater, we keep moving the j.
All right.
So in this case initially itself we can see that I.
Is the.
The eye pointer is pointing to an element which is greater.
So we stop.
Eye stops over here.
Now let's say I was 11 over here.
Then we would have moved forward, right.
So 12 is also not greater.
So we are still moved forward.
And we would have stopped at 18.
But in this case the first element itself is greater than the pivot.
So the eye pointer stops over here.
And the j pointer.
The first element where the j pointer is there itself is less than the pivot.
So the j pointer also stops over here.
All right.
Now once we have identified these two positions what we do is we will swap these two again.
Notice what we are trying to do is we are getting all the items which are less than 14 towards the left,
and all the items which are greater than 14 towards the right.
And at the end we will place 14 in its correct position.
At the current moment, 14 is over here and we keep just doing these two parts and then we will move
14 to its correct position.
So that's what we are going to do.
All right.
So let let me just take make some space over here.
So we identified that we need to swap these two.
So let's do that now.
Once we swap these two nine comes over here and 22 comes over here.
Now I and J are over here.
All right again we keep doing this.
We move I in this direction till we encounter an element which is greater than 14.
So let's do that.
So I will reach over here.
Right?
So I will reach over here when I was over here.
That's not greater than 14.
So it moves forward and it comes to 18.
Now 18 is greater than 14.
So we stop over here.
Now when it comes to the j pointer we move it in this direction till we encounter an element which is
less than 14.
Again remember, the easy way to visualize this is that we want 14 over here.
Anything less than 14 should be on the left.
Anything greater than 14 should be on the right right.
So the opposite of less is greater.
So in the less part we keep moving till we get the opposite of this.
So we got something greater than 14.
We stop in the with respect to the j pointer the opposite of greater is less right.
So we move in the left direction in this direction till we get to something which is opposite of greater
which is less.
So let's do that.
So we keep moving.
And when we reach over here we have 1313 is less than 14.
So we stop right.
So again we have identified these two elements.
And what we do is we go ahead and swap these two.
All right.
So let's make some space over here.
We are trying to swap these two right.
So let's do that.
Now when we swap these two you can see we have 13 over here where earlier 18 was.
And then we have 18 over here.
Right.
We have swapped these two.
And the pointers are over here.
I is over here and J is over here again.
We keep moving the I till we encounter an element which is greater than 14.
Right.
Again remember we have 14.
Anything less than 14 should be on the left.
Anything greater than 14 should be on the right.
So opposite of less is greater.
So we keep moving I till we get to something greater than 14.
So when we do that we reach over here because 19 is greater than 14.
So I stops over here.
And with respect to J we keep moving it in this direction till we get to something which is less than
14.
Right.
So when we reach over here we find eight is less than 14.
So J stops over here.
Now we have identified these two again.
We swap right again we swap these two.
So let's write that over here.
We have to swap 19 and eight and the array becomes 14 nine 1213, eight, 11, 19, 18 and 22.
So these two have been swapped and eight is over here and 19 is over here.
All right.
So I is over here and J is over here.
Now we continue we move I till we get to something which is greater than 14.
Right.
Again remember 14.
We want less on the less left side and we want greater on the right.
So when it comes to the I which is the left pointer, move till the opposite of less which is greater
that is reached.
Right.
So we keep moving it and we will reach over here.
Right.
Because 11 is not greater than 14, 19 is greater than 14.
So I will stop over here.
Now when it comes to J we move till the opposite of greater which is less right.
So we move over here.
Now 11 is less than 14.
So J stops over here.
Now at this point we can see that till till now right till over here always I was less than J.
Right.
But over here you can see that I has become greater than J.
Right.
So when this happens, when this happens we stop.
All right.
So we stop moving the I and J pointers.
And at this point all we need to do is to get to this right.
We need to get to this where we have all the items less than 14 on the left.
And then we have 14 and all the items greater than 14.
We have it on the right.
So you can see that all these elements right.
All these elements are less than 14 and these are greater than 14.
Right.
So to achieve this all we need to do is we need to swap these two, this item and this item that is
the pivot.
And the last item which is less than um 14.
Right.
Which is 11.
In this case we need to just swap these two.
So let's do that.
Let's make some space over here.
Now if we swap these two you can see that our arrangement becomes this.
And at this point we just swap these two.
Right.
11 is over here.
And 14 came over here.
Now at this point you can see that all the items to the left of 14, that is these items are less than
14.
And all the items to the right of 14 are greater than 14.
Right.
So we have achieved less than 14 and then greater.
This is what we were trying to achieve and we have successfully achieved it right now.
Remember, 14 was the pivot and we were able to successfully place the pivot in its correct position.
So once the array is sorted, the pivot should be over here, right?
This is the correct place.
This is what we have seen previously.
Also when we took the element six and with a smaller array we had seen it.
Right.
So in this way we have placed the pivot in the correct position.
All right.
Let me make some space over here.
Just clean this up a bit.
All right?
Now, once we have achieved, once we have achieved this, then what we will do is we will recursively
call the quicksort.
All right.
So we have now two sides the left side and the right side.
And we will call the quicksort on these two sides recurse recursively.
So quicksort is a recursive algorithm.
So we will do that.
And by doing this we will be able to sort this array.
So this is the logic behind the quicksort.
So we have successfully learned the first point.
That is we have understood the quicksort.
What we do is we select a pivot and then we do some operations to find the correct position of the pivot,
so that everything less than the pivot is on its left right.
And then we have the pivot.
And anything greater than the pivot is on its right.
And then we recursively call the quicksort right on this part of the array and on this part of the array.
And we keep doing this.
So this is how quicksort works.
All right.
Now before we go ahead we need to make some tweaks right before we go ahead and code our solution.
Now first let's look at the time complexity.
Let's look at the best case and the worst case.
And then let's look at some recommendations to avoid the worst case.