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

Now let’s observe the Hoare partitioning scheme as soon as once more, this time listening to what number of cycles of assignments it introduces.

Let’s assume we have now the identical array “A” of size N, and a pivot worth ‘p’ in accordance with which the partitioning should be made. Additionally let’s assume that there are ‘L’ values within the array which needs to be by some means rearranged, to be able to deliver “A” right into a partitioned state. It seems that Hoare partitioning scheme rearranges these ‘L’ values within the slowest doable approach, as a result of it introduces the maximal doable variety of cycles of assignments, with each cycle consisting of solely 2 values.

Transferring 2 values over a cycle of size 2, which is basically swapping them, requires 3 assignments. So the general variety of values assignments is “3*L/2” for the Hoare partitioning scheme.

The thought which lies beneath the optimization that I’m going to explain, comes from the truth that after partitioning a sequence, we’re typically not inquisitive about relative order of the values “A[i]<p”, which ought to end on the left a part of partitioned sequence, in addition to we aren’t within the relative order of those, which ought to end on the proper half. The one factor that we’re inquisitive about, is for all values lower than ‘p’ to come back earlier than the opposite ones. This truth permits us to change the cycles of assignments in Hoare scheme, and to provide you with only one cycle of assignments, containing all of the ‘L’ values, which ought to by some means be rearranged.

Let me first describe the altered partitioning scheme with the assistance of the next illustration:

So what are we doing right here?

• As within the unique Hoare scheme, at first we scan from the left and discover such worth “A[i]>=p” which ought to go to the appropriate half. However as an alternative of swapping it with another worth, we simply bear in mind it: “tmp := A[i]”.
• Subsequent we scan from proper and discover such worth “A[j]<p” which ought to go to the left half. And we simply do the project “A[i] := A[j]”, with out loosing the worth of “A[i]”, as it’s already saved in “tmp”.
• Subsequent we proceed the scan from left, and discover such worth “A[i]>=p” which additionally ought to go to the appropriate half. So we do the project “A[j] := A[i]”, with out loosing worth “A[j]”, as it’s already assigned to the earlier place of ‘i’.
• This sample continues, and as soon as indexes i and j meet one another, it stays to position some worth better than ‘p’ to “A[j]”, we simply do “A[j] := tmp”, as initially the variable “tmp” was holding the primary worth from left, better than ‘p’. The partitioning is accomplished.

As we see, right here we have now only one cycle of assignments which fits over all of the ‘L’ values, and to be able to correctly rearrange them it requires simply “L+1” worth assignments, in comparison with the “3*L/2” assignments of Hoare scheme.

I desire to name this new partitioning scheme a “Cyclic partition”, as a result of all of the ‘L’ values which needs to be by some means rearranged, now reside on a single cycle of assignments.

Right here is the pseudo-code of the Cyclic partition algorithm. In comparison with the pseudo-code of Hoare scheme the modifications are insignificant, however now we at all times 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 half
// The cycle of assignments begins right here
tmp := A[i]  // The one write to 'tmp' variable
whereas true
// Transfer proper index 'j', as a lot as wanted
whereas i < j and A[j] >= p
j := j-1
if i == j  // Verify for completion of scans
break
// The following project within the cycle
A[i] := A[j]
i := i+1
// Transfer left index 'i', as a lot as wanted
whereas i < j and A[i] < p
i := i+1
if i == j  // Verify for completion of scans
break
// The following project within the cycle
A[j] := A[i]
j := j-1
// The scans have accomplished
A[j] := tmp  // The one learn from 'tmp' variable
return j

Right here strains 5 and 6 arrange the beginning indexes for each scans (‘i’ — from left to proper, and ‘j’ — from proper to left).

Strains 7–9 search from left for such a price “A[i]”, which ought to go to the appropriate half. If it seems that there isn’t a such worth, and all N objects belong to the left half, strains 10 and 11 report that and end the algorithm.

In any other case, if such worth was discovered, at line 13 we bear in mind it within the ‘tmp’ variable, thus opening a slot at index ‘i’ for putting one other worth there.

Strains 15–19 search from proper for such a price “A[j]” which needs to be moved to the left half. As soon as discovered, strains 20–22 place it into the empty slot at index ‘i’, after which the slot at index ‘j’ turns into empty, and waits for one more worth.

Equally, strains 23–27 search from left for such a price “A[i]” which needs to be moved to the appropriate half. As soon as discovered, strains 28–30 place it into the empty slot at index ‘j’, after which the slot at index ‘i’ once more turns into empty, and waits for one more worth.

This sample is sustained in the primary loop of the algorithm, at strains 14–30.

As soon as indexes ‘i’ and ‘j’ meet one another, we have now an empty slot there, and contours 31 and 32 assign the initially remembered worth in ‘tmp’ variable there, so the index ‘j’ turns into the primary one to carry such worth which belongs to the appropriate half.

The final line returns that index.

This fashion we will write 2 assignments of the cycle collectively within the loop’s physique, as a result of because it was confirmed in chapter 3, ‘L’ is at all times a fair quantity.

Time complexity of this algorithm can also be O(N), as we nonetheless scan the sequence from each ends. It simply does 1.5x much less worth assignments, so the speed-up is mirrored solely within the fixed issue.

An implementation of Cyclic partition within the C++ language is current on GitHub, and is referenced on the finish of this story [1].

I additionally wish to present that the worth ‘L’ figuring within the Hoare scheme can’t be lowered, no matter what partitioning scheme we use. Assume that after partitioning, the size of the left half shall be “left_n”, and size of the appropriate half shall be “right_n”. Now, if wanting on the left-aligned “left_n”-long space of the unique unpartitioned array, we are going to discover some ‘t1’ values there, which aren’t at their last locations. So these are such values that are better or equal to ‘p’, and needs to be moved to the appropriate half anyway.

Equally, if wanting on the right-aligned “right_n”-long space of the unique unpartitioned array, we are going to discover some ‘t2’ values there, that are additionally not at their last locations. These are such values that are lower than ‘p’, and needs to be moved to the left half. We will’t transfer lower than ‘t1’ values from left to proper, in addition to we will’t transfer lower than ‘t2’ values from proper to left.

Within the Hoare partitioning scheme, the ‘t1’ and ‘t2’ values are those that are swapped between one another. So there we have now:

t1 = t2 = L/2,

or

t1 + t2 = L.

Which signifies that ‘L’ is definitely the minimal quantity of values which needs to be by some means rearranged, to ensure that the sequence to turn out to be partitioned. And the Cyclic partition algorithm rearranges them doing simply “L+1” assignments. That’s why I permit myself to name this new partitioning scheme as “practically optimum”.