Toady, I read about bolts and nuts problem. The method is similar to quicksort. But one difference is that, we should partition the array by an uncertain pivot. It means we don’t know where the pivot is in the array.
The normal way should be traverse the array for one time, and found the position of pivot. Then do quicksort as usual. By that, it can finish it in O(n) time, yet with traversal on the array for 2 times.
But I believe there is way that it only traverse for one time. After done hours research, I found this method. Which I should thank kartik kukreja for providing me this idea, link. By this method, we can finish it by one trip on the array.
The idea is that we keep a ‘higher group’ in the traversal, which means those elements which are larger than the pivot. And we record the start position of the ‘higher group’. Let me take an example:
Assume we want to partition the following array by a pivot of 5. If current array is:
3 9 7 6 2 1 5 4 8
Always maintain the ‘higher group’ in the one trip.
Next, we need to judge 2. Since 2 is less than 5, so we swap 2 with the first element of the higher group. So the next array is:
3 2 7 6 9 1 5 4 8
By this, higher group moves forward by 1. We should record the 1st element position in higher group.
Then next:
3 2 1 6 9 7 5 4 8
When we encounter the pivot 5, we swap it with the last element. So the next is:
3 2 1 6 9 7 8 4 5
After we’ve done with 2nd to last element, it is like this:
3 2 1 4 9 7 8 6 5
Now, we swap the last element(pivot) with 1st element position in higher group. The final result would be:
3 2 1 4 5 7 8 6 9
This is the code:
public static int partition(int[] arr, int low, int high, int pivot) {
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] < pivot){
swap(arr, i, j);
i++;
} else if(arr[j] == pivot){
swap(arr, j, high);
j--;
}
}
swap(arr, i, high);
return i;
}
public static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}