QuickSort Example in Java using Recursion - Sorting Algorithm Implementation

Quicksort is one of the very popular sorting algorithms in programming, often used to sort a large list of numbers. Though their are numerous algorithm available to sort list of objects, including integer, string and floating point number, quicksort is best for general purpose. It's a divide and conquer algorithm, where we divide the given array with respect to a particular element, known as 'pivot' such that the lower partition of the array are less than the pivot and upper partition elements of the array are higher than the pivot. Quicksort is also one of the best example of recursion. It's naturally recursive, because it sort the large list by dividing into smaller sub-list and then applying same algorithm on those.

The base case of recursion is when list contains either one or zero element, in that case they are sorted. Quicksort is well ahead with primitive sorting algorithms e.g. insertion sort, selection sort and bubble sort. Average time complexity of quicksort is O(nlogn), while in worst case it's performance is similar to bubble sort i.e. O(n^2).

Apparently the worst case of quicksort is the best case of insertion sort, where they have to sort an already sorted list. In this article, we will learn how to implement quicksort algorithm in Java using recursion.

We will also learn how quicksort works, and how it sorts a large list of unsorted number. In the last section, we will see some important things about quicksort.



How QuickSort Algorithm Perform Sorting

An old saying is, a picture is worth more than a thousand words. This is completely true in case of understanding how sorting algorithm works. In past, I have understood insertion sort, selection sort and quicksort much better by following a diagram rather then reading about it. That's why I am sharing this diagram which explains how quicksort algorithm works, how it sort a list of integers. It's similar to flowchart but doesn't use the notation flowchart uses, instead it practically shows how sorting happens. Once you go through this diagram, read the explanation, it will make more sense.

How to implement QuickSort in Java - Working Example






































As I told before QuickSort is a recursive algorithm, it divides the big list into smaller list around pivot until those lists are individually sorted. First step of Quicksort algorithm is to determine pivot, it's general practice to choose middle element of array as pivot, but you are free to choose any index. Now you have two list, next step is to ensure that left partition only contains numbers less than pivot and right partition only contains numbers greater than pivot. We start pointer from left and right of pivot, and as soon as left pointer encounter 4, it stops because 4 is greater than 3. Similarly, right pointer stops at 3 because all numbers on right side of the list is greater than 3. Now it's time to swap, so 3 takes place of 4 and vice-versa. Now, we move pointer to one more step, since 2 > 3, left pointer shifts but since 4 > 3, it stopped. Since left point is also past right pointer it stopped. Now if we repeat this process one more time, list will be sorted.


Concept of  Pivot and Partition

Though we often select a middle element of the array as a pivot, there is no such there is no such rule and pivot can be any element of the given array. You can even consider the first element as the pivot in every partition. It's experienced that choice of pivot effects the distribution of the elements in partitioning and affects the complexity of the quicksort algorithm. As per rule of partition, numbers in lower partition should be less than the pivot and upper partition numbers should be higher than the pivot. Running time of partition logic is linear.


Complexity of Quicksort Algorithm:

On an average Quicksort Algorithm has the complexity of O(nlogn) and in the worst case, it has O(n²) when the elements of the input array are already sorted in ascending or descending order. The good thing about Quicksort is that it's an in place algorithm, which means it does not take any additional space, except those used by method stack. By the way, there are some tricks to improve the performance of quicksort, even in worst case. As suggested in one of the best algorithm design book, The Algorithm Design Manual, from Steven Skiena, you can apply the following the recommendation to improve your quicksort algorithm implementation.

1) Randomization
You can avoid worst-case performance of O(n²) when sorting nearly-sorted data by random permutation of keys. Though it incurs some cost of permutation but still gives better performance than O(n²)

2) Leave small sub-arrays for Insertion sort
finish Quicksort recursion and switch to insertion sort when fewer than 20 elements:

By the way, there is a drawback of using recursion to implement quicksort algorithm, It will not scale because JVM has no tail call optimization, it will simply grow the method call stack to something proportional to the array to sort, and it will fail for the very large array.


Java Program to Sort Integer Array using QuickSort Algorithm

Here is our recursive implementation of QuickSort sorting algorithm. We have used it to sort an array of randomly distributed integers. We have two set of input, one which doesn't contain any repeated number and other which contains duplicates. Logic of quicksort is encapsulated in method recursiveQuickSort(int[] array, int startIdx, int endIdx) and partition(int[] array, int left, int right), which implements partitioning logic. In order to hide implementation details, we have only exposed a convenient static utility method called quickSort(int[] array), which takes an integer array and sort that in-place.

package test;

import java.util.Arrays;


/**
* Java program to Sort integer array using QuickSort algorithm using recursion.
* Recursive QuickSort algorithm, partitioned list into two parts by a pivot,
* and then recursively sorts each list.
* @author Javin Paul
*/
public class QuickSort{

    public static void main(String args[]) {

        int[] input = { 23, 31, 1, 21, 36, 72};
        System.out.println("Before sorting : " + Arrays.toString(input));
        quickSort(input); // sort the integer array using quick sort algorithm
        System.out.println("After sorting : " + Arrays.toString(input));
     
        // input with duplicates
        int[] withDuplicates = { 11, 14, 16, 12, 11, 15};
        System.out.println("Before sorting : " + Arrays.toString(withDuplicates));
        quickSort(withDuplicates); // sort the integer array using quick sort algorithm
        System.out.println("After sorting : " + Arrays.toString(withDuplicates));
    }

    /**
     * public method exposed to client, sorts given array using QuickSort
     * Algorithm in Java
     * @param array
     */
    public static void quickSort(int[] array) {
        recursiveQuickSort(array, 0, array.length - 1);
    }

    /**
     * Recursive quicksort logic
     *
     * @param array input array
     * @param startIdx start index of the array
     * @param endIdx end index of the array
     */
    public static void recursiveQuickSort(int[] array, int startIdx, int endIdx) {
     
        int idx = partition(array, startIdx, endIdx);

        // Recursively call quicksort with left part of the partitioned array
        if (startIdx < idx - 1) {
            recursiveQuickSort(array, startIdx, idx - 1);
        }

        // Recursively call quick sort with right part of the partitioned array
        if (endIdx > idx) {
            recursiveQuickSort(array, idx, endIdx);
        }
    }

    /**
     * Divides array from pivot, left side contains elements less than
     * Pivot while right side contains elements greater than pivot.
     *
     * @param array array to partitioned
     * @param left lower bound of the array
     * @param right upper bound of the array
     * @return the partition index
     */
    public static int partition(int[] array, int left, int right) {
        int pivot = array[left]; // taking first element as pivot

        while (left <= right) {
            //searching number which is greater than pivot, bottom up
            while (array[left] < pivot) {
                left++;
            }
            //searching number which is less than pivot, top down
            while (array[right] > pivot) {
                right--;
            }

            // swap the values
            if (left <= right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;

                //increment left index and decrement right index
                left++;
                right--;
            }
        }
        return left;
    }
}

Output:
Before sorting : [23, 31, 1, 21, 36, 72]
After sorting : [1, 21, 23, 31, 36, 72]
Before sorting : [11, 14, 16, 12, 11, 15]
After sorting : [11, 11, 12, 14, 15, 16]


Things to know about QuickSort Algorithm in Java

As I said, QuickSort is one of the most popular sorting algorithms between programmers, may be just next to Bubble sort, which is ironically worst algorithm to sort a large list of numbers. But one thing is common between QuickSort and Bubble Sort, do you know what? In worst case both have the complexity of O(n^2).

1) QuickSort is a divide and conquer algorithm, which means it sort a large array of numbers by dividing them into a smaller array and then individually sorting them (conquer).

2) Average case complexity of Quicksort is O(n log(n)) and worst case complexity of Quicksort is O(n²).

3) Quicksort is a comparison sort and, in efficient implementations, it's not a stable sort, which means equal numbers may not retain their original position after sorting.

4) Quicksort algorithm can be implemented in-place, which means no additional space will be required. This makes it suitable to sort the large array of numbers.

5) Arrays.sort() method in Java use quicksort to sort an array of primitives e.g. array of integers or float and uses Mergesort to sot objects e.g. array of String.


That's all about how to implement QuickSort algorithm in Java. QuickSort is one of the fast and efficient sorting algorithm, perfect for sorting large arrays, but some programmer finds it extremely hard to understand. One reason of this could be that because quicksort is in-place algorithm due to which programmers find it bit confusing, but it's very efficient. Otherwise, if you choose simplicity you can always implement it in other ways.

8 comments:

  1. please post more sorting tutorials.
    hmm, that was helpful.thanks

    ReplyDelete
  2. Quicksort is slightly sensitive to input that happens to be in the right order, in which case it can skip some swaps. Mergesort doesn't have any such optimizations, which also makes Quicksort a bit faster compared to Mergesort.

    To know more about quicksort and mergesort, below link can be useful

    Why Quick sort is better than Merge sort

    ReplyDelete
  3. What is the benefit of Quicksort algorithm over other O(logN) algorithms e.g. mergesort, heapsort, or shellsort?

    ReplyDelete
    Replies
    1. Apart from in-place sorting (mergesort needs one more collection) I don't see any other benefit of using QuickSort. On the other hand there is a drawback of QuickSort that it's not a stable algorithm, which means same elements will lose their original position after sorting, which doesn't happen on mergesort. Unfortunately this is not obvious when you read any explanatio of how quicksort works, it's hidden and mostly overlookded.

      Delete
  4. can u post bubble sorting program

    ReplyDelete
    Replies
    1. Why do you want to learn bubble sort? Go try to learn heapsort, or bucket sort, there is no benefit of learning buble sort dude.

      Delete
  5. The algorithm fails if you have more than half array as duplicates. E.g.

    { 1, 23, 1, 31, 1, 21, 36, 1, 72, 1}; // fails if duplicates are >= half of the array size

    ReplyDelete
    Replies
    1. You mean quicksort algoirthm cannot handle duplicates if they are more than half of the array or is there a bug here?

      Delete