In this post we will take a look on a working Java code example of QuickSort algorithm. We will also clarify the Quicksort by itself, describing the main steps of implementing it in Java language.

About QuickSort

QuickSort is a very popular algorithm for sorting. In most cases it is quicker than Insertion sort and Bubble sort (in average cases it’s complexity is O(n log n)). But it is also a little bit harder to implement.

The QuickSort is not really sophisticated. Its main principle is the partition-exchange. At first, we need to choose the pivot. In our case it will be a last element in the array. The next part is to separate items that are less than pivot and greater than pivot. The same algorithm should be repeated for sub-arrays from the left of a pivot and from the right.

QuickSort Java code implementation

We need to create only one class. Let’s call it QuickSort.java. Here is the full code listing:

import java.util.Random;

public class QuickSort {
    public  int [] arr;

    public QuickSort(int[] arr) {
        this.arr = arr;
    }

    public void sort() {
        sort(0, arr.length - 1);
    }

    public void sort(int first, int last){
        // this is the point when we break the recursion
        if (last - first < 1) return;

        int pivot = arr[last]; // the pivot is a last item of array
        System.out.println("Pivot: " + pivot);
        int index = first - 1;
        // after this loop array will be reorganized:
        // items <= pivot will be on the left of pivot; items greater than pivot - on the right;
        for (int i = first; i<last; i++) {
            if (arr[i] <= pivot) {
                swap(++index, i);
            }
            printArray(); // this line prints out the array on each iteration
        }
        swap(index + 1, last);

        // recursively running same algorithm for 2 sub-arrays:
        // smaller than pivot and larger than pivot
        sort(first, index);
        sort(index + 2, last);

    }

    public  void swap (int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }

    private void printArray() {
        for (int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort(initRandomArray(10, 10));
        quickSort.sort();
    }

    private static int[] initRandomArray(int size, int range) {
        int [] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = new Random().nextInt(range);
        }
        return arr;
    }

}

Explanation

The main logic is located inside the sort(int first, int last) method. You can see some utility methods like swap() – replaces 2 elements in array, printArray() – simply prints the array in the console, initRandomArray() – generates the random data.

The sort() method implements the Quicksort algorithm code like in the description above. If the logic is too complicated for you, take a look at this video. I hope it will clarify a lot.

If you know how to improve this QuickSort Java code example please let me know by leaving a comment below.