Partition an Array is non trivial
Given an array of integer int[] arr = {2, 1, 4, 3, 2}, choose a pivot, and partition the array into left and right so that all the number on the left is less or qual to the pivot and all the number on the right is greater than the pivot
int[] arr = {2, 1, 4, 3, 2}
1. Choose last element as pivot → 2
2. left array {2, 1, 3} less or equal than pivot
3. right array {4} greater than pivot
→ {2, 1, 3} {2} {4}
left pivot right
Approach 1
1. Create temporary array with same length as original array
0. Choose the most right element as pivot
2. Create left index and right index
3. Iterate through the origin array
1. If the element is less or equal the pivot
1. add the element to the left side of temporary array
else add the element to the right side of temporary array
int partition(int[] arr, int lo, int hi){
int len = arr.length;
int pivot = arr[hi]; // use last elem as pivot
int[] retArr = new int[len];
int leftInx = 0; // leftInx++ =>
int rightInx = len - 1; // rightInx-- <=
int k = lo;
while(leftInx != rightInx){
retArr[arr[k] <= pivot ? leftInx++ : rightInx--] = arr[k++];
}
// pivot index == leftInx == rightInx
// pivot position
retArr[leftInx] = pivot
// copy retArr back to arr
for(int i = 0; i < len; i++){
arr[lo + i] = retArr[i];
}
return leftInx;
}
Approach 2, Use only swap operation
This approach does not need temporary buffer. It only uses swap operation