Quicksort Sorting Algorithm in Java

Quicksort algorithm is one of the most used sorting algorithm, especially to sort large list and most of the programming languages, library have implemented it in one or another way. In Java, Arrays.sort() method sorts primitive data types using double pivot Quicksort algorithm, authored by Joshua Bloach and others. This implementation provides better performance for lot of data sets, where traditional quicksort algorithm reduced into quadratic performance. This method also uses MergeSort, another good sorting algorithm, to sort objects. QuickSort implementations are also available in C++ STL library. Have you ever thought why quicksort is so popular? because on average it is one of the fastest sorting algorithm we have. On average quicksort is a O(n log n) algorithm, while it's worst case is O(n^2), which is much better comparing with Bubble Sort or Insertion Sort. It's also one of the popular algorithm interview question, so as a programmer you must know how QuickSort works as well as how to implement Quicksort in Java or any other programming language. One of the most important thing interviewer look in your quicksort implementation is choice of pivot and whether you are sorting in place or not. In "in-place" sorting, actual sorting takes place in same array and no additional space is needed. Due to this reason, quicksort is very efficient in sorting large list of numbers, as no additional memory is required, a very space efficient sorting algorithm. Quicksort is also one of the naturally recursive algorithm and serves a good exercise for Java programmers to master art of recursion.

How QuickSort Algorithm works

Quicksort is a divide and conquer algorithm, which means original list is divided into multiple list, each of them is sorted individually and then sorted output is merged to produce the sorted list. Here is step by step explanation of how quicksort algorithm works :



Steps to implement Quick sort algorithm in place:



1) Choose an element, called pivot, from the list or array. Generally pivot is the middle element of array.



2) Reorder the list so that all elements with values less than the pivot come before the pivot, and all elements with values greater than the pivot come after it (equal values can go either way). This is also known as partitioning. After partitioning the pivot is in its final position.



3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values. If the array contains only one element or zero elements then the array is sorted.



Following GIF image will help you to understand working of Quick sort algorithm little better. In this image we have an array of integers which is not sorted and we need to sort them in ascending order. Our array is {6, 5, 3, 1, 8, 7, 2, 4} and we first choose 3 as pivot. Now partitioning starts and we pick 6 on left side of side, because its greater than 3. Now on right side, we leave 4 because its greater than 3, and pick 2 for swapping with 6. After swapping our list look like {2, 5, 3, 1, 8, 7, 6, 4}. Now we pick 5 on left side, and 1 on right side because it's greater than 3 and swap them again. Now, our array looks like {2, 1, 3, 5, 8, 7, 6, 4}. Since we are done with all elements with respect to 3 as pivot, we can now take the sub-array at left side of 3 and apply same procedure. This will sort the left array. Now on right side, we choose 4 as pivot, and repeat same procedure, which result in 4 swapped against 5. Now we take right side again with 6 as pivot and apply same procedure.

Sorting an array of integer using QuickSort sorting algorithm

Java Program to implement QuickSort Algorithm

Here is a Java program to sort an array of integers using QuickSort algorithm. It is an in-place, recursive implementation of QuickSort. Logic is encapsulated in QuickSort class, and method quickSort(int low, int high). This method is called recursively to sort the array. This algorithm work exactly as explained in above GIF image, so if you understand the logic there, its very easy to write by your own.

import java.util.Arrays;

/**
 * Test class to sort array of integers using Quicksort algorithm in Java.
 * @author Javin Paul
 */
public class QuickSortDemo{

    public static void main(String args[]) {

        // unsorted integer array
        int[] unsorted = {6, 5, 3, 1, 8, 7, 2, 4};
        System.out.println("Unsorted array :" + Arrays.toString(unsorted));

        QuickSort algorithm = new QuickSort();

        // sorting integer array using quicksort algorithm
        algorithm.sort(unsorted);

        // printing sorted array
        System.out.println("Sorted array :" + Arrays.toString(unsorted));

    }

}

/**
 * Java Program sort numbers using QuickSort Algorithm. QuickSort is a divide
 * and conquer algorithm, which divides the original list, sort it and then
 * merge it to create sorted output.
 *
 * @author Javin Paul
 */
class QuickSort {

    private int input[];
    private int length;

    public void sort(int[] numbers) {

        if (numbers == null || numbers.length == 0) {
            return;
        }
        this.input = numbers;
        length = numbers.length;
        quickSort(0, length - 1);
    }

    /*
     * This method implements in-place quicksort algorithm recursively.
     */
    private void quickSort(int low, int high) {
        int i = low;
        int j = high;

        // pivot is middle index
        int pivot = input[low + (high - low) / 2];

        // Divide into two arrays
        while (i <= j) {
            /**
             * As shown in above image, In each iteration, we will identify a
             * number from left side which is greater then the pivot value, and
             * a number from right side which is less then the pivot value. Once
             * search is complete, we can swap both numbers.
             */
            while (input[i] < pivot) {
                i++;
            }
            while (input[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                // move index to next position on both sides
                i++;
                j--;
            }
        }

        // calls quickSort() method recursively
        if (low < j) {
            quickSort(low, j);
        }

        if (i < high) {
            quickSort(i, high);
        }
    }

    private void swap(int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}

Output :
Unsorted array :[6, 5, 3, 1, 8, 7, 2, 4]
Sorted array :[1, 2, 3, 4, 5, 6, 7, 8]

Import points about Quicksort algorithm

Now we know how quick sort works and how to implement quicksort in Java, its time to revise some of the important points about this popular sorting algorithm.



1) QuickSort is a divide and conquer algorithm. Large list is divided into two and sorted separately (conquered), sorted list is merge later.



2) On "in-place" implementation of quick sort, list is sorted using same array, no additional array is required. Numbers are re-arranged pivot, also known as partitioning.



3) Partitioning happen around pivot, which is usually middle element of array.



4) Average case time complexity of Quicksort is O(n log n) and worst case time complexity is O(n ^2), which makes it one of the fasted sorting algorithm. Interesting thing is it's worst case performance is equal to Bubble Sort :)



5) Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.



6) Quicksort is also a good example of algorithm which makes best use of CPU caches, because of it's divide and conquer nature.



7) In Java, Arrays.sort() method uses quick sort algorithm to sort array of primitives. It's different than our algorithm, and uses two pivots. Good thing is that it perform much better than most of the quicksort algorithm available on internet for different data sets, where traditional quick sort perform poorly. One more reason, not to reinvent the wheel but to use the library method, when it comes to write production code.





That's all about Quicksort sorting algorithm in Java. It is one of the must know algorithm for all level of Java programmers, not that you need it often to implement it but to do well on interviews and use the lesson learned while implementing quick sort in Java. In our example, we have implemented quicksort "in-place", which is what you should do if asked to write quicksort in Java. Remember as Java programmer, you don't need to write your own implementation as library implementation are much better implemented and tested. You should use  Arrays.sort()  method to sort your array instead of writing your own sort method. One more reason of using library method is that they are usually improved over different version, and can take advantage of new machine instructions or native improvement.

Source:http://javarevisited.blogspot.com/2014/08/quicksort-sorting-algorithm-in-java-in-place-example.html