> So you start left, the first element on the left partition belongs in the left partition, so you swap it into the right partition?
Yes and no. You temporarily do swap it into the right partition, but then increment the pointers which redefines where the right partition is: you swap it with the first element of the right partition before incrementing both i and j. In essence what this does is move the entire right partition one step to the right, while putting the previously unknown element before it.
Consider this example:
l l l l r r r r r ? ? ? ?
^ ^
i j
Now if the first ? was an r element, you could simply increment j and be done with it. But suppose it was an l element, then you have this scenario:
l l l l r r r r r l ? ? ?
^ ^
i j
Note that "the first element of the right partition" is equivalent to "the first element after the left partition". Does it now make more sense that swapping the first element of the right partition and the unknown element (v[i], v[j]) is the right thing to do? After our swap we have this:
+- swap --+
v v
l l l l l r r r r r ? ? ?
^ ^
i j
So now incrementing i and j both fixes our invariant:
l l l l l r r r r r ? ? ?
^ ^
i j
> And what about the element that was in the right partition, when do you check where that one belongs?
That one still belongs in the right partition, which is why we increment both i and j.
Ahh, thank you, this clarifies things! I was thinking of Quicksort, where j moves left until it meets i, and missed the fact that they both move in the same direction and i runs through the entire list. Thanks!
EDIT: I'm now on the desktop and see that your graphs clarify this much better, on mobile I had Dark Reader and they were invisible. You may want a white background.
> I was thinking of Quicksort, where j moves left until it meets i, and missed the fact that they both move in the same direction and i runs through the entire list.
You were thinking of Hoare partitioning. Quicksort can use either Hoare or Lomuto (or any other) partitioning algorithm.
Yes and no. You temporarily do swap it into the right partition, but then increment the pointers which redefines where the right partition is: you swap it with the first element of the right partition before incrementing both i and j. In essence what this does is move the entire right partition one step to the right, while putting the previously unknown element before it.
Consider this example:
Now if the first ? was an r element, you could simply increment j and be done with it. But suppose it was an l element, then you have this scenario: Note that "the first element of the right partition" is equivalent to "the first element after the left partition". Does it now make more sense that swapping the first element of the right partition and the unknown element (v[i], v[j]) is the right thing to do? After our swap we have this: So now incrementing i and j both fixes our invariant: > And what about the element that was in the right partition, when do you check where that one belongs?That one still belongs in the right partition, which is why we increment both i and j.