Reference: EPI 5.1

Description:

The quicksort algorithm would have a bad performance when the array contains many duplicates because the subarrays may differ greatly in size.

One solution is reordering or shuffling the array before sorting. Another solution is known as Dutch national flag partitioning since the Dutch national flag consists of three horizontal bands (red, white, blue).

The Dutch National Flag

Let say an example [0, 1, 2, 0, 2, 1, 1], and the pivot index is $3$ (A[3] = 0), so the correct partitioning is [0, 0, 1, 2, 2, 1, 1]. The elements larger than $0$ should be after $0$, but the ordering does not matter.

If the pivot index is $1$ (A[1] = 1), so the correct partitioning is [0, 0, 1, 1, 1, 2, 2].

We have three groups: smaller, equal, larger. To simply the problem we have a enum class as follows:

1
2
public enum Color { RED, WHITE, BLUE }
// their ordinal()   0     1     2

We use RED to denote elements in the smaller group. They could be duplicates or different elements, but that is okay as long as they are less than the WHITE elements in the equal group.

Problem

Write a problem that takes an array A and an index i into A, and rearranges the elements such that all elements less than A[i] (the “pivot”) appear first, followed by elements equal to the pivot, followed by elements greater than the pivot.

Note: The problem is trivial to solve with $O(N)$ extra space. We can put elements into three arrays and then merge them.

Analysis

Brute-Force

We can avoid the extra space. In the first pass, we iterate through the array and seek an element smaller than the pivot. As soon as we find it, we move it to the subarray of smaller elements via swapping. In the second pass, we do the same thing but moving the larger element to the subarray of larger elements.

Note: In the second pass, we can stop when hitting an element smaller than the pivot, because smaller elements should all lie on the left part of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void dutchFlagPartition(int pivotIndex, List<Color> A) {
  Color pivot = A.get(pivotIndex);
  // First pass: group elements smaller than pivot.
  for (int i = 0; i < A.size(); ++i) {
    // Look for a smaller element
    for (int j = i + 1; j < A.size(); ++j) {
      if (A.get(j).ordinal() < pivot.ordinal()) {
        Collections.swap(A, i, j);
        break;
      }
    }
  }
  // Second pass: group elements larger than pivot.
  for (int i = A.size()  - 1; i >= 0; --i) {
    // Stop when hitting an element smaller than the pivot.
    if (A.get(i).ordinal() < pivot.ordinal()) break;
    for (int j = i - 1; j >= 0; --j) {
      if (A.get(j).ordinal() > pivot.ordinal()) {
        Collections.swap(A, i, j);
        break;
      }
    }
  }
}

Time: $O(N^2)$
Space: $O(1)$

The worst case occurs when the pivot is in the middle and all elements on its left are larger and the elements on its right are smaller, for example [5, 6, 9, 7, <5>, 3, 2, 4, 1]. As for the first element (i = 0), j has to go through half of the array, which takes $O(N/2)$ time, to find element 3.

Two Passes

We can improve the time complexity by making a single pass to move smaller elements to the beginning and by making another pass starting from the end to move larger elements to the end.

Alternatively, in the second pass, we can instead move elements which are equal to the pivot, so we don’t need an extra variable to store the current index.

Note: The element in the original pivotIndex may change when the pivot element is swapped. It does not affect the result since we have backed up the pivot at the beginning of the program, so the value of pivot won’t change.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Example:  2  6  3  7  <5>  3  2  7  1
public static void dutchFlagPartition(int pivotIndex, List<Color> A) {
  Color pivot = A.get(pivotIndex); // back up the pivot
  // First pass
  int count = 0;
  for (int i = 0; i < A.size(); ++i) {
    if (A.get(i).ordinal() < pivot.ordinal()) {
      Collections.swap(A, i, count++);
    }
  } // now "count" is pointing to first position of the "equal" group

  // Second pass - Move elements equal to pivot
  for (int i = count; i < A.size(); ++i) {
    if (A.get(i).ordinal() == pivot.ordinal()) {
      Collections.swap(A, i, count++);
    }
  }
  // larger elements are automatically arranged.
}

Time: $O(N)$
Space: $O(1)$

One Pass

Similar to the two-pass approach, the difference is that it performs classification into elements less than, equal to, and greater than the pivot in a single pass. We can do this by maintaining four subarrays: smaller, equal, unclassified, larger. In the code, we use three pointers smaller, equal, larger to denote the elements in the four subarrays.

The explanation is in the comments. Notice the equal always points to the incoming unclassified element. And the elements before smaller and the elements after larger are finalized.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2   6   3   7  <5>  3   2   7   1
sm                              lg
eq
2   6   3   7  <5>  3   2   7   1
    sm                          lg
    eq
2   1   3   7  <5>  3   2   7   6
    sm                      lg
    eq
2   1   3   7  <5>  3   2   7   6
        sm                  lg
        eq
2   1   3   7  <5>  3   2   7   6
            sm              lg
            eq
2   1   3   7  <5>  3   2   7   6
            sm          lg
            eq
2   1   3   2  <5>  3   7   7   6
            sm      lg
            eq
2   1   3   2  <5>  3   7   7   6
                sm  lg
                eq
2   1   3   2  <5>  3   7   7   6
                sm  lg
                    eq
2   1   3   2   3  <5>  7   7   6
                    sm
                    lg
                        eq       // end

Note: This is my solution based on larger = A.size() - 1 and while (equal <= larger). The solution in the book is based on larger = A.size() and while (equal < larger). They are equivalent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void dutchFlagPartition(int pivotIndex, List<Color> A) {
  Color pivot = A.get(pivotIndex);
  int smaller = 0, equal = 0, larger = A.size() - 1;
  while (equal <= larger) {
    // A.get(equal) is the incoming unclassified element
    if (A.get(equal).ordinal() < pivot.ordinal()) {
      Collections.swap(A, equal++, smaller++);
    } else if (A.get(equal).ordinal() > pivot.ordinal()) {
      Collections.swap(A, equal, larger--); // equal not changing since its element is not processed
    } else { // A.get(equal).ordinal() == pivot.ordinal()
      equal += 1;
    }
  }
}

Time: $O(N)$ since each time at least one of the pointers is moved and each subarray is either expended by one or shrunk by one.
Space: $O(1)$

Variant 1

Bring duplicate elements all together, but the ordering is not required.

1
2
3
4
5
6
7
8
9
10
11
12
public static void variant1(List<Color> A) {
  if (A.size() == 0) return;
  int count = 0;
  while (count < A.size()) {
    Color curr = A.get(count);
    for (int i = count; i < A.size(); ++i) {
      if (A.get(i).ordinal() == curr.ordinal()) {
        Collections.swap(A, i, count++);
      }
    }
  }
}

Time: $O(N)$
Space: $O(1)$