Partition an Array with a pivot 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
Best Approach 1 with BUG: Use only swap operation
NOTE: The approach contains a BUG if you use the following function inside your Quick Sort
This approach does not need temporary buffer. It only uses swap operation
public static int partitionArr(Integer[] arr, int lo, int hi){
int len = arr.length;
int bigInx = lo;
Integer pivot = arr[hi];
for(int i = 0; i < len; i++){
if(arr[i] <= pivot){
int tmp = arr[i];
arr[i] = arr[bigInx];
arr[bigInx] = tmp;
if(i < len - 1)
bigInx++;
}
}
return bigInx;
}
Best Approach 1 with NO BUG: Use only swap operation
public static int partitionArr2(Integer[] arr, int lo, int hi){
int len = arr.length;
int bigInx = lo;
Integer pivot = arr[hi];
for(int i = lo; i <= hi; i++){
if(arr[i] <= pivot){
int tmp = arr[i];
arr[i] = arr[bigInx];
arr[bigInx] = tmp;
if(i < hi)
bigInx++;
}
}
return bigInx;
}
We can use above partitionArr2 on Quick Sort Algorithm.
The idea is similar as preOrder traveral
public static void quickSort(Integer[] arr, int lo, int hi){
if(lo < hi){
int pivotInx = partitionArr2(arr, lo, hi);
quickSort(arr, lo, pivotInx - 1);
quickSort(arr, pivotInx + 1, hi);
}
}
Approach 2, Use a tmp array
0. Create temporary array with same length as original array
1. 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;
}