Partitioning array elements into two subsets Problem:


  Given a randomly ordered array of n-elements, partition the elements
  into two subsets such that elements &lt;= x are in one subset and elements
  
  
    x are in the other subset.
  
  
  One way to do this is to sort the array in ascending order. But with
  this solution we actually ordered the array in addition to partition.
  Also sort is costly.
  
  For example, let's take this array \$[37,36,27,11,15,12,34,29,4,10]\$
  and partition value is 17.
  
  So the array after partition should be
  \$[10,4,12,11,15,27,34.29.36,37]\$
  
  Comparing these two data sets we can see that elements from left side
  greater than 17 must be moved to right side and at the right side
  elements less than 17 to left side.
  
  Initially we do not know how many elements are less than &lt; 17. One
  way to solve this, pass through the array and count the number of
  elements less than 17. Once we know the partition value (here it is
  15), then make another pass through the array to make the exchange.
  But this is \$0(n^2)\$.
  
  We need to find a solution where this can be done with only pass
  through the array. Looking at these data sets we can find that even if
  we do not know the partition value(here it is 17), 37 can be exchanged
  with 10, 36 can be exchanged with 4 and so on.
  
  This is something like left partition is growing to right and right is
  growing to left.

| Left Partition -&gt;    ||   &lt;- Right Partition |
^                    ^                       ^
i=0            partition point           j=n (length of array) 

  
  So we get the basic mechanism to exchange, while two partitions have
  not met do
  
  
  Extend the left and right partitions inward exchanging wrongly  placed elements.
  Exchange can be done by the standard technique

t = a[i];
a[i] = a[j];
t = a[j];

  Moving inwards from left and right can be done by,
  
  from left to right: while(a[i] &lt;= x) i = i + 1;
  
  from right to left: while(x &lt; a[j]) j = j - 1;
  
  where a is the array, i is the starting index 0, j is last index
  that is the length of the array.
  
  
  One case is, initially we don't know a[i] and a[j] should be
  exchanged since there is no initial move inwards from the left and
  right to check if an exchange is really necessary. we can overcome
  this by placing a check before passing through the array:

while(a[i] &lt;= x) i = i + 1;
while(x &lt; a[j]) j = j - 1;

  
  Algorithm (it is based on R. G. Dromey's How to solve it by computer):
  
  
  Establish an array \$a[1...n]\$ and partition value x.
  Move the two partitions towards each other until a wrongly placed pair of    elements is encountered.
  While two partitions have not met or crossed do
  
  exchange wrongly placed pairs and extend both partitions inwards    by one element.
  extend left partition while elements less than or equal to x
  extend right partition while elements greater than x
  
  Print partitioning index p and partitioned array.
  


Here is my solution:

public class PartitionArray {

  public static void main(String args[]) {

    int[] elements = {37, 36, 27, 11, 15, 12, 34, 29, 4, 10};

    int x = 17;
    int p = 0;

    int i = 0;
    int j = elements.length - 1;

    while (elements[i] &lt;= x &amp;&amp; i &lt; j) i = i +1;
    while (x &lt; elements[j] &amp;&amp; i &lt; j) j = j - 1;

    int tmp;

    while (i &lt; j) {
      tmp = elements[i];
      elements[i] = elements[j];
      elements[j] = tmp;

      i = i + 1;
      j = j - 1;

      while (elements[i] &lt;= x &amp;&amp; i &lt; j) i = i +1;
      while (x &lt; elements[j] &amp;&amp; i &lt; j) j = j - 1;

      p = j;
    }

    print("P: " + elements[p]);
    print("Partitioned Array: " + Arrays.toString(elements));
  }
}
Unless it is a homework for sort algorithm study :


Manage ArrayList and load your list of number,
put all number&lt;=x in a new ArrayList,
delete them from the original ArrayList,
finish with .addAll(..), to concatenate if needed.


Knowing that VM is optmized, it would be interesting to compare performance of this approach with your one.