Cyclic Partition: An As much as 1.5x Sooner Partitioning Algorithm | by Tigran Hayrapetyan | Oct, 2024

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

Let’s assume we now have the identical array “A” of size N, and a pivot worth ‘p’ in keeping with which the partitioning should be made. Additionally let’s assume that there are ‘L’ values within the array which ought to be in some way rearranged, in an effort to deliver “A” right into a partitioned state. It seems that Hoare partitioning scheme rearranges these ‘L’ values within the slowest doable means, 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 concept which lies beneath the optimization that I’m going to explain, comes from the truth that after partitioning a sequence, we’re usually not interested by 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 interested by, is for all values lower than ‘p’ to return earlier than the opposite ones. This truth permits us to change the cycles of assignments in Hoare scheme, and to provide you with just one cycle of assignments, containing all of the ‘L’ values, which ought to in some way 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 authentic Hoare scheme, at first we scan from the left and discover such worth “A[i]>=p” which ought to go to the fitting half. However as a substitute of swapping it with another worth, we simply keep 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 task “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 fitting half. So we do the task “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 now have just one cycle of assignments which matches over all of the ‘L’ values, and in an effort to correctly rearrange them it requires simply “L+1” worth assignments, in comparison with the “3*L/2” assignments of Hoare scheme.

I want to name this new partitioning scheme a “Cyclic partition”, as a result of all of the ‘L’ values which ought to be in some way 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 adjustments 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  // Examine for completion of scans
break
// The following task 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  // Examine for completion of scans
break
// The following task 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 fitting half. If it seems that there isn’t any 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 keep 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 ought 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 ought to be moved to the fitting 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 now have 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 fitting half.

The final line returns that index.

This manner 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 good quantity.

Time complexity of this algorithm can 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 can be “left_n”, and size of the fitting half can be “right_n”. Now, if trying on the left-aligned “left_n”-long space of the unique unpartitioned array, we’ll 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 ought to be moved to the fitting half anyway.

Equally, if trying on the right-aligned “right_n”-long space of the unique unpartitioned array, we’ll discover some ‘t2’ values there, that are additionally not at their last locations. These are such values that are lower than ‘p’, and ought 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 now have:

t1 = t2 = L/2,

or

t1 + t2 = L.

Which signifies that ‘L’ is definitely the minimal quantity of values which ought to be in some way rearranged, to ensure that the sequence to change into partitioned. And the Cyclic partition algorithm rearranges them doing simply “L+1” assignments. That’s why I enable myself to name this new partitioning scheme as “almost optimum”.