Previously, we discussed an efficient algorithm for partitioning an array. Suppose we want to create a ternary partition, so all entries less than a given value or range come first, all entries equal to a given value or within the given range come second, and all entries greater than the given value or range come last.

For the purpose of this project, we will focus on a ternary partition with respect to a given value.

For example, given the following twenty values

    int array[20]{
        4, 5, 5, 9, 9, 2, 0, 0, 0, 5, 3, 6, 7, 3, 9, 2, 9, 3, 4, 5
    };

a ternary partition relative to 5 would be

    {4, 2, 0, 0, 0, 3, 3, 2, 3, 4, 5, 5, 5, 5, 9, 9, 6, 7, 9, 9}

This is of course, not unique, and another solution would be to simply sort the twenty values:

    {0, 0, 0, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 7, 9, 9, 9, 9} 

Sorting is, however, more expensive. Can you modify the previous partitioning algorithm to come up with some way of doing a ternary partition?

One counter-intuitive solution is as follows:

We will move objects in a similar manner as we did in the previous partitioning algorithm; however, we will do the opposite of what may seem to be most useful: we will copy entries that are equal to the value to either the front or the back of the array.

We will use four indices:

• index_equal_lower, which stores the next position to store an entry that equals the value in question.
• index_less, which stores the next position to store an entry that is less than the value in question when this index actually represents a 'hole'.
• index_greater, which stores the next position to store an entry that is greater than the value in question when this index actually represents a 'hole'
• index_equal_upper, which stores the next position to store an entry that equals the value in question.

Initially, the first two are 0 and the last two are capacity - 1. At the end of the partitioning phase, it will be true that index_less == index_greater, and that is the location of the 'hole' into which the first that was copied out from array[0] will be placed.

Finally, we will add 1 to the last two entries so that

• All entries from 0 to index_equal_lower - 1 store entries equal to the value.
• All entries from index_equal_lower to index_less - 1 store entries less than the value.
• All entries from index_less to index_greater - 1 store entries equal to the value (with there being either none or at most one entry on this range).
• All entries from index_greater to index_equal_upper - 1 store entries greater then the value.
• All entries from index_equal_upper to capacity - 1 store entries equal to the value.

Once this is achieved, we only need move the entries equal to the value back to the center, and we can use an unordered range swap, as the moved entries only need to satisfy the condition and their relative order does not matter. Once this is done, then:

• All entries from 0 to index_less - index_equal_lower - 1 store entries less than the value.
• All entries from index_less - index_equal_lower to index_greater + capacity - index_equal_upper - 1 store entries equal to the value.
• All entries from index_greater + capacity - index_equal_upper to capacity - 1 store entries greater than the value.

For example, if 0 is the value, then for the array

   {0, -1, 4, -2, 3, 9, 0, -5, -1, 6, -8, 8, 6, 0, 7, 0, -4, 9, -7, 7}

the preliminary partitioned would be

   {0, 0, -4, -2, -7, -1, -8, -5, -1, 0, 6, 8, 6, 7, 7, 9, 3, 9, 4, 0}

and when the zeros are moved, we are left with

   {-5, -1, -4, -2, -7, -1, -8, 0, 0, 0, 0, 8, 6, 7, 7, 9, 3, 9, 4, 6}

Similarly, the three states for this next array are:

   {-8, -6, -9, -5,  0, -4,  1, -2, -7, -6,  5,  8,  3,  9, -2, -1,  2,  5, -5,  0}
   { 0, -6, -9, -5, -5, -4, -1, -2, -7, -6, -2, -8,  3,  9,  8,  5,  2,  5,  1,  0}
   {-8, -6, -9, -5, -5, -4, -1, -2, -7, -6, -2,  0,  0,  9,  8,  5,  2,  5,  1,  3}

To return the two indices, we will use the standard library's std::pair class:

std::pair<std::size_t, std::size_t> ternary_partition(...);

The library is

#include <utility>

Rather than calling a constructor, there is a convenient factory, so if we are to return such a pair, we would use

	// Assume 'index_less' is the index of the
	// first equal to the 'value', and
	// 'index_greater' is the first index of the
	// first entry greater than the 'value'.
	return std::make_pair( index_less, index_greater );
}

There are two public member variables, first and second, and these can be accessed quite easily as they are public:

    auto bounds{ ternary_partition( array, capacity, f ) };
    std::cout << bounds.first << ", "
              << bounds.second << capacity << std::endl;

You can view this code at replit.com.

In this program, we also offer an alternative, whereby rather than just passing a value, we can pass a comparator that returns either a negative integer, 0 or a positive integer. Anything for which the comparator returns 0 will be placed in the middle third. This allows for a much more general application of this function.