Rohit Joshi

About Rohit Joshi

Rohit Joshi works as a Software Engineer in the Consumer Product Sector. He is a Sun Certified Java Programmer. He had worked in projects related to different domains. He is also involved in system analysis and system designing. He mainly works in Core Java and J2EE technologies but also have good experience in front-end technologies like Javascript and Jquery.

Quicksort algorithm in Java – Code Example

In this article, we will talk about how you can implement in Java one of the most famous and useful sorting techniques: Quicksort. Quicksort is the most widely used sorting algorithm. One of the main reasons is that it is faster than most common sorting algorithms. It was developed by the famous Computer Scientist Tony Hoare and it is based on the “Divide and Conquer Algorithm”.

First, we are going to explain how Quicksort works on an algorithmic level, with some simple examples. Finally, we will build our implementation in Java and discuss its performance.

 

1. The Quicksort Alogrithm

Quicksort works recursively in order to sort a given array. These are the three basic steps of the Quicksort algorithm:

1. Partition the array into a left sub-array and a right sub-array, in which the items in the left sub-array are smaller than the specified item and the items in the right sub-array are greater than the specified item.
2. Recursively call the Quicksort to sort the left sub-array.
3. Recursively call the Quicksort to sort the right sub-array.

The partitioning step is the key, when sorting an array with Quicksort. Quicksort itself uses a Partition algorithm to partition the given array.

The partition works by using two cursors (let say), one at each end of the array. These cursor moves towards each other. If the left cursor finds an item which is smaller than the pivot value, it ignores it and moves forward. But if, the item’s value is greater than the pivot value, it stops. Similarly for the right cursor, if an item is greater than the pivot value it ignores it and moves backwards, else the cursor stops. When both cursors stop, the items pointed by the cursors get swapped. That’s because these items are on the wrong side of the array. After the swap, both the cursors continue, and stop at the items which are on the wrong side of the array and swap them. And that’s how the algorithms goes on, until finally, all items are sorted.

The pivot value is the value which is used to partition the array into two sub-arrays. After the partition, the items in the left sub-array are smaller than the pivot value, and the items in the right sub-array are greater than the pivot value.

Partition

Partition

In the above figure, we chose 56 as a pivot value. After the partition (which of course consists of more than one sub steps), all the items on the left of the pivot are smaller, and the items on the right of it are greater than it and the pivot is at its sorted position. Also notice that, at this point, the array is not sorted of course. That was just one partitioning step.

You can choose any random value from the array as a pivot value. Later we will see that choosing a pivot value affects the performance of the algorithm. But for now, lets us take the right most item of the array as a pivot value and attempt to create the first version of our Java implementation.

QuicksortExample.java

package com.javacodegeeks.sorting.quicksort;

public class QuicksortExample {

	private static int []a;
	public static void main(String[] args) {
		// Get a random generated array
		a = getArray();
		
		// prints the given array
		printArray();
		
		// sort the array
		sort();
		
		System.out.println("");
		
		//prints the sorted array
		printArray();
		
	}
	
	// This method sorts an array and internally calls quickSort 
	public static void sort(){
		int left = 0;
		int right = a.length-1;
			
		quickSort(left, right);
	}
	
	// This method is used to sort the array using quicksort algorithm.
	// It takes the left and the right end of the array as the two cursors.
	private static void quickSort(int left,int right){
		
		// If both cursor scanned the complete array quicksort exits
		if(left >= right)
			return;
		
		// For the simplicity, we took the right most item of the array as a pivot 
		int pivot = a[right];
		int partition = partition(left, right, pivot);
		
		// Recursively, calls the quicksort with the different left and right parameters of the sub-array
		quickSort(0, partition-1);
		quickSort(partition+1, right);
	}
	
	// This method is used to partition the given array and returns the integer which points to the sorted pivot index
	private static int partition(int left,int right,int pivot){
		int leftCursor = left-1;
		int rightCursor = right;
		while(leftCursor < rightCursor){
                while(a[++leftCursor] < pivot);
                while(rightCursor > 0 && a[--rightCursor] > pivot);
			if(leftCursor >= rightCursor){
				break;
			}else{
				swap(leftCursor, rightCursor);
			}
		}
		swap(leftCursor, right);
		return leftCursor;
	}
	
	// This method is used to swap the values between the two given index
	public static void swap(int left,int right){
		int temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	
	public static void printArray(){
		for(int i : a){
			System.out.print(i+" ");
		}
	}
	
	public static int[] getArray(){
		int size=10;
		int []array = new int[size];
		int item = 0;
		for(int i=0;i<size;i++){
			item = (int)(Math.random()*100); 
			array[i] = item;
		}
		return array;
	}

}

  • If we run the above code, we will have the following results:
4 94 87 24 44 30 37 97 47 93 
4 24 30 37 44 47 87 93 94 97 

Let’s discuss how the above program works.

The quickSort() method takes two parameters, each holding the position of the cursors at the two ends of an array or a sub-array that needs to be sorted. For example, if left = 3, then the left cursor points to element 3 of the array. The method exits, if left is greater than or equal to right, which means that the array is already sorted or the length of the array is one. It also generates a pivot value, in this case the right most value of the array. The pivot value is passed to the partition method which is used to partition the given array.

The partition() method scans the array and swaps the items which are not at their proper place. The items which are greater than the pivot value, are swapped to the right of the pivot value with the values which are smaller than the pivot value. At the end of each scan, the left cursor ends up pointing to the left element of the right sub-array. The pivot is then swapped with it, and puts it into its proper sorted place. This method returns an integer that is the position of the sorted pivot value that partitioned the given array or a sub-array.

Then, the quicksort() method spawns the recursive call to sort the left sub-array and the right sub-array. Let’s have a deeper look into the partition method.

int leftCursor = left-1; : This statement initializes a leftCursor to one less than the left parameter. This is because while scanning, it first gets incremented and then used to evaluate. For example, if we are scanning the complete array and not a sub-array, the leftCursor would be at 0-1, i.e., -1.

int rightCursor = right; : This statement initializes a rightCursor to the right end of the given array, i.e., rightCursor = array.lenght-1.

while(leftCursor < rightCursor): The outer while loop runs till the leftCursor is not at same position or a position greater than the rightCursor. When this condition evaluates to false, it means that the cursors has scanned the complete array.

while(a[++leftCursor] < pivot);: This inner while loop has nothing inside its body. It’s used to move the left cursor towards right and compare the item it’s pointing with the pivot. The loop terminates if the pointed value is greater than the pivot value.

while(rightCursor > 0 && a[--rightCursor] > pivot);: This loop does a similar work. It moves towards the left of the array and compares each item it points with the pivot. If the pointed value is smaller than the pivot value, it terminates.

When both inner while loops terminate, both the cursors point to the items which are not at their proper place. We first check whether the cursors have crossed each other, which means they have scanned the full array. Then, it exits from the loop, else the items get swapped.

Then, the quicksort() method is called recursively. This time with the two sub-arrays, the left one starting from partitioin-1, and the right one starting from partition+1. It sorts the sub-arrays, until the full array gets partitioned and sorted, which finally results in the full sorted array.

Generally, quicksort operates in O(n*log n) time. But there are some cases, when its performance degrades to O(n^2). The problem lies in the selection of the pivot. In the above example, we choose the pivot randomly (the right most item of the array). The pivot should be the median of the items to be sorted. So that, half of the items in the array should be smaller than the pivot, and the rest should be the larger than the pivot. This would result in two equally sized sub-arrays. Two equal sized sub-arrays is, the best situation for the Quicksort algorithm, where it runs at O(logn). Having one large and one small sub-array results in less efficiency.

2. Median of 3 Partitioning

The best approach to choose a pivot, is by choosing the median of the first, middle, and the last items of the array. This approach is known as the “median of three approach”.

Median

Median

QuicksortMedianExample.java

package com.javacodegeeks.sorting.quicksort;

public class QuicksortMedianExample {

	private static int []a;
	public static void main(String[] args) {
		// Get a random generated array
		a = getArray();
		
		// prints the given array
		printArray();
		
		// sort the array
		sort();
		
		System.out.println("");
		
		//prints the sorted array
		printArray();
		
	}
	
	// This method sorts an array and internally calls quickSort 
	public static void sort(){
		int left = 0;
		int right = a.length-1;
			
		quickSort(left, right);
	}
	
	// This method is used to sort the array using quicksort algorithm.
	// It takes left and the right end of the array as two cursors
	private static void quickSort(int left,int right){
		
		// If both cursor scanned the complete array, quicksort exits
		if(left >= right)
			return;
		
		// Pivot using median of 3 approach
		int pivot = getMedian(left, right);
		int partition = partition(left, right, pivot);
		
		// Recursively, calls the quicksort with the different left and right parameters of the sub-array
		quickSort(0, partition-1);
		quickSort(partition+1, right);
	}
	
	// This method is used to partition the given array and returns the integer which points to the sorted pivot index
	private static int partition(int left,int right,int pivot){
		int leftCursor = left-1;
		int rightCursor = right;
		while(leftCursor < rightCursor){
        while(a[++leftCursor] < pivot);
        while(rightCursor > 0 && a[--rightCursor] > pivot);
			if(leftCursor >= rightCursor){
				break;
			}else{
				swap(leftCursor, rightCursor);
			}
		}
		swap(leftCursor, right);
		return leftCursor;
	}
	
	public static int getMedian(int left,int right){
		int center = (left+right)/2;
		
		if(a[left] > a[center])
			swap(left,center);
		
		if(a[left] > a[right])
			swap(left, right);
		
		if(a[center] > a[right])
			swap(center, right);
		
		swap(center, right);
		return a[right];
	}
	
	// This method is used to swap the values between the two given index
	public static void swap(int left,int right){
		int temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	
	public static void printArray(){
		for(int i : a){
			System.out.print(i+" ");
		}
	}
	
	public static int[] getArray(){
		int size=10;
		int []array = new int[size];
		int item = 0;
		for(int i=0;i<size;i++){
			item = (int)(Math.random()*100); 
			array[i] = item;
		}
		return array;
	}

}

  • If we run the above code, we will have the following results:
80 4 33 30 65 14 35 25 31 12 
4 12 14 25 30 31 33 35 65 80 

In the above example, we have used the median-of-3-approrach to find a “good” pivot. We used the first, the middle, and last items of the array to find the median. The median is the middle item between the orderly placed items. This approach is not only used to select the pivot, but it also put the three items in their sorted place in the array. Let’s have a look at the getMedian() used in the above example.

getMedian(int left, int right): This method is used to return a median among the three items specified. The returned median is used as the pivot in quicksort. This method has two parameters, both pointing at each end of the array or the sub-array. We used the middle, left and right items to find the median. At the end, we swapped the median with the item at the rightmost position of the array. So , after the scan all these three items should be in their proper sorted places in the array. This process is repeated with all the sub-arrays having different left, right and middle positions until the full array gets sorted.

3. Quicksort with String

So far, we have seen quicksort with integer arrays. In this example, we will sort an array of Strings using quicksort.

QuicksortStringExample.java

package com.javacodegeeks.sorting.quicksort;

public class QuicksortStringExample {

	private static String []a;
	public static void main(String[] args) {
		// Get an String array
		a = new String[]{"X","E","C","A"};
		
		// prints the given array
		printArray();
		
		// sort the array
		sort();
		
		System.out.println("");
		
		//prints the sorted array
		printArray();
		
	}
	
	// This method sort an array internally and internally calls quickSort 
	public static void sort(){
		int left = 0;
		int right = a.length-1;
			
		quickSort(left, right);
	}
	
	// This method is used to sort the array using quicksort algorithm.
	// It takes left and the right end of the array as two cursors
	private static void quickSort(int left,int right){
		
		// If both cursor scanned the complete array quicksort exits
		if(left >= right)
			return;
		
		// Pivot using median of 3 approach
		String pivot = getMedian(left, right);
		int partition = partition(left, right, pivot);
		
		// Recursively, calls the quicksort with the different left and right parameters of the sub-array
		quickSort(0, partition-1);
		quickSort(partition+1, right);
	}
	
	// This method is used to partition the given array and returns the integer which points to the sorted pivot index
	private static int partition(int left,int right,String pivot){
		int leftCursor = left-1;
		int rightCursor = right;
		while(leftCursor < rightCursor){
		while(((Comparable<String>)a[++leftCursor]).compareTo(pivot) < 0);
        while(rightCursor > 0 && ((Comparable<String>)a[--rightCursor]).compareTo(pivot) > 0);
			if(leftCursor >= rightCursor){
				break;
			}else{
				swap(leftCursor, rightCursor);
			}
		}
		swap(leftCursor, right);
		return leftCursor;
	}
	
	public static String getMedian(int left,int right){
		int center = (left+right)/2;
		
		if(((Comparable<String>)a[left]).compareTo(a[center]) > 0)
			swap(left,center);
		
		if(((Comparable<String>)a[left]).compareTo(a[right]) > 0)
			swap(left, right);
		
		if(((Comparable<String>)a[center]).compareTo(a[right]) > 0)
			swap(center, right);
		
		swap(center, right);
		return a[right];
	}
	
	// This method is used to swap the values between the two given index
	public static void swap(int left,int right){
		String temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	
	public static void printArray(){
		for(String i : a){
			System.out.print(i+" ");
		}
	}
	
}

  • If we run the above code, we will have the following results:
X E C A 
A C E X 

In the above example, we have sorted an array of Strings, using the quicksort. The String class implements the Comparable interface and overrides the compareTo() method. We have used the compareTo() method to compare the Strings. We have downcasted the String to the Comparable type and have used the compareTo() method to find the greater or the smaller between them.

The comparison is done using the natural ordering of the String. The natural ordering in the String is maintained alphabetically from “A – Z” and then from “a – z”. The rest of the code works same as shown in the previous example.

4. Quicksort Objects

In this example, we will see how to sort Objects of a class using the Quicksort. We will create a generic quicksort method which can be used to sort objects of any class. The class needs to implement the Comparable interface and override the method compareTo in order to use the quicksort, otherwise, it will throw a ClassCastException.

Let’s create an Employee class and sort employees on basis of their employeeCode using the Quicksort.

Employee.java

package com.javacodegeeks.entity;

public class Employee implements Comparable<Employee>{

	private String firstName;
	private String lastName;
	private int emplyeeCode;
	
	public Employee(String fistName,String lastName,int emplyeeCode){
		this.firstName = fistName;
		this.lastName = lastName;
		this.emplyeeCode = emplyeeCode;
	}
	
	public String getFirstName() {
		return firstName;
	}
	public void setFirstName(String firstName) {
		this.firstName = firstName;
	}
	public String getLastName() {
		return lastName;
	}
	public void setLastName(String lastName) {
		this.lastName = lastName;
	}
	public int getEmplyeeCode() {
		return emplyeeCode;
	}

	public void setEmplyeeCode(int emplyeeCode) {
		this.emplyeeCode = emplyeeCode;
	}

	public String toString(){
		return "Employee Code: "+getEmplyeeCode()+", Name:"+getFirstName()+" "+getLastName();
	}

	public int compareTo(Employee o) {
		Employee e = (Employee)o;
		if(this.emplyeeCode > e.getEmplyeeCode())
			return 1;
		if(this.emplyeeCode < e.getEmplyeeCode())
			return -1;
		if(this.emplyeeCode == e.getEmplyeeCode())
			return 0;
		return 0;
	}
}

We have created an Employee class which implements the Comparable interface and overrides the compareTo() method. The comparison between the Employee objects is defined by comparing the employeeCode property of the Employee objects. The comparTo() method returns an integer, which tells whether the current employeeCode is greater than, or smaller than or equal to the compared employeeCode. It returns 1, if the current employeeCode is greater than the compared employeeCode, -1 if, the current employeeCode is smaller than the compared employeeCode, else it returns 0 if both are equal. Since, the employeeCode is of type integer, we have compared it using the simple integer comparison operators.

QuicksortObjectExample.java

package com.javacodegeeks.sorting.quicksort;

import com.javacodegeeks.entity.Employee;

public class QuicksortObjectExample<T extends Comparable<T>> {

	private T []a;
	public static void main(String[] args) {
		
		Employee []employees = new Employee[5];
		Employee employee = new Employee("John","Carter",5658);
		employees[0] = employee;
		employee = new Employee("Mary","Carter",7412);
		employees[1] = employee;
		employee = new Employee("Alex","Lumb",1158);
		employees[2] = employee;
		employee = new Employee("David","Jhonson",1254);
		employees[3] = employee;
		employee = new Employee("Shaun","Smith",4587);
		employees[4] = employee;
		
		QuicksortObjectExample<Employee>ex = new QuicksortObjectExample<>();
		// Assigned array
		ex.a = employees;
		
		
		// prints the given array
		ex.printArray();
		
		// sort the array
		ex.sort();
		
		System.out.println("");
		
		//prints the sorted array
		ex.printArray();
		
	}
	
	// This method sort an array and internally calls quickSort 
	public void sort(){
		int left = 0;
		int right = a.length-1;
			
		quickSort(left, right);
	}
	
	// This method is used to sort the array using quicksort algorithm.
	// It takes left and the right end of the array as two cursors
	private void quickSort(int left,int right){
		
		// If both cursor scanned the complete array quicksort exits
		if(left >= right)
			return;
		
		// Pivot using median of 3 approach
		T pivot = getMedian(left, right);
		int partition = partition(left, right, pivot);
		
		// Recursively, calls the quicksort with the different left and right parameters of the sub-array
		quickSort(0, partition-1);
		quickSort(partition+1, right);
	}
	
	// This method is used to partition the given array and returns the integer which points to the sorted pivot index
	private int partition(int left,int right,T pivot){
		int leftCursor = left-1;
		int rightCursor = right;
		while(leftCursor < rightCursor){
        while(((Comparable<T>)a[++leftCursor]).compareTo(pivot) < 0);
        while(rightCursor > 0 && ((Comparable<T>)a[--rightCursor]).compareTo(pivot) > 0);
			if(leftCursor >= rightCursor){
				break;
			}else{
				swap(leftCursor, rightCursor);
			}
		}
		swap(leftCursor, right);
		return leftCursor;
	}
	
	public T getMedian(int left,int right){
		int center = (left+right)/2;
		
		if(((Comparable<T>)a[left]).compareTo(a[center]) > 0)
			swap(left,center);
		
		if(((Comparable<T>)a[left]).compareTo(a[right]) > 0)
			swap(left, right);
		
		if(((Comparable<T>)a[center]).compareTo(a[right]) > 0)
			swap(center, right);

		swap(center, right);
		return a[right];
	}
	
	// This method is used to swap the values between the two given index
	public void swap(int left,int right){
		T temp = a[left];
		a[left] = a[right];
		a[right] = temp;
	}
	
	public void printArray(){
		for(T i : a){
			System.out.println(i+" ");
		}
	}
	
}

  • If we run the above code, we will have the following results:
Employee Code: 5658, Name:John Carter 
Employee Code: 7412, Name:Mary Carter 
Employee Code: 1158, Name:Alex Lumb 
Employee Code: 1254, Name:David Jhonson 
Employee Code: 4587, Name:Shaun Smith 

Employee Code: 1158, Name:Alex Lumb 
Employee Code: 1254, Name:David Jhonson 
Employee Code: 4587, Name:Shaun Smith 
Employee Code: 5658, Name:John Carter 
Employee Code: 7412, Name:Mary Carter 

In the above example, we have created a generic class which can be used to sort any objects of any type, using Quicksort. Any class T which implements the Comparable interface can be used to sort using the above class. It performs the same functionality as shown in the previous example. The only difference is that this class is generic and it accepts any class T in its generic parameter which implements the Comparable interface.

In the previous code, we created the Employee class which implements Comparable interface and provides its own rule on how to compare its objects. The above class creates an array of the Employee class and assignes it to the array a. We print to show the current unsorted array of objects. Then, we called the sort() method which sorted the array of Employee type.

Please note that the comparison of the objects of the type Employee, is done by the rule defined in the compareTo() method in the Employee class i.e. on the basis of the employeeCode property of the class.

5. Download the source code

This was an example on Quicksort algorithm in Java. You can download the source code of this example from here: QuickSortExample.zip

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.
Examples Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Examples Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Examples Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close