Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/dutch-national-flag-dnf-problem/.

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c). This problem is also called three color sort.

Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. Hence, we can adopt the algorithm to sort any array of three different kinds of objects / values.

Though at the basics, it is using quicksort algorithm's partition logic.

Let's take a look at the implementation below where we sort an array of three different integers (in cpp) :

Let high be the higher of the 3 elements, and low be the lower of 3 elements , like in (0, 2, 1, 0, 1, 2) low =0, and high=2.

void dutchFlagSort(int inArray[], int arraySize, int high, int low)
{
  if (arraySize == 0)
    return;

  int lower = 0;
  while (inArray[lower] == low && lower < arraySize)
    lower++;

  int upper = arraySize - 1;
  while (inArray[upper] == high && upper >= 0)
    upper--;

  int temp = 0;
  int pivot;
  for (pivot = lower; pivot <= upper;)
  {
    if (inArray[pivot] == low)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[lower];
      inArray[lower] = temp;
      pivot++;
      lower++;
    }
    else if (inArray[pivot] == high)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[upper];
      inArray[upper] = temp;
      upper--;
    }
    else
      pivot++;
  }
}

Time complexity - O(n)

Explanation: the method above takes in an array of integers, the array's size, and the order of the integers (low and high) as arguments. Notice that low indicates the lowest value in the array and high indicates the highest value in the array. For example, if our array is (1, 2, 3, 1, 2, 3) then the low maybe 1 and high maybe 3. The algorithm uses those indicators to sort the array. We can actually specify low and high as any value in the array if we want to. It only affects how the array places the integers.

The basic strategy behind the method is to partition the array into three regions, low, middle and high. These regions correspond to the three kinds of integers. Low integers whose values equal low, high integers whose values equal high, and the middle integers whose values are anything other than high and low.

That's why we have three different iterators. Any integer before lower is low integer, and any integer after upper is high integer. The pivot iterator traveses the array and swaps high and low integers to their correct places. However, it skips over the middle integers because they are supposed to be in the region between low and high integer regions. Let's do an example to clear things up.

Example: lets Dutch Flag sort this array (0, 2, 1, 0, 1, 2)

1. low = 0, high = 2
2. After the first while loop, lower = 1. After the second while loop, upper = 4. Finally, pivot = 1.

     3.  Entering the for loop:

First iteration: array[pivot] = 2 (high), so we swap array[pivot] with array[upper] and decrease upper by 1.

Second iteration: pivot = 1, lower = 1, and upper = 3. Because array[pivot] = 1, we do nothing but increasing pivot by 1.

 Third iteration: pivot = 2, lower = 1, and upper = 3. Again, array[pivot] = 1, we just increase pivot by 1 and move on.

Fourth iteration: pivot = 3, lower = 1, and upper = 3. Since array[pivot] = 0 (low), we swap array[pivot] and array[lower]. Then, we increase both pivot and lower by 1.

Fifth iteration: pivot = 4, lower = 2, and upper = 3. The loop terminates here because pivot is now greater than upper. Here is the final array. Notice how all the 0s, 1s and 2s are separated and sorted in ascending order.

Thanks.

Source