Cyclic Partition: An Up to 1.5x Faster Partitioning Algorithm | by Tigran Hayrapetyan | Oct, 2024

Now let’s observe the Hoare partitioning scheme once again, this time paying attention to how many cycles of assignments it introduces.

Let’s assume we have the same array “A” of length N, and a pivot value ‘p’ according to which the partitioning must be made. Also let’s assume that there are ‘L’ values in the array which should be somehow rearranged, in order to bring “A” into a partitioned state. It turns out that Hoare partitioning scheme rearranges those ‘L’ values in the slowest possible way, because it introduces the maximal possible number of cycles of assignments, with every cycle consisting of only 2 values.

Moving 2 values over a cycle of length 2, which is essentially swapping them, requires 3 assignments. So the overall number of values assignments is “3*L/2” for the Hoare partitioning scheme.

The idea which lies beneath the optimization that I am going to describe, comes from the fact that after partitioning a sequence, we are generally not interested in relative order of the values “A[i]<p”, which should finish at the left part of partitioned sequence, as well as we are not interested in the relative order of the ones, which should finish at the right part. The only thing that we are interested in, is for all values less than ‘p’ to come before the other ones. This fact allows us to alter the cycles of assignments in Hoare scheme, and to come up with only 1 cycle of assignments, containing all the ‘L’ values, which should somehow be rearranged.

Let me first describe the altered partitioning scheme with the help of the following illustration:

So what are we doing here?

• As in the original Hoare scheme, at first we scan from the left and find such value “A[i]>=p” which should go to the right part. But instead of swapping it with some other value, we just remember it: “tmp := A[i]”.
• Next we scan from right and find such value “A[j]<p” which should go to the left part. And we just do the assignment “A[i] := A[j]”, without loosing the value of “A[i]”, as it is already stored in “tmp”.
• Next we continue the scan from left, and find such value “A[i]>=p” which also should go to the right part. So we do the assignment “A[j] := A[i]”, without loosing value “A[j]”, as it is already assigned to the previous position of ‘i’.
• This pattern continues, and once indexes i and j meet each other, it remains to place some value greater than ‘p’ to “A[j]”, we just do “A[j] := tmp”, as initially the variable “tmp” was holding the first value from left, greater than ‘p’. The partitioning is completed.

As we see, here we have only 1 cycle of assignments which goes over all the ‘L’ values, and in order to properly rearrange them it requires just “L+1” value assignments, compared to the “3*L/2” assignments of Hoare scheme.

I prefer to call this new partitioning scheme a “Cyclic partition”, because all the ‘L’ values which should be somehow rearranged, now reside on a single cycle of assignments.

Here is the pseudo-code of the Cyclic partition algorithm. Compared to the pseudo-code of Hoare scheme the changes are insignificant, but now we always do 1.5x fewer assignments.

// Partitions sequence A[0..N) with pivot value 'p' 
// by "cyclic partition" scheme, and returns index of 
// the first value of the resulting right part.
function partition_cyclic( A[0..N) : Array of Integers, p: Integer ) : Integer
i := 0
j := N-1
// Find the first value from left, which is not on its place
while i < N and A[i] < p
i := i+1
if i == N
return N  // All N values go to the left part
// The cycle of assignments starts here
tmp := A[i]  // The only write to 'tmp' variable
while true
// Move right index 'j', as much as needed
while i < j and A[j] >= p
j := j-1
if i == j  // Check for completion of scans
break
// The next assignment in the cycle
A[i] := A[j]
i := i+1
// Move left index 'i', as much as needed
while i < j and A[i] < p
i := i+1
if i == j  // Check for completion of scans
break
// The next assignment in the cycle
A[j] := A[i]
j := j-1
// The scans have completed
A[j] := tmp  // The only read from 'tmp' variable
return j

Here lines 5 and 6 set up the start indexes for both scans (‘i’ — from left to right, and ‘j’ — from right to left).

Lines 7–9 search from left for such a value “A[i]”, which should go to the right part. If it turns out that there is no such value, and all N items belong to the left part, lines 10 and 11 report that and finish the algorithm.

Otherwise, if such value was found, at line 13 we remember it in the ‘tmp’ variable, thus opening a slot at index ‘i’ for placing another value there.

Lines 15–19 search from right for such a value “A[j]” which should be moved to the left part. Once found, lines 20–22 place it into the empty slot at index ‘i’, after which the slot at index ‘j’ becomes empty, and waits for another value.

Similarly, lines 23–27 search from left for such a value “A[i]” which should be moved to the right part. Once found, lines 28–30 place it into the empty slot at index ‘j’, after which the slot at index ‘i’ again becomes empty, and waits for another value.

This pattern is continued in the main loop of the algorithm, at lines 14–30.

Once indexes ‘i’ and ‘j’ meet each other, we have an empty slot there, and lines 31 and 32 assign the originally remembered value in ‘tmp’ variable there, so the index ‘j’ becomes the first one to hold such value which belongs to the right part.

The last line returns that index.

This way we can write 2 assignments of the cycle together in the loop’s body, because as it was proven in chapter 3, ‘L’ is always an even number.

Time complexity of this algorithm is also O(N), as we still scan the sequence from both ends. It just does 1.5x less value assignments, so the speed-up is reflected only in the constant factor.

An implementation of Cyclic partition in the C++ language is present on GitHub, and is referenced at the end of this story [1].

I also want to show that the value ‘L’ figuring in the Hoare scheme can’t be lowered, regardless of what partitioning scheme we use. Assume that after partitioning, the length of the left part will be “left_n”, and length of the right part will be “right_n”. Now, if looking at the left-aligned “left_n”-long area of the original unpartitioned array, we will find some ‘t1’ values there, which are not at their final places. So those are such values which are greater or equal to ‘p’, and should be moved to the right part anyway.

Similarly, if looking at the right-aligned “right_n”-long area of the original unpartitioned array, we will find some ‘t2’ values there, which are also not at their final places. Those are such values which are less than ‘p’, and should be moved to the left part. We can’t move less than ‘t1’ values from left to right, as well as we can’t move less than ‘t2’ values from right to left.

In the Hoare partitioning scheme, the ‘t1’ and ‘t2’ values are the ones which are swapped between each other. So there we have:

t1 = t2 = L/2,

or

t1 + t2 = L.

Which means that ‘L’ is actually the minimal amount of values which should be somehow rearranged, in order for the sequence to become partitioned. And the Cyclic partition algorithm rearranges them doing just “L+1” assignments. That’s why I allow myself to call this new partitioning scheme as “nearly optimal”.