Quicksort in JAVA

Introduction

Sorting is one of the fundamental techniques used in solving problems, especially in those related to writing and implementing efficient algorithms.

Usually, sorting is paired with searching - meaning we first sort elements in the given collection, then search for something within it, as it is generally easier to search for something in a sorted, rather than an unsorted collection, as we can make educated guesses and impose assumptions on the data.

There are many algorithms that can efficiently sort elements, but in this guide we'll be taking a look at the theory behind as well as how to implement Quicksort in Java.

Quicksort in Java

Quicksort is a sorting algorithm belonging to the divide-and-conquer group of algorithms, and it's an in-place (no need for auxiliary data structures), non-stable (doesn't guarantee relative order of same-value elements after sorting) sorting algorithm.

The divide-and-conquer algorithms recursively break down a problem into two or more sub-problems of the same type, making them simpler to solve. The breakdown continues until a problem is simple enough to be solved on it's own (we call this the base case).

This algorithm has been shown to give the best results when working with large arrays, and on the other hand when working with smaller arrays an algorithm like Selection Sort might prove more efficient.

Quicksort modifies the base idea of Selection Sort, so that instead of a minimum (or a maximum), in every step of the way an element is placed on the spot it belongs on in the sorted array.

This element is called the pivot. However, if we wanted to use the divide-and-conquer approach and reduce the problem of sorting the array to a smaller group of two sub-arrays we need to abide by the following: while we're placing our pivot at it's spot in the array we need to group the rest of the elements in two smaller groups - the ones left of the pivot are lesser or equal to it, and the ones on the right are bigger than the pivot.

This is actually the key step of the algorithm - called partitioning, and implementing it efficiently is a must if we want our Quicksort to be efficient as well.

Before discussing how Quicksort works, we should address how we choose which element is the pivot. The perfect scenario is that we always choose the element that splits the array in exact halves. However, since this is almost impossible to achieve, we can approach this problem in a few different ways.

For example, the pivot can be the first or the last element in the array (or a sub-array) we're currently processing. We can pick a median element as the pivot, or even choose a random element to play the role.

We have a variety of ways of accomplishing this task, and the approach we'll be taking in this article is to always choose the first (that is, leftmost element of the array) as the pivot. Now let's jump into an example and explain how it all works.

Visualization of Quicksort

Suppose we have the following array:

In this example, the pivot in the first iteration will be 4, since the decision is to pick the first element of the array as the pivot. Now comes in the partitioning - we need to place 4 at the position it will be found in the sorted array.

The index of that position will be 2, so after the first partitioning our array will look like this:

This is to be expected - whenever we partition an array that isn't the base case (that is of size 1), the elements are grouped in a random order.

The important thing is what we discussed earlier: the elements left of the pivot are lesser or equal, and the elements on the right are bigger than the pivot. That isn't to say that they can't be sorted in the first grouping - while unlikely it can still happen.

We continue on, and see that here divide-and-conquer kicks in - we can break down our original problem into two smaller ones:

For the problem on the left we have an array of size 2, and the pivot element will be 2. After positioning the pivot at its place (at the position 1), we get an array [1, 2] after which we have no more cases for the left side of the problem, since the only two subcases of [1, 2] are [1] and [2] which are both base cases. With this we finish with the left side of subcases and consider that part of the array sorted.

Now for the right side - the pivot is 13. Since it's the largest of all of the numbers in the array we're processing, we have the following setup:

Unlike earlier when the pivot broke down our array into two subcases, there's only one case here - [8, 10, 7, 5]. The pivot now is 8 and we need to bring it to the position 5 in the array:

The pivot now splits the array in two subcases: [7, 5] and [10]. Since [10] is of size 1, that is our base case and we don't consider it at all.

The only subarray left is the array of [7, 5]. Here, 7 is the pivot, and after bringing it to its position (index 4), to the left of it at the position 3 is only 5. We have no more subcases and this is where the algorithm ends.

After running Quicksort, we have the following sorted array:

This approach also accounts for duplicates in the array, since all of the elements left of the pivot are lesser or equal than the pivot itself.

Implementing Quicksort in Java

With a good intuition of how Quicksort works - we can follow through with an implementation. First of all, we'll go through the main part of the program that will be running Quicksort itself.

Since Quicksort is a divide-and-conquer algorithm, it's naturally implemented recursively, although you could do it iteratively as well (any recursive function can also be implemented iteratively) - though, the implementation is not as clean:

static void quicksort(int[] arr, int low, int high){
    if(low < high){
        int p = partition(arr, low, high);
        quicksort(arr, low, p-1);
        quicksort(arr, p+1, high);
    }
}

The partition(arr, low, high) method partitions the array, and upon it's execution the variable p stores the position of the pivot after the partitioning.

This method is only invoked when we're processing arrays that have more than one element, hence the partitioning only takes place if low < high.

Since Quicksort works in-place, the starting multiset of elements that can be found within the array stays unchanged, but we've accomplished exactly what we aimed to do - group up smaller or equal elements left to the pivot, and bigger than the pivot on the right.

Afterwards, we call the quicksort method recursively twice: for the part of the array from low to p-1 and for the part from p+1 to high.

Before we discuss the partition() method, for the sake of readability we'll implement a simple swap() function that swaps two elements in the same array:

static void swap(int[] arr, int low, int pivot){
    int tmp = arr[low];
    arr[low] = arr[pivot];
    arr[pivot] = tmp;
}

Now, let's dive into the code for the partition() method and see how it does what we've explained above:

static int partition(int[] arr, int low, int high){
    int p = low, j;
    for(j=low+1; j <= high; j++)
        if(arr[j] < arr[low])
            swap(arr, ++p, j);

    swap(arr, low, p);
    return p;
}

When the for loop is done executing, j has value of high+1, meaning the elements on arr[p+1, high] are higher or equal than the pivot. Because of this it's required we do one more swap of the elements on the position low and p, bringing the pivot at its correct position in the array (that is, position p).

The last thing we need to do is run our quicksort() method and sort an array. We'll be using the same array as we did in the example before, and calling quicksort(arr, low, high) will sort the arr[low, high] part of the array:

public static void main(String[] args) {
    int[] arr = {4, 8, 1, 10, 13, 5, 2, 7};
    // Sorting the whole array
    quicksort(arr, 0, arr.length - 1); 
}

This results in:

1, 2, 3, 4, 5, 7, 8, 10, 13

Complexity of Quicksort

Quicksort, as well as other algorithms that apply the divide-and-conquer tactic, has a time complexity of O(n log n). However, compared to something like Merge Sort, which has the worst-case time complexity of O(n log n), Quicksort can theoretically have the worst-case of O(n^2).

The complexity depends on how much time we take to efficiently choose a pivot, which can sometimes be as difficult as sorting the array itself, and since we expect the choosing of a pivot to be O(1) we usually can't guarantee that in every step of the way we'll be choosing the best pivot possible.

Even though the worst-case of Quicksort can be O(n^2), most of the pivot-choosing strategies are implemented such so they don't deter the complexity too much, which is why the average complexity of Quicksort is O(n log n). It's widely implemented and used, and the name itself is an homage to its performance capabilities.

On the other hand, where Quicksort hands-down beats Merge Sort is the space complexity - Merge Sort requires O(n) space because it uses a separate array for merging, while Quicksort sorts in-place and has the space complexity of O(1).

Conclusion

In this article we've covered how the Quicksort algorithm works, how it's implemented and discussed its complexity. Even though the choice of the pivot can "make or break" this algorithm, it's usually considered as one of the most efficient sorting algorithms and is widely used whenever we have a need for sorting arrays with huge amounts of elements.