- Quicksort.
I showed this image of a 1959 six pence
because once there was a six pence bet
between the inventor of quicksort,
Sir Tony Hoare and his employer at the time.
Tony was asked to implement a version of shell sort.
Shell short is an improved version of insertion sort.
And Tony said he knew a faster algorithm.
They made a bet.
And while you can guess what happened.
Now we have quicksort which is one
of the fastest sorting algorithms we have
for a wide variety of use cases.
Like merge sort,
quicksort is a divide-and-conquer algorithm.
And as you recall,
divide-and-conquer algorithms break down
a problem recursively and then combine the results
of subproblems to produce the final result.
To refresh our memory on recursion,
recursive functions call themselves.
And they require a base case.
And here the base case is vector of one element
which is already sorted.
And we've seen now many examples
of recursive functions in this class.
Merge sort in some previous videos,
Fibonacci,
factorial and Shamos' subsequence sum.
So what is quicksort?
Well let's look at some pseudocode.
What do you notice about this algorithm?
When we compare it with merge sort what's different?
Well,
let's walk through it.
Quicksort picks an element to divide the array.
We call that the pivot.
I think your book calls it the divider
but pivot is a more common term.
Move items less than the pivot to the left
of the pivot and move items greater than
or equal to the pivot to the right of the pivot.
And then we let p be the index
of the pivot and we start over again.
So the big difference here is that quicksort does the work
before making the recursive calls.
Whereas most of merge sorts work is emerging
after the elements have been split.
You can think of quicksort
as a series of successive refinements.
First we segregate elements into two partitions,
on one side values that are less than
the pivot and on the other values that
are greater than or equal to that of the pivot.
And then we make the recursive calls
on these two partitions,
on these two portions of our vector,
refining them further each time.
Now I know we visited visualgo.net
and I encourage you to do so please.
But I also like this animation.
This is from Wikipedia
and it shows now we're spanning the entire vector
and where the red bar indicates the pivot.
And we're putting all of the elements
that are smaller than the pivot to the left-hand side
and all of the elements that are larger than
or equal to that of the pivot on the right-hand side.
And you'll see as it goes
through the process that it successively refines the sort.
Let that go one more time.
Now we're working on the left half
or the left side I should say
left side of the left side and right side of the left side.
See how these,
the gray bar indicates the span that we're working with.
And that's quicksort.
So this is the basic idea,
but there are lots of implementation details to consider.
But let's look at more detailed pseudocode
and then work through some small problem instances.
Here's some more detailed pseudocode.
You'll see we have the quicksort function itself
and a separate function called by quicksort
to do the partitioning.
Quicksort calls partition
and partition returns and integer,
which is an index that indicates
how the vector has been partitioned.
That's p the pseudocode here.
Quicksort makes two recursive calls,
one passing in the portion of the vector
to the left of what's index by p
and another passing in the portion of the vector
that's to the right of p.
Most of the work is done in that partitioning function.
Here.
Let's see what happens now in that partition function.
If the partition function receives one element
then nothing has changed.
So let's look at a case where
the partition function receives two elements.
Here the elements are in order.
And here we choose the pivot to be the element
at the end of the vector.
We set i to the start and begin the loop.
Here so i equals start
and here's our loop for j from start to end.
So here,
the value at position j now five
is less than that of the pivot
so we swap the elements of positions i and j.
But i and j are the same.
So we're swapping five with itself and there's no change.
Now we increment i,
and we continue to loop.
Nine is not less than nine so we do nothing
and the loop terminates.
As a last step,
you'll see here we swap the elements of position
i and the end.
Again these are the same in this case
so we swap nine with nine.
And you see if we pass in a two element vector
with the elements in order
their order is preserved by the partition function.
Now let's look at a case where they're out of order.
We've initialized as before,
but now five is the pivot.
And we begin this loop for j from start to end.
Now nine is not less than five
so we don't swap and we don't increment i,
we just continue with that loop incrementing j.
So we move to the next j now five is not less than five.
So again we do nothing.
And now the last step calls for us to swap the elements
of position i and the ending position.
So if we swap,
now our elements are in the correct order.
So we've seen in the case of two element factors
that everything works as we'd want it to.
If the elements are out of order,
they're put into order.
And if the elements are already in order,
we leave them as is.
That might not be an earth shattering result
but let's see what happens when we look at
a little bigger example.
Here we have a vector of four elements.
Six, three, eight, and four.
Initializing as before we take the value
of the element at the end to be the pivot.
That's four,
we initialize i and j and we begin our four loop.
That's the four loop here.
And so for the first step of six is not less than four.
So we don't swap and we don't increment i,
we just move on to the next j.
Now here,
the value at the position j is less than that of the pivot.
And so we swap elements i and j and we increment i.
Now we move on to the next j.
Here eight is not less than four
and so we do nothing.
And we increment j and then
at the next step four is not less than four.
So again we do nothing.
So now we've finished this loop.
So we're going to exit that loop and then execute this swap.
So we swap the values of four and six
and now you'll notice that all the values
to the left of four are smaller than four.
And all the values to the right
of four are greater than or equal to four
and our partition is complete.
Now wait a minute,
you say these aren't completely sorted.
And you're right but let's see what happens next.
This value of i is returned to quicksort.
It'll be one in this case cause we're zero indexed.
And so now p equals one and we call quicksort again,
first on the portion of the vector
to the left of p that's this three here,
and then on the portion of the vector
to the right of p that's the six.
And the first recursive call we'll get
a single element three and that's already sorted
that's our base case so nothing changes.
And for the portion on the right, we've already seen that
if we pass a two element vector to the partition function
that the elements will be placed in the correct order.
So after those two calls have been made
our vector will be completely sorted.
So no matter how large the original input vector is
we'll always work our way down to small cases like this.
At each smaller partition,
we refine the order of the elements
and ultimately this produces a sorted vector.
Now,
quicksort has many different implementations
and performance varies significantly
with the implementation.
So what are these implementation issues
and why does performance vary?
Well how do we choose a pivot or the divider?
There are many schemes,
and we'll look at one of those later on.
Quicksort also doesn't do well on sorted lists
or when there are many repeated values
and quicksort can have
a worst-case complexity of O(n squared).
In the best cases,
with a good implementation,
quicksort is faster than merge sort.
And there's another algorithm
we'll see a little later called heap sort.
Quicksort also generally outperforms heap sort.
And sometimes it's implemented in a hybrid form
with insertion sort used when the sub-problems become small.
We'll also touch on that a little later in the video.
But let's see why quicksort
doesn't do well with sorted lists.
First let's take a step back and look at merge sort.
This is sort of a schematic of what goes on on merge sort
at least in the portion where we're dividing our vector
into single element sub vectors.
Here we have 16 elements,
and we divide these into individual elements
in only four steps.
So if we divide by half,
this is our input factor.
We divide by half, once, twice, three times, four times.
And notice we have 16 elements
and four divisions to get to one element sub vectors
it should come as no surprise
that log base two of 16 is four
and hence the maximum number of recursion depth is log (n).
That makes sense.
That's what we've seen in merge sort.
And in the case of quicksort
we divide elements with respect to some pivot element.
Now, if we were to choose the median value each time,
we'd have something similar to merge sort.
A recursion depth of roughly log (n)
Now, in many cases the depth may be a little more,
but not much more.
But what happens if we pass a sorted list to quicksort?
Well, things go wrong.
If we pass a sorted list to quicksort
and our algorithm always chooses,
say the left most element and the vector to serve as a pivot
then we'd have a recursion depths of n.
You see what's happening here.
We're going to partition everything
that's less than a to the left-hand side
and everything that's greater than or equal to a
to the right-hand side.
And so we partition only one element at each step.
And so to break our problem down here in
we have 16 elements here to break the problem
down into 16 individual single element factors,
we'd have a recursion depth of n not log (n) but n.
That's a big difference.
So in the worst case,
this would take O(n squared) time
because we have n elements to process
and a recursion depth of n.
N times n is n squared.
And if the problem instance were big enough
we could even overflow the call stack.
We could cause a crash.
So while picking one end or the other of our vector to serve
as a pivot might do well with unsorted data,
it can perform horribly with sorted or partly sorted data
or data that have a large number of repeated values.
Now notice that the same thing would happen
if we were to choose the right most element as the pivot
it's just that we would have,
we'd be splitting off elements
from this side rather than this side
but the result is the same,
o events squared and that's yucky.
So how do we choose a pivot?
Well, we've seen that we can choose the element
from one end or the other of the vector
and that works pretty well in most cases
and it's super easy in the implementation
but the downside is it can really perform horribly
if we pass a sorted already sorted list
or a partially sorted list to the algorithm,
it get bad.
And we could pick at random,
and that would work pretty well on most cases,
it's unlikely that we would choose the minimum
or the maximum value and run into these problems
with this long linear chain of recursion calls.
But then there's the overhead of choosing it random.
After you have to pick a random number each time
and that that gets costly.
So that's really not worth the trouble.
Then there's this technique
that's called median-of-three.
Median-of-three is simply if we have three values
we pick the one in the middle,
and that works pretty well in most cases
and it's not too costly.
And it really reduces the likelihood
of this worst case performance that we've seen.
The downside is we have a little overhead
we have to do three extra comparisons
and up to three extra swaps,
but that's a small price to pay
to avoid this O(n squared) performance.
So let's look at what median-of-three does.
Given some vector V and start and end indices,
we can calculate the middle.
We've done this before with a merge sort
where we take start plus end and divide by two.
And that's integer division.
So it'll truncate if we have an odd number.
And then if the element indexed by middle is less
than the element index by start we swap those two.
Then if the element index by end is less
than the element index by start we swap those two.
And if the element index by the middle is less
than the element index by the end we swap those two.
And then we let the pivot be the element that's now
at the end position.
Let's see how that works in practice.
We'll go back to our playing cards here
for this demonstration.
Here's median of three at work.
Let's say we have these cards,
and we're gonna run the median of three algorithm.
Well, the first thing we're going to do is we're
gonna compare the middle and start elements.
If the middle element is less
than the start element, then we swap.
So here we're going to swap six and 10.
That's one comparison and one swap.
Now we compare the element
at the start position with the one at the end.
If the one at the end is less
than the one at the start we swap.
So now we've made two comparisons and two swaps.
Finally, we compare the middle element
and the one at the end.
If the middle element is less than the one at the end
and we swap middle and end.
Here 10 is greater than six.
So we don't swap.
And so that's three comparisons and two swaps.
And the one left at the end position becomes our pivot.
So that's our pivot.
And you'll notice
that that's the median of four, 10, and six.
Now this doesn't guarantee that you'll find the median
of all the values of the cards,
just the median of the three that we chose.
But it is a quick way to make sure that you're
not picking the largest or smallest valued element.
So this simple technique reduces the likelihood
of choosing a really bad pivot and driving your performance
toward that OFN square worst case.
We'll include this in the next video
when we implement quicksort in C++ we'll see,
we'll compare our version that uses median
of three in a version that doesn't.
So what is quicksorts complexity?
Well, the partition function must process O(n) elements
and the recursion depth is typically O(log n),
hence we have O(n log n)
And that's the best case and the average case.
So what is quicksorts complexity?
The partition function must process O(n) elements.
And the recursion depth is typically O(log n),
hence we have O(n log n).
This is the best case and the average case.
The worst case is as we have seen
when we have a linear chain of partitions
and a recursion depth of O (n).
Again the partition function has to process O(n) elements
and so we have n times n that's n square.
However we can avoid worst case performance
in many situations by choosing our pivot well.
This is why many implementations
of quicksort use the median-of-three approach,
or something similar.
Now what about stability.
Is quicksort stable?
The answer here is maybe.
In its original form and in the form
I've shown you quicksort does not
preserve the relative border
of equal values in the input factor.
So what I've shown you is not stable.
It can however be implemented in a stable form
although this takes more space.
So if we're willing to use a little more working space
we can implement a stable version of quicksort.
But again, what I've shown you here
in this video is not stable.
We will demonstrate an implementation
of stable version in a later video.
Now let's get back to this hybridization
that I mentioned in an earlier slide.
It's not uncommon that quicksort is hybridized
with another algorithm,
typically insertion sort.
And you may have noticed that when we have
small vectors that we've seen swapping an element
with itself is not uncommon
and that's kind of wasteful.
And insertion sort performs well
with partially sorted lists.
So we're likely in small vectors
with quicksort to have partially sorted lists.
So we use insertion sort for vectors below a certain size,
say around 10 elements.
We use quicksort in the main for larger problem instances.
But when we get below a certain size
we switched to insertion sort.
And that gives quick sort of modest speed up in many cases.
Now let's go back to that comparison chart
that we've been looking at.
You can see here that quicksort has a time complexity
of O(n log n) that's what we've seen so far.
It has a space complexity of O(1).
So it's space complexity is less
than that of merge sort and it's not stable.
We'll see in a later video
how we can implement a stable version of quicksort
which also has O(n log n) complexity time complexity
but has O(n) space complexity.
And that one will be stable.
And just to remind you here's the curve
for O(n log n) and you see
that that grows much more slowly
than the curve for O (n squared).
So O(n log n) is much faster than O(n squared).
So in summary,
quicksort is a recursive divide-and-conquer algorithm.
It has O(n log n) time complexity.
In the unstable implementation that we've seen here.
We have O(1) space complexity
and in its original design,
it's not stable but if we willing
to increase the space complexity
to O(n) it can be implemented as a stable algorithm.
And we'll see that in a later video.
That's all for now.
Thanks.