Partitioning problems

Sort an array containing only 0, 1 and 2 in one pass and O(1) space, as if sorting the three stripes of the Dutch flag. Maintain three zones with pointers: [0, lo) holds 0s, [lo, mid) holds 1s, (hi, n) holds 2s, and [mid, hi] is unexamined. Dijkstra's solution handles each element once.

The first preset is exactly this problem, with pivot value 1.

1static void sortColors(int[] a) {
2    int lo = 0, mid = 0, hi = a.length - 1;
3    while (mid <= hi) {
4        if (a[mid] == 0) swap(a, lo++, mid++);
5        else if (a[mid] == 2) swap(a, mid, hi--);   // do not advance mid: the swapped-in value is unexamined
6        else mid++;
7    }
8}

1static void partition3(int[] a, int pivot) {
2    int lo = 0, mid = 0, hi = a.length - 1;      // [0,lo) < pivot, [lo,mid) == pivot, (hi,n) > pivot
3    while (mid <= hi) {
4        if (a[mid] < pivot) swap(a, lo++, mid++);
5        else if (a[mid] > pivot) swap(a, mid, hi--);
6        else mid++;
7    }
8}

Partitioning by a pivot value moves every element smaller than the pivot to the left and the rest to the right. The Lomuto scheme keeps a store index of the next slot for a small value and swaps each small element into it. It returns how many values are smaller. One pass, O(n) time, O(1) space, not stable.

This is the heart of quicksort and quickselect.

1static int partition(int[] a, int pivot) {      // returns the count of values < pivot
2    int store = 0;
3    for (int i = 0; i < a.length; i++) {
4        if (a[i] < pivot) { swap(a, store, i); store++; }
5    }
6    return store;
7}

1static int partition(int[] a, int pivot) {      // returns how many values are < pivot
2    int store = 0;
3    for (int i = 0; i < a.length; i++) {
4        if (a[i] < pivot) {
5            swap(a, store, i);
6            store++;
7        }
8    }
9    return store;
10}

Rearranging so that signs alternate (positives at even indexes, negatives at odd) while keeping the relative order within each sign is easy with an output array and two write indexes advancing by 2. It needs equal numbers of positives and negatives (and no zeros) for a perfect alternation.

The order-preserving in-place variant requires rotations and costs O(n²).

1static int[] rearrange(int[] a) {
2    int[] out = new int[a.length];
3    int pos = 0, neg = 1;
4    for (int x : a) {
5        if (x > 0) { out[pos] = x; pos += 2; } else { out[neg] = x; neg += 2; }
6    }
7    return out;
8}

1static int[] rearrange(int[] a) {          // equal numbers of positives and negatives
2    int[] out = new int[a.length];
3    int pos = 0, neg = 1;                  // positives take even slots, negatives odd slots
4    for (int x : a) {
5        if (x > 0) { out[pos] = x; pos += 2; }
6        else       { out[neg] = x; neg += 2; }
7    }
8    return out;
9}

A stable partition keeps the original relative order inside each group; an unstable one may reorder equal-group elements. The stable version needs O(n) extra space (or O(n log n) time in place). The two-pointer version uses O(1) space but its long-distance swaps can reorder values.

Run both methods on the same duplicated input and compare the a/b tags.

1// stable: evens first, relative order kept, O(n) extra space
2static int[] stablePartition(int[] a) {
3    int[] out = new int[a.length]; int w = 0;
4    for (int x : a) if (x % 2 == 0) out[w++] = x;
5    for (int x : a) if (x % 2 != 0) out[w++] = x;
6    return out;
7}
8// unstable: O(1) extra space, order not kept
9static void unstablePartition(int[] a) {
10    int l = 0, r = a.length - 1;
11    while (l < r) {
12        if (a[l] % 2 == 0) l++;
13        else if (a[r] % 2 != 0) r--;
14        else swap(a, l++, r--);
15    }
16}

A three-way partition splits around a pivot value into less, equal and greater. Handling the equal elements in one block is what makes three-way quicksort fast on inputs with many duplicates. It generalises the Dutch flag to an arbitrary pivot.

Choose a pivot that is not in the array, or one that appears many times, and watch the three zones.

1static void partition3(int[] a, int pivot) {
2    int lo = 0, mid = 0, hi = a.length - 1;
3    while (mid <= hi) {
4        if (a[mid] < pivot) swap(a, lo++, mid++);
5        else if (a[mid] > pivot) swap(a, mid, hi--);
6        else mid++;
7    }
8}

1static void partition3(int[] a, int pivot) {
2    int lo = 0, mid = 0, hi = a.length - 1;      // [0,lo) < pivot, [lo,mid) == pivot, (hi,n) > pivot
3    while (mid <= hi) {
4        if (a[mid] < pivot) swap(a, lo++, mid++);
5        else if (a[mid] > pivot) swap(a, mid, hi--);
6        else mid++;
7    }
8}