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