QuickSort in Java

QuickSort is a popular sorting algorithm that uses the Divide and Conquer paradigm to sort an array. QuickSort, just like Merge Sort, has an average time complexity of O(N log N), but its performance can deteriorate in worst-case scenarios.

In this tutorial, we will learn the QuickSort algorithm and implement it in Java.

QuickSort Algorithm

• As discussed above, the QuickSort algorithm uses Divide and Conquer approach to sort an array.
• The QuickSort algorithm begins by choosing a pivot element. We need to put this pivot element at its correct position.
• But it doesn't end there. We also need to put all the elements smaller than the pivot to the left of the pivot element, and all the elements greater than the pivot should be placed on its right.
• Our problem is now divided into two smaller subproblems and we also have one element of the array in its correct position. Now, we just need to recursively repeat this on the elements to the left of the pivot and the elements on the right half of the array.

Let's try to understand the above approach with the help of an example. Suppose we have to sort the following array - [5, 10, 7, 1, 2, 11, 25, 6] and element six is chosen as the pivot. We will use a pointer that is initially set to -1.

All array elements to the left of this pointer(including the element present at the pointer) should be smaller than our pivot.

We will iterate through the entire array and whenever we encounter an element smaller than the pivot, we will increment our pointer and place this smaller element at that position. The following steps explain the partitioning process.

The iteration starts with the first element of the array, which is 5. This is less than the pivot and so we will update the pointer value and put this element at that index.

• The next element is 10, and it is not smaller than 6, so we will simply move to the next element.
• 7 is also greater than 6, so we will move on.
• The next element is 1, which is smaller than 6. We will increment our pointer and swap the element present at that position with element 1.

• The next element is 2, which is again smaller than 6, so we will increment the pointer, and swap the values.

• The next elements are 11, and 25, which are greater than 6, so we won't change anything.
• The loop terminates and we will once again increment our pointer and will put the pivot at this position.

Importance of Pivot Element

• The pivot element plays a crucial role in determining the efficiency of the QuickSort algorithm. For best efficiency, the pivot element should divide the array into equal halves. But looking for such elements in the array can add up to the time complexity.
• The worst-case scenario is when the pivot is always chosen as the smallest or the largest element of the array. In these cases, the array will not be divided at all, because all the remaining elements will either be greater than the pivot or smaller than the pivot.
• Most of the implementations of QuickSort will either choose the first element or the last element as the pivot. A major drawback of this approach is that if the array is already sorted, then we are always choosing the smallest or the largest element of the array.
• A common method used to solve this problem is to randomly choose a pivot. This will significantly reduce the chances of getting the smallest or the largest element in each iteration.

QuickSort Implementation in Java

We will use two methods to implement QuickSort. One method is responsible for choosing a pivot and placing it in its correct position and it will also split the array into two halves of smaller and greater elements. We will call this the partition() method.

public static int partition(int[] arrToSort, int leftIdx, int rightIdx)
{
	int i = leftIdx - 1;
	int pivot = arrToSort[rightIdx];//the rightmost element is chosen as the pivot
		
	for(int j = leftIdx; j < rightIdx; j++)
	{
		//if current element is smaller than pivot then add it to the left half
		if(arrToSort[j] < pivot)
		{
			i += 1;
			int temp = arrToSort[j];
			arrToSort[j] = arrToSort[i];
			arrToSort[i] = temp;
		}
	}
		
	//add pivot element at its correct position
	int temp = arrToSort[i + 1];
	arrToSort[i + 1] = pivot;
	arrToSort[rightIdx] = temp;
		
	//return the sorted position of the pivot element
	return i + 1;
}

The other method will be called quicksort() and it will be responsible for recursive calls.

public static void quickSort(int[] arrToSort, int leftIdx, int rightIdx)
{
	if(leftIdx >= rightIdx)//array contains less than 2 elements
		return;
		
	int partitionIdx = partition(arrToSort, leftIdx, rightIdx);//getting the index of the pivot
		
	quickSort(arrToSort, leftIdx, partitionIdx - 1);//sorting the array to the left of pivot
	quickSort(arrToSort, partitionIdx + 1, rightIdx);//sorting the array to the right of pivot
}

Let's check if our code works correctly and gives the desired output.

import java.util.Arrays;
public class QuickSortDemo
{
    public static void main(String[] args)
	{
		int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
		int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
		int[] arr3 = {1};
		int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
		
		quickSort(arr1, 0, arr1.length - 1);
		quickSort(arr2, 0, arr2.length - 1);
		quickSort(arr3, 0, arr3.length - 1);
		quickSort(arr4, 0, arr4.length - 1);
		
		System.out.println(Arrays.toString(arr1));
		System.out.println(Arrays.toString(arr2));
		System.out.println(Arrays.toString(arr3));
		System.out.println(Arrays.toString(arr4));
	}
}

[1, 2, 6, 7, 9, 10, 15]
[1, 2, 3, 4, 5, 6, 7, 8]
[1]
[-20, -5, -1, 0, 2, 11, 20]

Time and Space Complexity

As discussed in the previous sections, QuickSort's efficiency is determined by the choice of the pivot element. The best-case and the average-case time complexity is O(NLogN), where N is the length of the input array. However, in the worst-case scenario, the time complexity can go up to O(N^2).

QuickSort is an in-place algorithm, which means it uses constant space. So space complexity of QuickSort is O(1).

Summary

QuickSort is an efficient sorting algorithm that can be very useful for sorting large amounts of data. The QuickSort algorithm works by choosing a pivot element and placing it in its correct position. It also places all the smaller elements to the left of the pivot and all the larger elements to its right. The choice of the pivot can affect the overall complexity of this algorithm, but randomly choosing a pivot will mostly give the optimal complexity.