Java Quicksort: A Beginner’s Guide

It can be difficult to wrap your head around the quicksort sorting algorithm. It’s not as intuitive as other sorts like an insertion sort or a bubble sort.

Quicksorts are an efficient way of sorting smaller lists. In this guide, we’re going to talk about how to build a quicksort in Java. We’ll walk through an example quicksort to get you started.

Without further ado, let’s begin!

What is a Java Quicksort?

A quicksort is a sorting algorithm that devices an array into subarrays which are recursively called to sort each element in the list.

Slow down! In a quicksort, we start by selecting a number called a pivot. We compare this pivot number to every number in the list.

If an item is greater than the pivot, it is moved to the right of the pivot; otherwise, it is moved to the left. Then, all the items greater than and lesser than the pivot are divided into two lists. The sorting algorithm repeats until every item has been the pivot at least one time.

The quicksort is more advanced than other sorts. It’s best to try out this sort only if you have a good understanding of recursion and more basic sorting algorithms. 

The quick sort is more efficient than a merge sort when sorting smaller arrays. On larger arrays, a merge sort is more efficient.

How Does a Quicksort Work?

We can’t begin to write a Java quicksort without first walking through the algorithm. We’ll take it step-by-step so that you can follow along.

The first step in a quicksort is to select a pivot from an array. We’re going to select the last item in a list as our pivot for convenience. The pivot can be any item in an array.

5 is our pivot number.

Then, the items smaller than the pivot are moved to the left of the pivot. The items greater than the pivot are moved to the right:

Next, we divide the list into two smaller lists. The items to the left of the pivot make one list. The items to the right of the pivot make another list. The pivot is sorted so it does not move down into a new list.

We perform the same process as above on both of these small lists until each is sorted. The numbers in bold are the pivot numbers.

If we combine all of our values, we get a sorted list:

Our list has been successfully sorted!

Quick sorts use a recursive algorithm. This is because each list is divided into sublists on which the same quicksort is performed. Because quicksorts use recursion, they use the divide-and-conquer approach to sort a list.

The initial list is sorted based on the value of each number relative to the pivot number. Next, it is divided into subarrays. These subarrays are then subject to the same sorting algorithm using a recursive function. This is where the conquer step comes in.

How to Build a Java Quicksort

Now that you’re familiar with how a quicksort works, we can discuss how to implement it in Java. We’ll start by importing the Arrays library and defining a class for our code:

import java.util.Arrays;

class QuickSort {
}

The Arrays library allows us to print out the value of an array. Next, we’re going to define a function called “prepare”. This function will move elements based on their value relative to the pivot. This process is called preparing, or partitioning, our data.

Elements greater than the pivot will move to the right of the pivot. Elements less than the pivot will move to the left.

int prepare(int numbers[], int low, int high) {
	int pivot = numbers[high];
	int item = low - 1;

	for (int i = low; i < high; i++) {
		if (numbers[i] <= pivot) {
			item++;
			int swap = numbers[item];
			numbers[item] = numbers[i];
			numbers[i] = swap;
		}
	}

	int swap = numbers[item + 1];
	numbers[item + 1] = numbers[high];
	numbers[high] = swap;
	return (item + 1);
}

We start by defining the pivot number. This number is equal to the last item in our list. Next, we use a for loop to iterate through every item in the “numbers” list. If a number is lower than the pivot, it is moved after the pivot number. Otherwise, the number is moved before the pivot number.

We’re not done yet. This function only prepares our data. We’ve still got to perform the actual sort. Let’s define a new function for our sort:

void sorting(int numbers[], int low, int high) {
	if (low < high) {
		int pivot = prepare(numbers, low, high);

		sorting(numbers, low, pivot - 1);
		sorting(numbers, pivot + 1, high);
	}
}

As long as the value of “low” is less than “high”, the contents of our sorting() method runs. This ensures that our sorting algorithm stops when our list is sorted.

The sorting() function calls our prepare() function to prepare the array. Next, it calls itself again twice. The first time, sorting() is called to sort the lower half of the list. The second time, sorting() sorts the upper half of the list.

This happens until every item in the list is sorted. Because the sorting() function calls itself, it is considered a recursive function.

The final step is to write a main program that calls our sorting() function:

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

public static void main(String args[]) {
	int[] numbers = { 12, 8, 3, 1, 0, 5 };
	int to_sort = numbers.length;

	QuickSort new_sort = new QuickSort();
	new_sort.sorting(numbers, 0, to_sort - 1);
	
	System.out.println(Arrays.toString(numbers));
}

We define a variable called “numbers” which contains the list of numbers we want to sort. We use the .length method to calculate the length of this list. Next, we initialize a new instance of our QuickSort class. We then call the sorting() method to sort our list of numbers.

The “to_sort – 1” is specified as the high value in the sorting() function. This is because lists are indexed from 0 and so we need to subtract one from the length of the list so that we don’t try to sort a value that does not exist.

Next, we print the sorted array to the console. The Arrays.toString() method converts the value of “numbers” into a string that Java can print to the console.

Let’s run our code altogether:

[0, 1, 3, 5, 8, 12]


Our list has been sorted!

Complexity Review

We’re not done yet. We have to review the complexity of the quicksort algorithm before concluding. In the best and average cases, the quicksort performs at O(n*log n).

In the worst case, the quicksort performs at O(n^2). This happens when the pivot element is either the largest or smallest item in a list.

Conclusion

The quicksort algorithm is an efficient method at sorting lists. While it does not outperform the merge sort on larger lists, it is powerful when used on smaller lists.

Quicksorts are implemented using a recursive function. This is a function that calls itself repeatedly until a problem has been solved.
Now you’re ready to implement a quicksort algorithm in Java like an expert!