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
