QuickSort In Java – Algorithm, Illustration & Implementation

This Tutorial Explains the Quicksort Algorithm in Java, its illustrations, QuickSort Implementation in Java with the help of Code Examples:

Quicksort sorting technique is widely used in software applications. Quicksort uses a divide-and-conquer strategy like merge sort.

In the quicksort algorithm, a special element called “pivot” is first selected and the array or list in question is partitioned into two subsets. The partitioned subsets may or may not be equal in size.

=> Read Through The Easy Java Training Series.

QuickSort Technique in Java

The partitions are such that all the elements less than the pivot element are towards the left of the pivot and the elements greater than the pivot is at the right of the pivot. The Quicksort routine recursively sorts the two sub-lists. Quicksort works efficiently and also faster even for larger arrays or lists.

Quicksort Partition Java

Partitioning is the key process of the Quicksort technique. So what is partitioning?

Given an array A, we choose a value x called pivot such that all the elements lesser than x are before x, and all the elements greater than x are after x.

A pivot value can be any of the following:

  • The first element in the array
  • The last element in the array
  • The mid element in the array
  • Any random element in the array

This pivot value is then placed at its proper position in the array by partitioning the array. Thus the output of the ‘partitioning’ process is the pivot value at its proper position and the elements less than pivot on the left and elements greater than a pivot at the right.

Consider the following diagram that explains the partitioning process.

partitioning process

The above diagram shows the process of partitioning array by repeatedly selecting the last element in the array as a pivot. At each level, note that we partition the array into two sub-arrays by placing pivot at its correct position.

Next, we list the algorithm and pseudo-code for quicksort technique that also includes partition routine.

Quicksort Algorithm Java

The general algorithm for quicksort is given below.

quicksort(Arr, low, high)
begin
	Declare array Arr[N] to be sorted
	low = 1st element; high = last element; pivot 
	if(low < high)
	begin
		pivot = partition (Arr,low,high);
		quicksort(Arr,low,pivot-1)
		quicksort(Arr,pivot+1,high)		
	end
end

Given below is the pseudo-code for the quicksort technique.

Pseudocode For Quick Sort

Following is the pseudo-code for a quick sort sorting technique. Note that we have provided the pseudo-code for quicksort and partitioning routine.

//pseudocode for quick sort main algorithm
procedure quickSort(arr[], low, high)
	arr = list to be sorted
	low – first element of the array
	high – last element of array
begin
    if (low < high)
    {
       // pivot – pivot element around which array will be partitioned 
        pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);  // call quicksort recursively to sort sub array before pivot
        quickSort(arr, pivot + 1, high); // call quicksort recursively to sort sub array after pivot
    }
end procedure

//partition routine selects and places the pivot element into its proper position that will partition the array. 
//Here, the pivot selected is the last element of the array
procedure partition (arr[], low, high)
begin
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
     i = (low - 1)  // Index of smaller element
    for j = low to high
    {
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
end procedure

Illustration

Let's see the illustration of the quicksort algorithm. Take the following array as an example. Here we have selected the last element as pivot.

As shown, the first element is labeled low and the last element is high.

Illustration of Quicksort algorithm

As evident in the above illustration, there are two pointers, high and low that respectively point to the last and first elements of the array. Both these pointers are moved as the quicksort progresses.

When the element pointed by the low pointer becomes greater than the pivot element and element pointed by the high pointer is lesser than the pivot element, we exchange the elements pointed by the low and high pointer, and each pointer advances by 1 position.

The above steps are carried out until both the pointers cross each other in the array. Once they cross, the pivot element gets its proper position in the array. At this point, the array is partitioned and now we can sort each sub-array independently by recursively applying a quick sort algorithm to each of the sub-array.

Quicksort Implementation In Java

QuickSort technique can be implemented in Java using either recursion or iteration. In this section, we will see both of these techniques.

Recursive Quicksort

We know that the basic technique of quicksort illustrated above uses recursion for sorting the array. In the recursive quicksort after partitioning the array, the quicksort routine is called recursively to sort the sub-arrays.

The below Implementation demonstrates the quicksort technique using recursion.

import java.util.*;
class QuickSort { 
    //selects last element as pivot, pi using which array is partitioned. 
    int partition(int intArray[], int low, int high) { 
        int pi = intArray[high];  
        int i = (low-1); // smaller element index   
        for (int j=low; j<high; j++) { 
            // check if current element is less than or equal to pi 
            if (intArray[j] <= pi) { 
                i++; 
                // swap intArray[i] and intArray[j] 
                int temp = intArray[i]; 
                intArray[i] = intArray[j]; 
                intArray[j] = temp; 
            } 
        } 
  
        // swap intArray[i+1] and intArray[high] (or pi) 
        int temp = intArray[i+1]; 
        intArray[i+1] = intArray[high]; 
        intArray[high] = temp; 
  
        return i+1; 
    } 
  
  
  //routine to sort the array partitions recursively
    void quick_sort(int intArray[], int low, int high) { 
        if (low < high) { 
            //partition the array around pi=>partitioning index and return pi
            int pi = partition(intArray, low, high); 
  
            // sort each partition recursively 
            quick_sort(intArray, low, pi-1); 
            quick_sort(intArray, pi+1, high); 
        } 
    } 
}

class Main{
    public static void main(String args[]) {
        //initialize a numeric array, intArray
        int intArray[] = {4,-1,6,8,0,5,-3}; 
        int n = intArray.length; 
        //print the original array
        System.out.println("Original Array: " + Arrays.toString(intArray));
        //call quick_sort routine using QuickSort object
        QuickSort obj = new QuickSort(); 
        obj.quick_sort(intArray, 0, n-1); 
        //print the sorted array
        System.out.println("\nSorted Array: " + Arrays.toString(intArray)); 
    } 
}

Output:

Original Array: [4, -1, 6, 8, 0, 5, -3]
Sorted Array: [-3, -1, 0, 4, 5, 6, 8]

Recursive quicksort - output

Iterative Quicksort

In iterative quicksort, we use the auxiliary stack to place intermediate parameters instead of using recursion and sort partitions.

The following Java program implements iterative quicksort.

import java.util.*; 
  
class Main { 
    //partitions the array around pivot=> last element
    static int partition(int numArray[], int low, int high)   { 
        int pivot = numArray[high]; 
        // smaller element index 
        int i = (low - 1); 
        for (int j = low; j <= high - 1; j++) { 
            // check if current element is less than or equal to pivot
            if (numArray[j] <= pivot) {
                i++; 
                // swap the elements
                int temp = numArray[i]; 
                numArray[i] = numArray[j]; 
                numArray[j] = temp; 
            } 
        } 
        // swap numArray[i+1] and numArray[high] (or pivot) 
        int temp = numArray[i + 1]; 
        numArray[i + 1] = numArray[high]; 
        numArray[high] = temp; 
        return i + 1; 
    } 
  
    
//sort the array using quickSort
    static void quickSort(int numArray[], int low, int high) 
    { 
        //auxillary stack
        int[] intStack = new int[high - low + 1]; 
  
        // top of stack initialized to -1
        int top = -1; 
  
        // push initial values of low and high to stack 
        intStack[++top] = low; 
        intStack[++top] = high; 
  
        // Keep popping from stack while is not empty 
        while (top >= 0) { 
            // Pop h and l 
            high = intStack[top--]; 
            low = intStack[top--]; 
  
            // Set pivot element at its correct position 
            // in sorted array 
            int pivot = partition(numArray, low, high); 
  
            // If there are elements on left side of pivot, 
            // then push left side to stack 
            if (pivot - 1 > low) { 
                intStack[++top] = low; 
                intStack[++top] = pivot - 1; 
            } 
  
            // If there are elements on right side of pivot, 
            // then push right side to stack 
            if (pivot + 1 < high) { 
                intStack[++top] = pivot + 1; 
                intStack[++top] = high; 
            } 
        } 
    }

public static void main(String args[]) 
    { 
        //define array to be sorted
        int numArray[] = { 3,2,6,-1,9,1,-6,10,5 }; 
        int n = 8; 
        System.out.println("Original Array:" + Arrays.toString(numArray)); 
        // call quickSort routine to sort the array 
        quickSort(numArray, 0, n - 1); 
        //print the sorted array
        System.out.println("\nSorted Array:" + Arrays.toString(numArray)); 
    } 
}

Output:

Original Array:[3, 2, 6, -1, 9, 1, -6, 10, 5]
Sorted Array:[-6, -1, 1, 2, 3, 6, 9, 10, 5]

Iterative quicksort - output

Frequently Asked Questions

Q #1) How does a Quicksort work?

Answer: Quicksort uses a divide and conquers strategy. Quicksort first partitions an array around a pivot element selected and generates sub-arrays that are sorted recursively.

Q #2) What is the time complexity of Quicksort?

Answer: The time complexity of quicksort on an average is O (nlogn). In the worst case, it is O (n^2) the same as the selection sort.

Q #3) Where is Quicksort used?

Answer: Quicksort is mostly used in recursive applications. Quicksort is the part of C-library. Also, almost the programming languages that use built-in sorting implement quicksort.

Q #4) What is the advantage of Quicksort?

Answer:

  • Quicksort is an efficient algorithm and can easily sort even a huge list of elements.
  • It is in-place sort and hence does not need extra space or memory.
  • It is widely used and provides an efficient way to sort data sets of any length.

Q #5) Why is Quicksort better than the merge sort?

Answer: The main reason for which the quicksort is better than the merge sort is that quicksort is in-place sorting method and does not require additional memory space. Merge sort requires additional memory for intermediate sorting.

Conclusion

Quicksort is considered as the best sorting algorithm mainly because of its efficiency to sort even a huge data set in O (nlogn) time.

Quicksort is also an in-place sort and doesn’t require additional memory space. In this tutorial, we have seen the recursive and iterative implementation of quicksort.

In our upcoming tutorial, we will continue with sorting methods in Java.

=> Take A Look At The Java Beginners Guide Here.