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