QuickSort Implementation In Java

This interactive article will cover a Java implementation of the QuickSort algorithm.

Overview

QuickSort is a sorting algorithm that is based on the divide-and-conquer strategy. That means like MergeSort, the input array is partitioned into smaller parts to be rearranged. Unlike the approach in MergeSort, where we created new arrays at each division, we will do all the sorting in-place – meaning we are going to refer to sub-arrays by starting and ending indices of the original array. This saves space!

This article walks through the implementation of the QuickSort algorithm in Java. The parts we will cover are:

  • Writing the partition process, which takes the given part of the array bounded by a left and right pointer, and swaps elements to the correct side of a pivot element. The process also returns the partition point for the next recursive calls of QuickSort.
  • Setting up the condition for the base case and recursive step of QuickSort.
  • Writing the recursive QuickSort calls on both the left side and right side of the partition.
  • Running our implementation with helpful print statements

Partitioning

Partitioning is the meat of the QuickSort algorithm. It’s here that we compare the elements and swap them. We will write this as its own partition() method that takes the original array, a left pointer (index), and a right pointer (index). In the first call of the partition() function, leftPointer will be 0 and rightPointer will be arr.length - 1.

public int partition (int[] arr, int leftPointer, int rightPointer) } }

At the beginning of the function, we should choose an element of the array as our pivot element. Common choices in QuickSort implementations are: the first element (element at leftPointer), last element (at rightPointer) and middle element (at the average of leftPointer and rightPointer). We’ll go with the middle element in our partition() implementation.

The goal is to have all elements less than the pivot element on the left side of it (not necessarily sorted), and elements greater than it be on the right side. leftPointer and rightPointer step in opposite directions to compare each element to the pivot element. If there are elements on the wrong side of the pivot, we should swap those elements.

Let’s walk through how the partition() function should run on a given array.

Walk-through of Partition

Let’s use this array to demonstrate:

[ 39, 15, 24, 35, 76, 19 ]

Note: We will use L to indicate where the leftPointer is, R to indicate rightPointer, and P to indicate the pivot element, which is the value of the middle element at the beginning of partition().

At the start, arr[leftPointer] as indicated by L is 39, arr[rightPointer] as indicated by R is 19, and the pivot middle element P is 24.

[ 39, 15, 24, 35, 76, 19 ] L P R

Let’s compare L with the pivot element. As long as L is less than the pivot, meaning that it is on the correct side of the pivot, we want to move the L forward one step to the right. Here, L does not increment because it is greater than the pivot. This will be the element involved in the first swap.

39 > 24. That means we want it on the other side of the pivot. L stays [ 39, 15, 9, 35, 76, 19 ] L P R

Now let’s do the same with R and the pivot. We are moving R to the left as long as the current element is greater than the pivot element.

R also stays the same since 19 < 24. Both L and R pointers are paused, ready for the elements to be swapped. [ 39, 15, 24, 35, 76, 19 ] L P R

We should swap the elements at L and R. Note: in some instances, either the left or right pointer might pause at the pivot element. The pivot element’s position can be swapped with another element, but the pivot value will stay the same.

[ 19, 15, 24, 35, 76, 39 ] L P R

The while loop should start again. L increments while the element is less than the pivot. R decrements while the element is greater than the pivot. The pointers are paused here.

[ 19, 15, 24, 35, 76, 39 ] L R P

If the left index is now equal to the right index, the while loop ends. We return the left index L as the partition point. Note that the partition point returned will only sometimes equal the index of the pivot element.

We illustrated step-by-step what should happen during the partition process, so we can interpret the steps into pseudocode below. Make sure to read through it carefully and go through the example above again.

int partition (int[] arr, int leftPointer, int rightPointer) { Pivot = value of arr at (average of leftPointer and rightPointer, rounded down) While leftPointer and rightPointer don't meet (i.e. the pointers haven't hit all the elements yet) Increment leftPointer until element pointed to is > pivot Decrement rightPointer until element pointed to is < pivot If leftPointer less than rightPointer Swap elements at leftPointer and rightPointer return leftPointer as the partition point }

Note that we already have a swap() function from previous sorting lessons.