Quicksort Algorithm with Java

The Quicksort algorithm is one of the most effective for Java and any other programming languages. It’s used behind the scenes in many JDK API methods for example.

Choosing the pivot with the Quicksort Algorithm

The first step to do the Quicksort algorithm is to choose the pivot number. The pivot number ideally should be a number that when the array is fully sorted would be right in the middle.

It doesn’t need to be exactly the number in the middle of the array. Instead, we try to choose an element that will be close to it. A technique that is commonly used for that is the median of three. The idea is that we pick the first, middle, and last elements of the array, sort them, and finally choose the element in the middle. If the pivot element is in the middle or close to it, then we will have a time complexity of O(n log n).

Alternatively, we can simply pick the first or last elements of the array. But if the element is the smallest or greatest of the array, then the sorting will have the worst-time complexity of O(n2).

Creating Partitions with the Quicksort Algorithm

When choosing the pivot it’s possible to create partitions in the array. The objective of the partition is to break the array in the middle with elements lower than the pivot on the left and elements greater than the pivot on the right.

When the partition is being created the elements will also be sorted. The partition method will be invoked recursively until all elements are fully sorted.

Let’s see how the process of the Quicksort algorithm works in the following:

import java.util.Arrays;

public class Quicksort {

  static void quickSort(int[] array, int lowIndex, int highIndex) {
    if (lowIndex < highIndex) {
      int partitionIndex = partition(array, lowIndex, highIndex);

      quickSort(array, lowIndex, partitionIndex - 1);
      quickSort(array, partitionIndex + 1, highIndex);
    }
  }

  static int partition(int[] array, int lowIndex, int highIndex) {
    int pivot = array[highIndex];
    int i = (lowIndex - 1);

    for (int j = lowIndex; j < highIndex; j++) {
      if (array[j] < pivot) {
        i++;
        swap(array, i, j);
      }
    }
    swap(array, i + 1, highIndex);
    return (i + 1);
  }

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

  public static void main(String[] args) {
    int[] array = { 10, 3, 2, 0, 9, 7 };
    int n = array.length;

    quickSort(array, 0, n - 1);
    System.out.println(Arrays.toString(array));
  }
}

Output:
[0, 2, 3, 7, 9, 10]

Code analysis:

Notice that the quickSort method will have two pointers, the lowIndex with the lowest index of the array and highIndex with the highest index of the array.

Then we will invoke the partition method that will first choose the pivot number, which in our case it’s the last element from the array to facilitate the understanding of the algorithm. Then, the elements that are lower than the pivot will go to the left, and the elements that are greater than the pivot will go to the right.

Notice that when the partition happens obviously the whole array won’t be sorted. Therefore, to fully sort the array it’s necessary to recursively invoke the partitioned array from the left and right sides, and do the same process until the array is fully sorted.

Creating Partition with Left and Right Pointers

This is another interesting approach to sorting the partition elements for the Quicksort that is easier to be absorbed and more didactic.

The idea is the same from the other algorithm, to keep elements lower than the pivot on the left and the greater element on the right.

In the following code, we create a while looping to check if the leftPointer is greater than the rightPointer. Also, if elements from the left of the array are lower or equal to the pivot the leftPointer will be incremented.

If the elements from the right of the array are greater or equal to the pivot the rightPointer will be decremented.

Once the leftPointer has an element that is greater or equals to the pivot and the rightPointer has an element that is lower or equal to the pivot, the elements will be swapped.

The only thing that makes this algorithm a bit confusing is the last if check. However, it’s necessary because the leftPointer element might be greater than the highIndex. If that’s true, the elements will be swapped, otherwise, the leftPointer will have the highIndex:

  static int partition(int[] array, int lowIndex, int highIndex) {
    int pivot = array[highIndex];
    int leftPointer = lowIndex;
    int rightPointer = highIndex - 1;

    while (leftPointer < rightPointer) {
      while (array[leftPointer] <= pivot && leftPointer < rightPointer)
        leftPointer++;
      while (array[rightPointer] >= pivot && leftPointer < rightPointer)
        rightPointer--;
      swap(array, leftPointer, rightPointer);
    }

    if(array[leftPointer] > array[highIndex])
      swap(array, leftPointer, highIndex);
    else
      leftPointer = highIndex;

    return leftPointer;
  }

Watch the following video from Coding with John for a full explanation of the above algorithm:

Summary

In this article, we’ve seen how the Quicksort algorithm works and what are the most important steps to accomplish the sorting. Therefore, let’s recap some important points:

• When using the Arrays.sort() method from the JDK code, the Quicksort is used behind the scenes.
• It’s required to choose the pivot to partition the array. Ideally, the pivot should be the number in the middle.
• When the pivot is the greatest or the lowest number in all partitions, the algorithm will have the worst-case scenario. Therefore, the time complexity will be O(n2).
• We can choose the first, last, random element. Also, we can use the median of three strategy to choose the number in the middle from the first, middle, and last elements.
• The partitions will be sorted recursively on each method invocation. When the partitions are small enough there won’t be any remaining elements to be sorted. Therefore, the array will be already sorted.