Dutch national flag problem

• three color problem
• sort an array for 0s-1s-2s

Problem description

Reorder the array so that all elements less than the pivot appear first, followed by elements greater than the pivot.

Simple solution swap in place with two pass

/**
 * Time complexity: O(n^2)
 * Worst case: if i = n/2, and all the elements greater than A[i], and all elements after i are less than A[i]
 * Space complexity: O(1)
 */
public static void dutchNationalFlagInPlace(int[] array, int pivot) {

    // group elements smaller than array
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < pivot) {
                swap(array, i, j);
                break;
            }
        }
    }

    // group elements bigger than array
    for (int i = array.length - 1; i >= 0 && array[i] >= pivot; i--) {
        for (int j = i - 1; j >= 0 && array[j] >= pivot; j--) {
            if (array[j] > pivot) {
                swap(array, i, j);
                break;
            }
        }
    }

}

private static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

Solution swap in place with two pass

public static void dutchNationalFlagInPlaceOnePass(int[] array, int pivot) {
    /**
     * Time complexity: O(n)
     * Space complexity: O(1)
     * Because there is no reason to start from so far back,
     * we can begin from the last location we advanced to.
     */

    int smaller = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] < pivot)
            swap(array, i, smaller++);
    }

    int larger = array.length - 1;
    for (int i = array.length - 1; i >= 0 && array[i] >= pivot; i--) {
        if (array[i] > pivot) {
            swap(array, i, larger--);
        }
    }

}

Solution swap in place with one pass

public static void dutchNationalFlagPartition(int[] array, int pivot) {
    /**
     * Time complexity: O(n)
     * Space complexity: O(1)
     */

    int smaller = 0;
    int equal = 0;
    int larger = array.length - 1;

    /**
     * Keep the following invariants during partitioning:
     * bottom group: A.subList(0 : smaller).
     * middle group: A.subList(smaller : equal).
     * unclassified group: A.subList(equal : larger + 1).
     * top group: A.subList(larger + 1, A.size()).
     */
    while (equal <= larger) {
        // array[equal] is the incoming unclassified element
        if (array[equal] < pivot) {
            swap(array, equal++, smaller++);
        } else if (array[equal] == pivot) {
            equal++;
        } else {
            swap(array, equal++, larger--);
        }
    }
}