@@ -0,0 +1,1502 @@
+package interviewquestions;%0A%0Aimport java.util.Arrays;%0A%0Apublic class Partition extends TestCase %7B%0A  /**%0A   * Rebuilds %60array%60 so that items smaller than %60array%5Bk%5D%60 will be left of %60array%5Bk%5D%60,%0A   * and items larger than %60array%5Bk%5D%60 will be right of %60array%5Bk%5D%60.%0A   *%0A   * @return the new index of k%0A   */%0A  private static int partition(int%5B%5D array, int k) %7B%0A    final int item = array%5Bk%5D;%0A%0A    swap(array, k, array.length - 1);%0A    k = array.length - 1;%0A%0A    for (int i = 0; i %3C k; i++) %7B%0A      while (array%5Bi%5D %3E item && k %3E i) %7B%0A        swap(array, i, k);%0A        swap(array, i, k - 1);%0A        k--;%0A      %7D%0A    %7D%0A    %0A    return k;%0A  %7D%0A%0A  private static void swap(int%5B%5D array, int i, int j) %7B%0A    final int tmp = array%5Bi%5D;%0A    array%5Bi%5D = array%5Bj%5D;%0A    array%5Bj%5D = tmp;%0A  %7D%0A%0A  private static int%5B%5D makeArray() %7B%0A    return new int%5B%5D %7B 1, 84, 7, 55, 12, 95, 247, 28, 4, 3 %7D;%0A  %7D%0A%0A  public static void main(String%5B%5D args) %7B%0A    int array%5B%5D;%0A%0A    array = makeArray();%0A    System.out.println(Arrays.toString(array));%0A%0A    array = makeArray();%0A    assertEquals(6, partition(array, 3)); // 55%0A    System.out.println(Arrays.toString(array));%0A%0A    array = makeArray();%0A    assertEquals(4, partition(array, 4)); // 12%0A    System.out.println(Arrays.toString(array));%0A%0A    array = makeArray();%0A    assertEquals(0, partition(array, 0)); // 1%0A    System.out.println(Arrays.toString(array));%0A%0A    array = makeArray();%0A    assertEquals(1, partition(array, 9)); // 3%0A    System.out.println(Arrays.toString(array));%0A  %7D%0A%7D%0A%0A

Partition the array