Partitioning array elements into two subsets

Question

Problem:

Given a randomly ordered array of n-elements, partition the elements into two subsets such that elements <= 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 < 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 ->    ||   <- 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

1. Extend the left and right partitions inward exchanging wrongly placed elements.

2. Exchange can be done by the standard technique

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

3. Moving inwards from left and right can be done by,

   from left to right: while(a[i] <= x) i = i + 1;

   from right to left: while(x < 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] <= x) i = i + 1;
while(x < a[j]) j = j - 1;

Algorithm (it is based on R. G. Dromey's How to solve it by computer):

1. Establish an array \$a[1...n]\$ and partition value x.

2. Move the two partitions towards each other until a wrongly placed pair of elements is encountered.

3. 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
4. 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] <= x && i < j) i = i +1;
    while (x < elements[j] && i < j) j = j - 1;

    int tmp;

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

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

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

      p = j;
    }

    print("P: " + elements[p]);
    print("Partitioned Array: " + Arrays.toString(elements));
  }
}

Answer 1

Unless it is a homework for sort algorithm study :

• Manage ArrayList and load your list of number,
• put all number<=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.