package threeWayPartition;
public final class ThreeWayPartition {
/** Simple pair type (works on any Java version). */
public static final class Pair {
public final int i; // start (inclusive) of == pivot block
public final int j; // end (inclusive) of == pivot block
public Pair(int i, int j) { this.i = i; this.j = j; }
public int i() { return i; }
public int j() { return j; }
@Override public String toString() { return "(" + i + "," + j + ")"; }
}
private ThreeWayPartition() {}
/** Partition entire array using a[0] as pivot; returns inclusive [i, j] of == pivot. */
public static Pair threeWayPartition(int[] a) {
if (a == null || a.length == 0) throw new IllegalArgumentException("empty array");
return threeWayPartition(a, 0, a.length - 1);
}
/**
* 3-way partition of a subarray [lo..hi] using a[lo] as pivot.
* Returns (i, j) where a[lo..i-1] < pivot, a[i..j] == pivot, a[j+1..hi] > pivot.
*/
public static Pair threeWayPartition(int[] a, int lo, int hi) {
// TODO: Implement me
return new Pair(0,0); // so it compiles
}
private static void swap(int[] a, int x, int y) {
if (x == y) return;
int tmp = a[x];
a[x] = a[y];
a[y] = tmp;
}
}