Quick sort algorithm Java

Selection sort algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.

There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.

To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and program them in Java.

Today we will look at quick sort using the pivot.

So far, we have discussed the following sorting algorithms:

• Sorting algorithms: an introduction to data sorting,
• Bubble sort,
• Comb sort,
• Big O notation: analyzing the complexity of algorithms,
• Selection sort – sorting by selection,
• Insertion sort – sorting by insertion,
• Counting sort – sorting by counting,
• Heap sort,
• Merge sort – sorting by splitting and merging.

What is quick sort? – definition

Quick sort is a very popular, versatile and efficient data sorting algorithm created between 1959 and 1961 by British computer scientist Tony Hoare. Like Merge sort, it uses the “divide and conquer” technique, the basic idea of which is based on trying to break down a complex problem into smaller parts and solving those parts separately. Quick sort is interesting because it tries to place one array element first in the right place – called a pivot, which has the special property that all array elements smaller than it are in the left part and all array elements larger than it are in the right part. However, the elements in both parts are not sorted correctly yet, but since the pivot is in the right place in the sorted output vector, it can serve as a place to divide the array into two parts – partitions. The two parts are then viewed as separate arrays that can be further split using new pivots until the parts contain only one element. The result of the sorting is a collection of the sorting results of the individual partitions. In general, Quicksort is faster than Mergesort and Heapsort, especially if we have a random ordering of elements in a large dataset that needs to be sorted. However, it should be emphasized that the performance of the algorithm is heavily dependent on the appropriate choice of the pivot. An unfortunate choice of the pivot can lead to a time complexity higher than that of the two algorithms mentioned above.

Quick sort – principle explained

As we mentioned above, the goal of the algorithm is to select, for a given input vector, an element – the pivot – that optimally splits the vector into two approximately large partitions, and all elements on the left are smaller and on the right larger than the pivot. The worst-case scenario occurs if we select a pivot where (almost) all elements are to the left of the pivot, or to the right. Therefore, there are several methods to select a pivot. The quick sort algorithm consists of the following steps:

1. selection of the pivot element,
2. rearranging the field,
3. dividing the field into partitions.

Quick sort – selection of pivot element

There are many ways to select the pivot element. Some of the simplest ones include selecting the first element, selecting the last element, selecting a random element, selecting the middle element, etc. There are also more complicated versions of pivot selection, where for example we randomly select three elements and use the median as the pivot.

Quick sort – field rearrangement

Suppose we have chosen the last element of the array as the pivot. We gradually compare the elements from the beginning to the pivot. If the current array element is larger than the pivot, we go to the next element, if the element is smaller, we replace it with one of the previous larger elements. When traversing we will need two indices, the first index determines the element currently being compared to the pivot, the second index determines where the elements smaller than the pivot end. Once the first index reaches the pivot, we replace the pivot with the first element larger than the pivot (the current position of the second index). We will then better understand how to work with these indices by using an example in Java.

Quick sort – dividing the field into partitions

The pivot is in the correct position after rearranging the array and is considered as a classified element. It also splits the original array into two partitions, which we recursively treat as two separate arrays to be sorted. Steps 1 to 3 are repeated sequentially. The recursion ends if we have a single element left in the array. The result of the sort then represents the individual elements from all partitions.

Quick sort animation, visualization, gif

The quick sort animation looks like this:

Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

You can find an animation of the algorithm on Toptal. There are 8 types of algorithms, you can also play the animation backwards.

On this page you can go through the steps of the algorithm to check the time consumption of the algorithm.

Quick sort algorithm advantages

• Efficient for huge random data sets,
• no data is copied during sorting (In-place sorting),
• can be parallelized and thus spread the computational load over multiple processors.

Quick sort algorithm disadvantages

• It is not stable,
• sensitive to the appropriate choice of pivot,
• unsuitable for small datasets due to the overhead associated with recursive calls and partition management.

Quick sort – time complexity

Quick Sort – implementation, Java code

Now we will show the implementation of the Quick sort algorithm in Java.

QuickSort.java

package sorting;

public class QuickSort {
    public void sort(int[] data, int low, int high)
    {
        if (low >= high)
            return;
        // Pivot index (pi)
        int pi = partition(data, low, high);
        // Sort both parts of array recursively
        sort(data, low, pi - 1);
        sort(data, pi + 1, high);
    }
    
    private int partition(int[] data, int low, int high) {
        // Selection of pivot (last element)
        int pivot = data[high];
        // Index of last element smaller than pivot
        int i = (low - 1);
        // Compare each element with pivot
        for (int j = low; j < high; j++) {
            if (data[j] <= pivot) {
                // Swap the smaller element with greater placed on (i+1)
                int temp = data[++i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        // Swap of pivot
        int temp = data[++i];
        data[i] = data[high];
        data[high] = temp;
        // Print some algo information
        System.out.println("Pivot selected: " + data[i]);
        printArray(data, low, i - 1);
        System.out.print("(" + data[i] + ") ");
        printArray(data, i + 1, high);
        System.out.println();
        // Returns the pivot index
        return i;
    }

    // Function to print an array
    public void printArray(int[] data)
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
    }
    public void printArray(int[] data, int low, int high)
    {
        for (int i = low; i <= high; i++)
            System.out.print(data[i] + " ");
    }
}

Main.java

import sorting.QuickSort;

public class Main {
    public static void main(String[] args) {
        int[] dataToSort = { 9, 1, 8, 2, 7, 3, 5, 6, 4 };
        QuickSort quickSort = new QuickSort();
        System.out.print("Input: ");
        quickSort.printArray(dataToSort);
        System.out.println();
        quickSort.sort(dataToSort, 0, dataToSort.length - 1);
        System.out.print("Sorted: ");
        quickSort.printArray(dataToSort);
    }
}

The output of this example is:

We have prepared the files with the above example in the form of code that you can run directly in Java. Download the Java QuickSort code here.

If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.