Partitioning is the process by which we reorder our array so that elements with a value less than our pivot are moved to the left of the pivot and those with a larger value are moved to the right (see Figure 2.2). There are numerous manners in which we can do this. Here, we will describe an easy-to-understand scheme known as Lomuto Partitioning.
Take a look at this diagram:
To get a good perception on this partitioning scheme, it is best to simplify what the algorithm is doing in five simple steps, as follows:
- Pick the right most element of the array as the pivot.
- Start from the left and find the next element that is larger than the pivot.
- Swap this element with the next, which is smaller than pivot element.
- Repeat steps 2 and 3 until no more swapping is possible.
- Swap the first item which is larger than the pivot's value with the pivot itself.
To perform efficient partitioning using the steps mentioned, we can make use of two pointers, one pointing to the first item larger than the pivot value and the other used to search for the value that is smaller than pivot value.
In the following code, these are the integer pointers named x and i, respectively. The algorithm starts by choosing the pivot as the last item on the input array. It then processes the array from left to right in a single pass using the variable i. If the element currently being processed at i is smaller than the pivot, x is incremented and swapped. Using this technique, variable x is either pointing to a value larger than the pivot or the value of x is the same as i, in which case swapping will not modify the array. Once the loop exits, we perform the final step of swapping the first item that is larger than the pivot's value with the pivot. The code is as follows:
private int partition(int[] numbers, int start, int end) {
int pivot = numbers[end];
int x = start - 1;
for (int i = start; i < end; i++) {
if (numbers[i] < pivot) {
x++;
swap(numbers, x, i);
}
}
swap(numbers, x + 1, end);
return x + 1;
}