Sort An Integer Array With the Quicksort Algorithm And Java

Circling back to data structures and algorithms, we’re now going to take a look at the efficient sorting algorithm known as Quicksort.

Quicksort via Wikipedia:

Sometimes called partition-exchange sort, is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

The idea behind Quicksort is to take a large array of values and divide it into two smaller arrays, doing this recursively, and swapping elements.

This is one of the fundamental algorithms you’ll learn in any computer science course. It is also a very good question that could be asked in a job interview for an engineering type position. I’m going to help you through it using Java.

Below is a valid implementation of the Quicksort algorithm in Java.

public class Sorting {

    public Sorting() { }

    public void quickSort(int[] arr, int left, int right) {

        int pivotIndex = left + (right - left) / 2;
        int pivotValue = arr[pivotIndex];

        int i = left, j = right;

        while(i <= j) {

            while(arr[i] < pivotValue) {
                i++;
            }

            while(arr[j] > pivotValue) {
                j--;
            }

            if(i <= j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }

            if(left < i) {
                quickSort(arr, left, j);
            }

            if(right > i) {
                quickSort(arr, i, right);
            }

        }

    }

}

What we’re doing in the above code is picking a pivot value in the middle of our array. We then loop around the pivot on both sides while checking to see if the left value is less than the pivot and the right value greater than the pivot. When these scenarios are inaccurate swap values on both sides of the pivot. The process will repeat, continually pointing at smaller sections of the array and sorting them.

So how do we see this algorithm in action? Create a driver file called MainDriver.java and add the following code:

public class MainDriver {

    public static void main(String[] args) {

        Sorting s = new Sorting();
        int[] arr = new int[] {5, 3, 7, 2, 1, 6};

        s.quickSort(arr, 0, arr.length - 1);

        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

}

In the above code we create an instance of our class as well as an unsorted array of numeric values. The quickSort(arr, left, right) function will take our unsorted array as well as both endpoints being zero and the length minus one because it is a zero based array. To prove that the sort worked, we will then print it out on the screen.

Go ahead and test it! If you’re comfortable with the terminal or command prompt, navigate to the same directory as your code and run the following:

javac MainDriver.java
java MainDriver

The above will compile our two class files, then run the main function.

Quicksort is a solid algorithm because the time complexity is not too bad for its simple implementation. In the best scenario, we are looking at a time complexity of O(nlogn) where in our worse scenario we are looking at a time complexity of O(n^2).

If you think you can best my implementation or have been asked something similar in an interview, please share in the comments section.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.