In this lecture, we are going to start talking about QuickSort.
QuickSort is going to be another divide and conquer algorithm that is also going to use recursion.
So kind of similar to what we did for Merge sort in the previous lecture with this being the last sorting
algorithm that we are going to talk to, I am going to make this an assignment for you to try to implement
it on your own.
And by the end of this lecture you will have the confidence to attempt implementing it on your own.
And if you get stuck at any point, please feel free to ask some questions in the Q&A section and I
will get back to you pretty quickly on how to get unstuck and continue moving forward.
After you give an attempt on the assignment, the next lecture will be my solution to implementing in
QuickSort.
So let's start taking a look at what QuickSort is and how it works.
So the first thing I want to do is I want to create an array with some elements in there.
So we're going to have eight, five, one, two, seven, three and four.
And then here.
We need to have something called a pivot.
And there's many ways to come up with a pivot.
But for simplicity, I'm going to make the last element in our array the pivot.
So in this case, four is the pivot.
And then we're going to have two variables I and J that are going to iterate over the rest of these
elements and help us begin figuring out where this pivot goes.
Because after we're done with our first iteration, we want four to be in the correct spot in this array.
So we know that the array is going to be one, two, three, four, five, seven, eight.
So one, two, three, four, five, seven, eight.
So we want to get four into this spot here.
This is our goal through the first iteration, but also with four being here.
We also want to make sure that we have one, two and three in no particular order and this in these
three spots.
So when four is here, every element down here should be less than four.
It could be one, two, three, it could be three, two, one, it could be two, one, three, and
so on and so forth.
But then the same applies for up here.
We would want every element greater than four to already be in an index, greater than where our four
element is.
That way we can begin doing QuickSort on these elements as well.
So that's where the recursive approach comes into.
Once we have four and its correct spot, well we no longer have to worry about four, but now we can
call quicksort on these elements and then we'd be able to call quicksort on these elements.
So let's go ahead and run through this real quick and kind of see what this looks like.
So we will say that AI is here and J is here.
And what we're going to do is AI is going to look for numbers greater than four.
So I greater than four and J is going to look for numbers less than four.
Well, luckily, we actually don't have to look too hard to find that.
So we see we have an AI, which is a greater value than our pivot and we have J, which is a value less
than our pivot.
So what we're going to do here is we're actually going to swap these values.
So now we have 351, two, seven, eight and four.
So this is going to be our new array currently and now we're going to decrement J So J will go here
and now we're going to increase AI.
So remember, we're looking for values of AI greater than four and J less than four.
So AI is currently greater than four.
So we will leave that as j less than four.
It is not so we will go ahead and decrement it.
So now two is less than four.
So now we will swap these values.
So our new array is 3 to 1.
Five.
Seven.
Eight and four.
So our value.
Is now where the five is.
Now we're going to increment I by one.
Well, as I greater than four.
No.
So now we will cross that out and increment it by one.
Well now we see that I and J are at the exact same position, which now means that our pivot and we'll
just keep them circled that way.
We know it's our pivot.
Now we know our pivot actually goes here.
So now we swap this five with our pivot.
So now our index is three, two, one, four, seven, eight and five.
And now, if you remember at the beginning of this lecture, I said, when our four is in the correct
index, we want to make sure every value to the left of it is below four, and every value to the right
of it is above four.
And you can see that that is the outcome of our first iteration.
So now we know four is in the correct spot.
So now we would take our recursive approach and we would call QuickSort here
and we would call quicksort here.
And then we would keep doing that until the array is correctly sorted.
And that's exactly how QuickSort works.
So you can see that it's a pretty efficient algorithm.
So now what we want to do is we want to take a look at the pseudocode so that you can have a good idea
of what we need to do in order to implement this code in.
So we're going to have our QuickSort function.
And it's going to take a couple of parameters.
We'll take our our vector.
We're going to take low.
So the beginning of the Array's index and then the high, which is the ending array, excuse me, the
end index of the array.
So what we want to do in here is check if low is less than high, and then we will say pi and this pi
equals r partitioning
index.
So we want to do pi is equal to partition or partition and we want to pass in our array our low and
our high.
And then when we get our partitioning index, we want to call quicksort.
On the array, on the low, and then the partitioning index minus one.
And then we also want to call QuickSort.
So that would be the left side.
This is the left side.
Now we want to call it on the array partitioning index plus one and then the high.
So remember, this is going to be the left side and this will be the right side.
So left meaning over here, right meaning over here.
And then for in this case is our partitioning index.
And that is all we want to do for QuickSort.
So we'll just kind of wrap all this up right here.
That way we know that this is QuickSort, so we see that we have another function call in here called
called partition.
So now we need to create a partition, some partition pseudocode.
So we're going to have partition and partition is going to take our array, it's going to take our low
and it's going to take our high.
And then in here we're going to get our pivot.
So.
Pivot is equal to.
And then in our case, it was our high index.
So the last element, so we want to set it to array of high and then I is going to be equal to zero
in our case.
And then we will set J also to high minus one.
So now we want to implement in.
If J is less than we want to find a j, less than our pivot and an eye greater than our pivot, that
way we can start sorting them out.
So if J is less than pivot
and also AI is greater than pivot, then we want to swap i, I and J and then you want to increment
I and you also want to increment J.
And then once the index of I and J is the same so we can say something along the lines of if.
A ray of j is less than the pivot, meaning we have passed that midway point then we're going to want
to swap.
I plus one.
And our pivot.
That way.
This puts it in the middle.
And this will put pivot.
In.
Correct location.
Let's be a little bit more specific in the correct index.
Right.
So, again, we're checking to see if Jay is less than pivot and if eye is greater than pivot.
Then we want to swap I and J, and then we also want to increment until this condition is satisfied.
And then once a ray of j is less than the pivot.
Then you want to swap.
Let's actually let's redo this part.
Make it a little clearer, because if a red j is less than the pivot.
That means all of our values are are now correctly on the left side.
So at that point, we just want to swap.
J and pivot.
And there's other ways that you can swap here, because remember, at some point I and Jay are going
to intersect.
So that is when you want to swap.
So let's just make a note of that when I.
And J intersect.
Swap with.
Because then that'll put pivot in the correct spot and the correct index will be in correct.
Index.
And then that's all we have to do for our partitioning function.
So again, take some time to try to implement this on your own.
If you have any issues, please feel free to ask them in the Q&A section and I'll be more than happy
to provide you with some assistance.
And then once you have given it a go, please proceed to the next lecture while I will implement my
solution to this assignment.