0:00

The goal of this video is to provide more details about the implementation of the

QuickSort algorithm and, in particular, if you're ever going to drill down on the

key Partition subroutine, just let me remind you what the job of the Partition

subroutine is in the context of sorting an array. So recall that key idea in QuickSort

is to partition the input array around a pivot element. So this has two steps.

First, you somehow choose a pivot element, and in this video, we're not going to worry

about how you choose the pivot element. For concreteness, you might just want to

think about you pick the first element in the array to serve as

your pivot. So in this example array, the first element happens to be 3, so we

can choose 3 as the pivot element. Now, there's a key rearrangement step. So

you rearrange the array so that it has the following properties. Any entries

that are to the left of the pivot element should be less than the pivot element.

Whereas any entries, which are to the right of the pivot element, should be

greater than the pivot element. So, for example, in this, version of, the second

version of the array, we see to the left of the 3 is the 2 and the 1.

They're in reverse order, but that's okay. Both the 2 and the 1 are to the left

of the 3, and they're both less than 3. And the five elements to the right

of the 3, they're jumbled up, but they're all bigger than the pivot element.

So, this is a legitimate rearrangement that satisfies the partitioning property.

And, again, recall that this definitely makes partial progress toward having a

sorted array. The pivot element winds up in its rightful position. It winds up

where it's supposed to be in the final sorted array, to the right of everything

less than it, to the left of everything bigger than it. Moreover, we've correctly

bucketed the other N-1 elements to the left and to the right of the pivot

according to where they should wind up in the final sorted array. So that's the job,

that the Partition subroutine is responsible for. Now what's cool is we'll

be able to implement this Partition subroutine in linear time. Even better,

we'll be able to implement it so that all it does, really, is swaps in the array.

That is, it works in-place. It needs no additional, essentially constant

additional memory, to rearrange the array according to those properties. And then,

as we saw on the high-level description of the QuickSort algorithm, what partitioning

does is, it enables a divide-and-conquer approach. It reduces the problem size.

After you've partitioned the array around the pivot, all you gotta do is recurse on

the left side, recurse on the right side, and you're done. So, what I owe you is

this implementation. How do you actually satisfy the partitioning property, stuff

to the left of the pivot is smaller than it, stuff to the right of the pivot is

bigger than it, in linear time, and in- place. Well, first, let's observe that, if

we didn't care about the in-place requirement, if we were happy to just

allocate a second array and copy stuff over, it would actually be pretty easy to

implement a Partition subroutine in linear time. That is, using O(N) extra

memory, it's easy to partition around a pivot element in O(N) time. And as

usual, you know, probably I should be more precise and write theta of N, are used in cases that would

be the more accurate stronger statement, but I'm going to be sloppy and I'm just

going to write the weaker but still correct statement, using Big-Oh, okay? So

O(N) time using linear extra memory. So how would you do this? Well let

me just sort of illustrate by example. I think you'll get the idea. So let's go

back to our running example of an input array. Well, if we're allowed to use

linear extra space, we can just preallocate another array of length N.

3:18

Then we can just do a simple scan through the input array, bucketing elements

according to whether they are bigger than or less than the pivot. And, so for

example, we can fill in the additional array both from the left and the right,

using elements that are less than or bigger than the pivot respectively. So for

example we start with the 8, we know that the 8 is bigger than the pivot,

so you put that at the end of the output array. Then we get to the 2. The 2 is

less than the pivot, so that should go on the left hand side of the output array.

When you get to the 5, it should go on the right-hand side, and the 1 should go on

the left-hand side, and so on. When we complete our scan through the input array,

there'll be one hole left, and that's exactly where the pivot belongs, to the

right of everything less than it, to the left of everything bigger than it. So,

what's really interesting, then, is to have an implementation of Partition, which

is not merely linear time, but also uses essentially no additional space. It

doesn't re-sort to this cop-out of pre-allocating an extra array of

length N. So, let's turn to how that works. First, starting at a high-level,

then filling in the details. So I'm gonna describe the Partition subroutine

only for the case where the pivot is in fact the first element. But really this is

without loss of generality. If, instead, you want to use some pivot from the middle

of the array, you can just have a preprocessing step that swaps the first

element of the array with the given pivot, and then run the subroutine that I'm about

to describe, okay. So with constant time preprocessing, the case of a general pivot

reduces to the case of when the pivot is the first element. So here's the high-level

idea, and it's very cool. The idea is, we're gonna be able to able to get

away with just a single linear scan of the input array. So in any given moment in

this scan, there's just gonna be a single for-Loop, we'll be keeping track of both

the part of the array we've looked at so far, and the part that we haven't looked at

so far. So there's gonna be two groups, what we've seen, what we haven't seen.

Then within the group we've seen, we're gonna have definitely split further, according

to the elements that are less than the pivot and those that are bigger than the

pivot. So we're gonna leave the pivot element just hanging out in the first

element of the array until the very end of the algorithm, when we correct its

position with a swap. And at any given snapshot of this algorithm, we will have

some stuff that we've already looked at, and some stuff that we haven't yet looked

at in our linear scan. Of course, we have no idea what's up with the elements that

we haven't looked at yet, who knows what they are, and whether they're bigger

or less than the pivot. But, we're gonna implement the algorithm, so, among the

stuff that we've already seen, it will be partitioned, in the sense that all

elements less than the pivot come first, all elements bigger than the pivot come

last. And, as usual, we don't care about the relative order, amongst elements less

than the pivot, or amongst elements bigger than the pivot. So summarizing, we do a

single scan through the input array. And the trick will be to maintain the

following invariant throughout the linear scan. But basically, everything we have

looked at the input array is partitioned. Everything less than the pivot comes

before everything bigger than the pivot. And, we wanna maintain that invariant,

doing only constant work, and no additional storage, with each step of our

linear scan. So, here's what I'm gonna do next. I'm

gonna go through an example, and execute the Partition subroutine on a concrete

array, the same input array we've been using as an example, thus far. Now, maybe

it seems weird to give an example before I've actually given you the algorithm,

before I've given you the code. But, doing it this way, I think you'll see the gist

of what's going on in the example, and then when I present the code, it'll be

very clear what's going on. Whereas, if I presented the code first, it may seem a

little opaque when I first show you the algorithm. So, let's start with an

example. Throughout the example, we wanna keep in mind the high-level picture that

we discussed in the previous slide. The goal is that, at any time in the Partition

subroutine, we've got the pivot hanging out in the first entry. Then, we've got

stuff that we haven't looked at. So, of course, who knows whether

those elements are bigger than or less than the pivot? And then, for the stuff

we've looked at so far, everything less than the pivot comes before everything

bigger than the pivot. This is the picture we wanna retain, as we go through the

linear scan. As this high-level picture would suggest, there is two boundaries

that we're gonna need to keep track of throughout the algorithm. We're gonna need

to keep track of the boundary between what we've looked at so far, and what we

haven't looked at yet. So, that's going to be, we're going to use the index "j" to keep

track of that boundary. And then, we also need a second boundary, for amongst the

stuff that we've seen, where is the split between those less than the pivot and

those bigger than the pivot. So, that's gonna be "i". So, let's use our running

example array. >> So stuff is pretty simple when we're starting out. We haven't

looked at anything. So all of this stuff is unpartitioned. And "i" and "j" both point

to the boundary between the pivot and all the stuff that we haven't seen yet. Now to

get a running time reaches linear, we want to make sure that at each step we

advance "j", we look at one new element. That way in a linear number of steps, we'll

have looked at everything, and hopefully we'll be done, and we'll have a partitioned

array. So, in the next step, we're going to advance "j". So the region of the array

which is, which we haven't looked at, which is unpartitioned, is one smaller

than before. We've now looked at the 8, the first element after the pivot.

9:04

Now the 8 itself is indeed a partitioned array. Everything less than

the pivot comes before, everything after the pivot turns out there's nothing less

than the pivot. So vacuously this is indeed partitioned. So "j" records

delineates the boundary between what we've looked at and what we haven't looked at, "i"

delineates amongst the stuff we've looked at, where is the boundary between what's

bigger than and what's less than the pivot. So the 8 is bigger than the pivot,

so "i" should be right here. Okay, because we want "i" to be just to the left of all the

stuff bigger than the pivot. Now, what's gonna happen in the next iteration? This

is where things get interesting. Suppose we advance "j" one further. Now the part of

the array that we've seen is an 8 followed by a 2. Now an 8 and a 2

is not a partitioned subarray. Remember what it means to be a partitioned

subarray? All the stuff less than the pivot, all the stuff less than

3, should come before everything bigger than 3. So (8, 2) obviously

fails that property. 2 is less than the pivot, but it comes after the 8, which

is bigger than the pivot. So, to correct this, we're going to need to do a swap.

We're going to swap the 2 and the 8. That gives us the following version of the

original array. So now the stuff that we have not yet looked at is one smaller than

before. We've advanced "j". So all other stuff is unpartitioned. Who knows what's

going on with that stuff? "j" is one further entry to the right than it was before, and

at least after we have done this swap, we do indeed have a partitioned array. So

post-swap, the 2 and the 8, are indeed partitioned. Now remember, "I"

delineates the boundary between amongst what we've seen so far, the stuff less

than the pivot, less than 3 in this case, and that bigger than 3, so "I" is

going to be wedged in between the 2 and the 8. In the next iteration, our life

is pretty easy. So, in this case, in advancing "j", we uncover an element which

is bigger than the pivot. So, this is what happened in the first iteration, when we

uncovered the 8. It's different than what happened in the last iteration when

we uncovered the 2. And so, this case, this third iteration is gonna be more

similar to the first iteration than the second iteration. In particular, we won't

need to swap. We won't need to advance "i". We just advance "j", and we're done. So,

let's see why that's true. So, we've advanced "j". We've done one more iteration.

So, now the stuff we haven't seen yet is only the last four elements. So, who knows

what's up with, the stuff we haven't seen yet? But if you look at the stuff we have

seen, the 2, the 8, and the 5, this is, in fact, partitioned, right? All

the numbers that are bigger than 3 succeed, come after, all the numbers

smaller than three. So the "j", the boundary between what we've seen and

what we haven't is between the 5 and the 1; and the "i", the boundary between

the stuff less than the pivot and bigger than the pivot is between the 2 and the

8, just like it was before. Adding a 5 to the end didn't change anything. So

let's wrap up this example in the next slide. So first, let's just remember where

we left off from the previous slide. So I'm just gonna redraw that same step after

three iterations of the algorithm. And notice, in the next generation, we're going

to, again, have to make some modifications to the array, if we want preserve our

variant. The reason is that when we advance "j", when we scan this 1, now

again we're scanning in a new element which is less than the pivot, and what

that means is that, the partitioned region, or the region that we've looked at

so far, will not be partitioned. We'll have 2851. Remember we need everything

less than 3 to precede everything bigger than 3, and this 1

at end is not going to cut it. So we're going to have to make a swap. Now what are

we going to swap? We're going to swap the 1 and the 8. So, why do we swap the

1 and the 8? Well, clearly, we have to swap the 1 with something. And, what

makes sense? What makes sense is the left-most array entry, which is currently

bigger than the pivot. And, that's exactly the 8. Okay, that's the first,

left-most entry bigger than 3, so if we swap the 1 with it, then the 1 will

become the right-most entry smaller than 3. So after the swap, we're gonna have

the following array. The stuff we haven't seen is the 4, the 7, and the 6.

13:37

So the "j" will be between the 8 and the 4. The stuff we have seen is the 2,

1, 5, and 8. And notice, that this is indeed partitioned. All the

elements, which are less than 3, the 2 and the 1, precede all of the

entries, which are bigger than 3, the 5 and the 8. "i", remember, is

supposed to split, be the boundary between those less than 3 and those

bigger than 3. So, that's gonna lie between the 1 and the 5. That is one

further to the right than it was in the previous iteration. Okay, so the, because

the rest of the unseen elements, the 4, the 7, and the 6, are all bigger

than the pivot, the last three iterations are easy. No further swaps are necessary.

No increments to "i" are necessary. "j" is just going to get incremented until we fall off

the array. And then, fast forwarding, the Partition subroutine, or this main linear

scan, will terminate with the following situation. So at this point, all of the

elements have been seen, all the elements are partitioned. "j" in effect has fallen

off the end of the array, and "i", the boundary between those less than and bigger than

the pivot, still lies between the 1 and the 5. Now, we're not quite done,

because the pivot element 3 is not in the correct place. Remember, what we're

aiming for is an array where everything less than the pivot is to the left of it,

and everything bigger than the pivot is to the right. But right now, the pivot still

is hanging out in the first element. So, we just have to swap that into the correct

place. Where's the correct place? Well, it's going to be the right-most element,

which is smaller than the pivot. So, in this case, the 1. So the subroutine will

terminate with the following array, 12358476. And, indeed, as desired,

everything to the left of the pivot is less than the pivot, and everything to

the right of the pivot is bigger than the pivot. The 1 and 2 happen to be in

sorted order, but that was just sorta an accident. And the 4, 5, 6 and

7 and 8, you'll notice, are jumbled up. They're not in sorted order. So

hopefully from this example you have a gist of how the Partition subroutine is

going to work in general. But, just to make sure the details are clear, let me

now describe the pseudocode for the Partition subroutine. So the way I'm going

to denote it is, there's going to be an input array A. But rather than being told

some explicit link, what's going to be passed to the subroutine are two array

indices. The leftmost index, which delineates this part of the separator

you're supposed to work on, and the rightmost index. The reason I'm writing it

this way is because Partition is going to be called recursively from within a QuickSort

algorithm. So any point in QuickSort, we're going to be recursing on some

subset, contiguous subset of the original input array. "l(el)" and "r" meant to denote

what the left boundary and the right boundary of that subarray are. So, let's

not lose sight of the high-level picture of the invariant that the algorithm is

meant to maintain. So, as we discussed, we're assuming the pivot element is the

first element, although that's really without loss of generality. At any given

time, there's gonna be stuff we haven't seen yet. Who knows what's up with that?

And, amongst the stuff we've seen, we're gonna maintain the invariant that all the

stuff less than the pivot comes before all the stuff bigger than the pivot. And "j" and

I denote the boundaries, between the seen and the unseen, and between the small

elements and the large elements, respectively. So back to the pseudocode,

we initialize the pivot to be the first entry in the array. And again remember, l

denotes the leftmost index that we're responsible for looking at. Initial value

of "i", should be just to the right of the pivot so that's gonna be el+1.

That's also the initial value of "j", which will be assigned in the main for-Loop. So this

for-Loop with "j", taking on all values from el+1 to the rightmost index "r",

denotes the linear scan through the input array. And, what we saw in the example is that there

were two cases, depending on, for the newly seen element, whether it's bigger

than the pivot, or less than the pivot. The easy case is when it's bigger than the

pivot. Then we essentially don't have to do anything. Remember, we didn't do any

swaps, we didn't change "i", the boundary didn't change. It was when the new element

was less than the pivot that we had to do some work. So, we're gonna check that, is

the newly seen element, A[j], less than "p". And if it's not, we actually don't have to do

anything. So let me just put as a comment. If the new element is bigger than

the pivot, we do nothing. Of course at the end of the for-Loop, the value of "j" will

get in command so that's the only thing that changes from iteration to iteration,

when we're sucking up new elements that happen to be bigger than "p". So what do we

do in the example, when we suck up our new element less than p? Well we have to do

two things. So, in the event that the newly seen element is less than "p", I'll

circle that here in pink. We need to do a rearrangement, so we, again, have a

partitioned, sub-array amongst those elements we've seen so far. And, the best

way to do that is to swap this new element with the left-most element that's bigger

than the pivot. And because we have an index "i", which is keeping track of the

boundary between the elements less than the pivot and bigger than the pivot, we can

immediately access the leftmost element bigger than the pivot.

That's just the "i"th entry in the array. Now I am

doing something a little sneaky here, I should be honest about. Which is there is

the case where you haven't yet seen any elements bigger than the pivot, and then

you don't actually have a leftmost element bigger than the pivot to swap

with. Turns out this code still works, I'll let you verify that, but it does do

some redundant swaps. Really, you don't need to do any swaps until you first see

some elements bigger than the pivot, and then see some elements less than the

pivot. So, you can imagine a different limitation of this, where you

actually keep track of whether or not that's happened to avoid the redundant

swaps. I'm just gonna give you the simple pseudocode. And again, for

intuition, you wanna think about the case just like, in the picture here in blue,

where we've already seen some elements that are bigger than the pivot, and the

next newly seen element is less than the pivot. That's really sort of the key case

here. Now the other thing we have to do after one of these swaps is, now the

boundary, between where the array elements less than the pivot and

those bigger than the pivot, has moved. It's moved one to the right, so

we have to increment "i". So, that's the main linear scan. Once this concludes, "j"

will have fallen off the end of the array. And, everything that we've seen the final

20:50

elements, except for the pivot, will be arranged so that those less than "p" are

first, those bigger than "p" will be last. The final thing we have to do is just swap

the pivot into its rightful position. And, recall for that, we just swap it with the

right-most element less than it. So, that is it. That is the Partition subroutine.

There's a number of variants of partition. This is certainly not the unique

implementation. If you look on the web, or if you look in certain textbooks, you'll

find some other implementations as well as discussion of the various merits. But, I

hope this gives you, I mean, this is a canonical implementation, and I hope it

gives you a clear picture of how you rearrange the array using in-place swaps

to get the desired property, that all the stuff before the pivot comes first, all

the stuff after the pivot comes last. Let me just add a few details about why

this pseudocode I just gave you does, indeed, have the properties required. The

running time is O(N), really theta of N, but again, I'll be sloppy and write

O(N). Where N is the number of array elements that we have to look at. So, N is

r-el+1, which is the length of the sub-array that this Partition

subroutine is invoked upon. And why is this true? Well if you just go inspect the

pseudocode, you can just count it up naively and you'll find that this is true.

We just do a linear scan through the array and all we do is basically a comparison

and possibly a swap and an increment for each array entry that we see. Also, if you

inspect the code, it is evident that it works in-place. We do not allocate some

second copy of an array to populate, like we did in the naive Partition

subroutine. All we do is repeated swaps. Correctness of the subroutine follows by

induction, so in particular the best way to argue it is by invariant. So I'll state

the invariant here, but mostly leave it for you to check that indeed, every

iteration of the for-Loop maintains this invariant. So first of all, all of the

stuff to the right of the pivot element, to the right of the leftmost entry and up

to the index "i", is indeed less than the pivot element, as suggested by the

picture. And also suggested by the picture, everything beginning with the "i"th

entry, leading just up before the "j"th entry, is bigger than the pivot. And I'll

leave it as a good exercise for you to check that this holds by induction.

23:18

The invariant holds initially, when both "i" and "j" are equal to el+1,

because both of these sets are vacuous, okay? So, there are no such elements, so they're

trivially satisfied these properties. And then, every time we advance "j", well, in

one case it's very easy, where the new element is bigger than the pivot. It's

clear that, if the invariant held before, it also holds at, at the next iteration.

And then, if you think about it carefully, this swap in this increment of "i" that we

do, in the case where the new element is less than the pivot. After the swap, once

the fold is complete, again if this invariant was true at the beginning of it,

it's also true at the end. So what good is that? Well, by this claim, at the

conclusion of the linear scan at which point "j" has fallen off the end of the

array, the array must look like this. At the end of the for-Loop, the question

mark part of the array has vanished, so everything other than the pivot has been

organized so that all this stuff less than the pivot comes before everything after

the pivot, and that means once you do the final swap, once you swap the pivot

element from its first and left most entry, with the right most entry less than

the pivot, you're done. Okay? You've got the desired property that everything to

the left of the pivot is less than, and everything to the right of the pivot is

bigger than. So now that given a pivot element we understand how to very quickly

rearrange the array so that it's partitioned around that pivot element,

let's move on to understanding how that pivot element should be chosen and how,

given suitable choices of that pivot element, we can implement the QuickSort

algorithm, to run very quickly, in particular, on average in O(N) log time.