Thursday, 20 August 2015

Partition Array


Given an array arr = {1, 3, 5, 7, 2, 4, 6, 8} and index 5 (arr[5] has element 4). Partition array such that all elements less than 4 are left side of it and greater than 4 are right side of it.
import java.util.Arrays;
import java.util.Objects;

public class MoveElem {
 private int[] arr;

 private void swap(int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
 }

 public void moveElements(int arr[], int position) {
  Objects.nonNull(arr);

  if (position > arr.length - 1)
   throw new IllegalArgumentException("position " + position
     + " should less than array length " + arr.length);

  this.arr = arr;

  swap(0, position);
  partition(0, arr.length);

 }

 private void partition(int low, int high) {
  int i = low + 1;
  int pivot = arr[low];

  for (int j = low + 1; j < high; j++) {
   if (arr[j] < pivot) {
    swap(i, j);
    i++;
   }
  }

  i--;
  swap(low, i);
 }

 public static void main(String args[]) {
  MoveElem moveElem = new MoveElem();

  int arr1[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr2[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr3[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr4[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr5[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr6[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr7[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
  int arr8[] = { 1, 3, 5, 7, 2, 4, 6, 8 };

  moveElem.moveElements(arr1, 0);
  System.out.println(Arrays.toString(arr1));

  moveElem.moveElements(arr2, 1);
  System.out.println(Arrays.toString(arr2));

  moveElem.moveElements(arr3, 2);
  System.out.println(Arrays.toString(arr3));

  moveElem.moveElements(arr4, 3);
  System.out.println(Arrays.toString(arr4));

  moveElem.moveElements(arr5, 4);
  System.out.println(Arrays.toString(arr5));

  moveElem.moveElements(arr6, 5);
  System.out.println(Arrays.toString(arr6));

  moveElem.moveElements(arr7, 6);
  System.out.println(Arrays.toString(arr7));

  moveElem.moveElements(arr8, 7);
  System.out.println(Arrays.toString(arr8));
 }
}


Output
[1, 3, 5, 7, 2, 4, 6, 8]
[2, 1, 3, 7, 5, 4, 6, 8]
[4, 3, 1, 2, 5, 7, 6, 8]
[6, 3, 5, 1, 2, 4, 7, 8]
[1, 2, 5, 7, 3, 4, 6, 8]
[1, 3, 2, 4, 5, 7, 6, 8]
[1, 3, 5, 2, 4, 6, 7, 8]
[1, 3, 5, 7, 2, 4, 6, 8]


No comments:

Post a Comment