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.

Â