How to Use the partition Method for Quicksort in Java

The hard part of the Java Quicksort technique is the partition method. This method accepts two parameters: the low and high indexes that mark the portion of the array that should be sorted. The basic outline of the partition method goes something like this:

  1. Pick a pivot point.

  2. Move all elements that are less than the pivot point to the left side of the partition.

  3. Move all elements that are greater than the pivot point to the right side of the partition.

  4. Return the index of the pivot point.

The most common technique for partitioning the array is to maintain two index variables, named i and j, that work from both ends of the array toward the center.

First, i starts at the beginning of the array and moves forward until it encounters a value that’s greater than the pivot value. Then j starts at the opposite end of the array and moves backward until it finds a value that’s less than the pivot point.

At that point, the partition method has a value that’s greater than the pivot point on the left side of the array and a value that’s less than the pivot point on the right side of the array. So it swaps them.

Next, the cycle repeats: i is incremented until it finds another value that’s greater than the pivot value, j is decremented until it finds another value that’s less than the pivot value, and the elements are swapped. This process repeats until j is less than i, which means that the indexes have crossed and the partitioning is done.

Here’s some code that puts everything together:

public static int partition(int low, int high)
{
 int pivot = a[low];
 int i = low - 1;
 int j = high + 1;
 while (i < j)
 {
  for (i++; a[i] < pivot; i++);
  for (j--; a[j] > pivot; j--);
  if (i < j)
   swap(i, j);
 }
 return j;
}

Notice that in this code, the array being sorted is a static int array named a. The low and high ends of the partition to be partitioned are passed in as parameters, and the method starts by choosing the first element in the partition as the value for the pivot point. Next, it initializes the index variables i and j from the parameters.

Notice that 1 is subtracted from the low value and that 1 is added to the high value. The index variables take one step back from the array before the looping starts so they can get a good start.

The while loop is used to indicate when the partitioning is finished. It repeats as long as i is less than j. After these index variables stop, the partitioning is done, and the value of j is returned to indicate the index point that divides the left partition from the right partition.

In the body of the while loop are two strange bodyless for loops. These for loops don’t have bodies because their only purpose is to move their index values until they find a value that’s either less than or greater than the pivot value.

The first for loop increments the i index variable until it finds a value that’s greater than the pivot point. This for loop finds the first value that might need to be moved to the other side of the array.

Next, the second for loop decrements the j index variable until it finds a value that’s less than the pivot point. So this loop finds a value that may need to be swapped with the value found by the first for loop.

Finally, the if statement checks whether the indexes have crossed. Assuming that they haven’t, a swap method is called to swap the elements. The swap method is mercifully simple:

public static void swap(int i, int j)
{
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

This method moves the i element to a temporary variable, moves the j element to the i element, and then moves the temporary variable to the j element.

  • Add a Comment
  • Print
  • Share
blog comments powered by Disqus
Advertisement

Inside Dummies.com